C語言基于考研的棧和隊列
棧
棧的基本操作
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)格路徑拼接的速度對比分析，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)字符串刪除字符后逆序輸出，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05
平衡二叉樹是具有平衡屬性的有序二叉樹，本文主要介紹了C語言中的平衡二叉樹，具有一定的參考價值，需要的小伙伴可以參考閱讀2023-04-04
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)井字棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
詳解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)方法,需要的朋友可以參考下2018-08-08
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中，文章通過實例給出示例代碼，相信會對大家的理解和學(xué)習(xí)很有幫助，有需要的朋友們下面來一起看看吧。2016-10-10
這篇文章主要介紹了C++設(shè)計模式之備忘錄模式,本文講解了什么是備忘錄模式、備忘錄模式的UML類圖、備忘錄模式的使用場合等內(nèi)容,需要的朋友可以參考下2014-10-10
C語言的getc()函數(shù)和gets()函數(shù)的使用對比
這篇文章主要介紹了C語言的getc()函數(shù)和gets()函數(shù)的使用對比,從數(shù)據(jù)流中一個是讀取字符一個是讀取字符串,需要的朋友可以參考下2015-08-08