欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言基于考研的棧和隊列

 更新時間:2021年08月26日 17:24:47   投稿:BJT  
這篇文章主要介紹了考研時的C語言中的堆棧和隊列的相關(guān)資料,需要的朋友可以參考下,小編覺得這篇文章寫的很好,希望能給你帶來幫助


棧的基本操作

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

在這里插入圖片描述

InitStack(&S):初始化

StackEmpty(S):判空,空則true,非空則false

Push(&S,x):入棧

Pop(&S,&x):出棧,并用x返回元素內(nèi)容

GetTop(S,&x):讀棧頂元素

DestroyStack(&S):銷毀并釋放空間

棧是一種受限的線性表,只允許在一端操作

棧若只能在棧頂操作,則只可能上溢

采用非遞歸方式重寫遞歸時,不一定要用棧,比如菲波那切數(shù)列只要用循環(huán)即可

共享棧:

從兩頭往中間填充,有效的利用空間。

出棧序列的個數(shù):1𝑛+1𝐶2𝑛𝑛

隊列

隊列也是受限的線性表,只允許在一端插入,另一端刪除

FIFO(First in first out)

常見操作:

InitQueue(&Q):初始化,構(gòu)造一個空隊列Q

QueueEmpty(Q):判空

EnQueue(&Q,x):入隊

DeQueue(&Q,&x):出隊并返回出隊的元素至x

GetHead(Q,&x):獲取對頭元素

隊列的大題真題考的是,畫初始狀態(tài),判空判滿的條件,入隊基本過程

So先看類似的概念,想法,思路,后期再看具體的代碼實現(xiàn),畢竟沒考過具體代碼

順序存儲定義:

#define Maxsize 50

typedef struct{
Elemtype data[Maxsize];

int front,rear;

}SqQueue;

循環(huán)隊列:

初始化:Q.front=Q.rear=0

隊首指針+1\入隊:Q.front=(Q.front+1)%Maxsize

隊尾指針+1\出隊:Q.rear=(Q.rear+1)%Maxsize

隊列長度:(Q.rear+Maxsize-Q.front)%Maxsize

因為隊滿和隊空都是Q.front=Q.rear,所以無法判斷到底是隊空還是隊滿

有三個解決辦法

1)常用方法:犧牲一個單元來區(qū)分隊空和隊滿,入隊是少用一個單元

隊滿條件:(Q.rear+1)%MaxsizeQ.front

隊空條件:Q.frontQ.rear

隊列中元素個數(shù):(Q.rear-Q.front+Maxsize)%Maxsize

2)類型中增設(shè)一個數(shù)據(jù)成員表示元素個數(shù),這樣隊空:Q.size0,隊滿:Q.sizeMaxsize

3)增設(shè)tag,入隊時令tag=1,出隊時令tag=0,這樣能表示當(dāng)Q.frontQ.rear時,如果tag1,則隊滿,tag==0則隊空

鏈?zhǔn)酱鎯Γ?/strong>

typedef struct LinkNode{ //定義節(jié)點

Elemtype data;

struct LinkNode *next;

}LinkNode;

typedef struct{ //定義隊列的首尾節(jié)點

Node *front,*rear;

}LinkQueue;

棧和隊列的應(yīng)用

括號匹配

表達(dá)式求值

后綴表達(dá)式:數(shù)據(jù)進(jìn)棧,操作符則彈出2個數(shù)據(jù)進(jìn)行操作再將結(jié)果進(jìn)棧

同一個問題,遞歸算法和非遞歸算法一般來說,非遞歸效率比較低,因為有很多重復(fù)計算

圖的廣度優(yōu)先算法要借助輔助隊列

將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式

轉(zhuǎn)換步驟如下:

初始化兩個棧:運算符棧s1,儲存中間結(jié)果的棧s2

從右至左掃描中綴表達(dá)式

遇到操作數(shù)時,將其壓入s2

遇到運算符時,比較其與s1棧頂運算符的優(yōu)先級

如果s1為空,或棧頂運算符為右括號“)”,則直接將此運算符入棧

否則,若優(yōu)先級比棧頂運算符的較高或相等,也將運算符壓入s1

否則,將s1棧頂?shù)倪\算符彈出并壓入到s2中,再次轉(zhuǎn)到(4-1)與s1中新的棧頂運算符相比較

遇到括號時

如果是右括號“)”,則直接壓入s1

如果是左括號“(”,則依次彈出S1棧頂?shù)倪\算符,并壓入S2,直到遇到右括號為止,此時將這一對括號丟棄

重復(fù)步驟2至5,直到表達(dá)式的最左邊

將s1中剩余的運算符依次彈出并壓入s2

依次彈出s2中的元素并輸出,結(jié)果即為中綴表達(dá)式對應(yīng)的前綴表達(dá)式

將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式

與轉(zhuǎn)換為前綴表達(dá)式相似,步驟如下:

初始化兩個棧:運算符棧s1和儲存中間結(jié)果的棧s2;

