棧

棧的基本操作

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ù)據(jù)成員表示元素個數(shù)，這樣隊空：Q.size0,隊滿：Q.sizeMaxsize

3）增設tag，入隊時令tag=1，出隊時令tag=0，這樣能表示當Q.frontQ.rear時，如果tag1，則隊滿，tag==0則隊空

鏈式存儲：

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

Elemtype data;

struct LinkNode *next;

}LinkNode;

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

Node *front,*rear;

}LinkQueue;

棧和隊列的應用

括號匹配

表達式求值

后綴表達式：數(shù)據(jù)進棧，操作符則彈出2個數(shù)據(jù)進行操作再將結(jié)果進棧

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

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

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

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

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

從右至左掃描中綴表達式

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

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

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

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

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

遇到括號時

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

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

重復步驟2至5，直到表達式的最左邊

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

依次彈出s2中的元素并輸出，結(jié)果即為中綴表達式對應的前綴表達式

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

與轉(zhuǎn)換為前綴表達式相似，步驟如下：

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

從左至右掃描中綴表達式；

遇到操作數(shù)時，將其壓s2；

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

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

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

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

遇到括號時：

如果是左括號“(”，則直接壓入s1；

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

重復步驟2至5，直到表達式的最右邊；

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

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

特殊矩陣的壓縮存儲

對稱矩陣

三角矩陣

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

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

總結(jié)

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

最新評論