從左至右掃描中綴表達(dá)式;

遇到操作數(shù)時,將其壓s2;

遇到運算符時,比較其與s1棧頂運算符的優(yōu)先級:

如果s1為空,或棧頂運算符為左括號“(”,則直接將此運算符入棧;

否則,若優(yōu)先級比棧頂運算符的高,也將運算符壓入s1(注意轉(zhuǎn)換為前綴表達(dá)式時是優(yōu)先級較高或相同,而這里則不包括相同的情況);

否則,將s1棧頂?shù)倪\算符彈出并壓入到s2中,再次轉(zhuǎn)到(4-1)與s1中新的棧頂運算符相比較;

遇到括號時:

如果是左括號“(”,則直接壓入s1;

如果是右括號“)”,則依次彈出s1棧頂?shù)倪\算符,并壓入s2,直到遇到左括號為止,此時將這一對括號丟棄;

重復(fù)步驟2至5,直到表達(dá)式的最右邊;

將s1中剩余的運算符依次彈出并壓入s2;

依次彈出s2中的元素并輸出,結(jié)果的逆序即為中綴表達(dá)式對應(yīng)的后綴表達(dá)式(轉(zhuǎn)換為前綴表達(dá)式時不用逆序)

特殊矩陣的壓縮存儲

對稱矩陣

三角矩陣

三對角矩陣:又稱帶狀矩陣

稀疏矩陣:三元組既可以用數(shù)組存儲,也可以用十字鏈表法

總結(jié)

本篇文章就到這里了,希望能給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

相關(guān)文章

  • 關(guān)于c++11與c風(fēng)格路徑拼接的速度對比

    關(guān)于c++11與c風(fēng)格路徑拼接的速度對比

    這篇文章主要介紹了關(guān)于c++11與c風(fēng)格路徑拼接的速度對比分析,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-07-07
  • C++實現(xiàn)字符串刪除字符后逆序輸出

    C++實現(xiàn)字符串刪除字符后逆序輸出

    這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)字符串刪除字符后逆序輸出,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-05-05
  • C語言之平衡二叉樹詳解

    C語言之平衡二叉樹詳解

    平衡二叉樹是具有平衡屬性的有序二叉樹,本文主要介紹了C語言中的平衡二叉樹,具有一定的參考價值,需要的小伙伴可以參考閱讀
    2023-04-04
  • C++實現(xiàn)井字棋游戲

    C++實現(xiàn)井字棋游戲

    這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)井字棋游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-07-07
  • 詳解C語言編程中的函數(shù)指針以及函數(shù)回調(diào)

    詳解C語言編程中的函數(shù)指針以及函數(shù)回調(diào)

    這篇文章主要介紹了C語言編程中的函數(shù)指針以及函數(shù)回調(diào),函數(shù)回調(diào)實際上就是讓函數(shù)指針作函數(shù)參數(shù)、調(diào)用時傳入函數(shù)地址,需要的朋友可以參考下
    2016-04-04
  • C語言中求字符串長度的函數(shù)的幾種實現(xiàn)方法

    C語言中求字符串長度的函數(shù)的幾種實現(xiàn)方法

    這篇文章主要介紹了C語言中求字符串長度的函數(shù)的幾種實現(xiàn)方法,需要的朋友可以參考下
    2018-08-08
  • c語言函數(shù)棧幀的創(chuàng)建和銷毀過程詳解

    c語言函數(shù)棧幀的創(chuàng)建和銷毀過程詳解

    我們知道c語言中函數(shù)都是被調(diào)用的,main函數(shù)里面能調(diào)用其他函數(shù),其實main函數(shù)也是被別的函數(shù)調(diào)用的,下面通過本文給大家分享c語言函數(shù)棧幀的創(chuàng)建和銷毀過程,一起看看吧
    2021-08-08
  • C++從文本文件讀取數(shù)據(jù)到vector中的方法

    C++從文本文件讀取數(shù)據(jù)到vector中的方法

    這篇文章主要給大家介紹了利用C++如何從文本文件讀取數(shù)據(jù)到vector中,文章通過實例給出示例代碼,相信會對大家的理解和學(xué)習(xí)很有幫助,有需要的朋友們下面來一起看看吧。
    2016-10-10
  • C++設(shè)計模式之備忘錄模式

    C++設(shè)計模式之備忘錄模式

    這篇文章主要介紹了C++設(shè)計模式之備忘錄模式,本文講解了什么是備忘錄模式、備忘錄模式的UML類圖、備忘錄模式的使用場合等內(nèi)容,需要的朋友可以參考下
    2014-10-10
  • C語言的getc()函數(shù)和gets()函數(shù)的使用對比

    C語言的getc()函數(shù)和gets()函數(shù)的使用對比

    這篇文章主要介紹了C語言的getc()函數(shù)和gets()函數(shù)的使用對比,從數(shù)據(jù)流中一個是讀取字符一個是讀取字符串,需要的朋友可以參考下
    2015-08-08

最新評論