C語(yǔ)言基于考研的棧和隊(duì)列
棧
棧的基本操作
InitStack(&S):初始化
StackEmpty(S):判空，空則true，非空則false
Push(&S,x):入棧
Pop(&S,&x):出棧，并用x返回元素內(nèi)容
GetTop(S,&x):讀棧頂元素
DestroyStack(&S):銷毀并釋放空間
棧是一種受限的線性表，只允許在一端操作
棧若只能在棧頂操作，則只可能上溢
采用非遞歸方式重寫(xiě)遞歸時(shí)，不一定要用棧，比如菲波那切數(shù)列只要用循環(huán)即可
共享?xiàng)＃?/strong>
從兩頭往中間填充，有效的利用空間。
出棧序列的個(gè)數(shù)：1𝑛+1𝐶2𝑛𝑛
隊(duì)列
隊(duì)列也是受限的線性表，只允許在一端插入，另一端刪除
FIFO（First in first out）
常見(jiàn)操作：
InitQueue（&Q）：初始化，構(gòu)造一個(gè)空隊(duì)列Q
QueueEmpty（Q）：判空
EnQueue（&Q，x）：入隊(duì)
DeQueue（&Q，&x）：出隊(duì)并返回出隊(duì)的元素至x
GetHead（Q，&x）：獲取對(duì)頭元素
隊(duì)列的大題真題考的是，畫(huà)初始狀態(tài)，判空判滿的條件，入隊(duì)基本過(guò)程
So先看類似的概念，想法，思路，后期再看具體的代碼實(shí)現(xiàn)，畢竟沒(méi)考過(guò)具體代碼
順序存儲(chǔ)定義：
#define Maxsize 50
typedef struct{
Elemtype data[Maxsize];
int front,rear;
}SqQueue;
循環(huán)隊(duì)列：
初始化：Q.front=Q.rear=0
隊(duì)首指針+1\入隊(duì)：Q.front=(Q.front+1)%Maxsize
隊(duì)尾指針+1\出隊(duì)：Q.rear=(Q.rear+1)%Maxsize
隊(duì)列長(zhǎng)度：(Q.rear+Maxsize-Q.front)%Maxsize
因?yàn)殛?duì)滿和隊(duì)空都是Q.front=Q.rear，所以無(wú)法判斷到底是隊(duì)空還是隊(duì)滿
有三個(gè)解決辦法
1）常用方法：犧牲一個(gè)單元來(lái)區(qū)分隊(duì)空和隊(duì)滿，入隊(duì)是少用一個(gè)單元
隊(duì)滿條件：（Q.rear+1）%MaxsizeQ.front
隊(duì)空條件：Q.frontQ.rear
隊(duì)列中元素個(gè)數(shù)：（Q.rear-Q.front+Maxsize）%Maxsize
2）類型中增設(shè)一個(gè)數(shù)據(jù)成員表示元素個(gè)數(shù)，這樣隊(duì)空：Q.size0,隊(duì)滿：Q.sizeMaxsize
3）增設(shè)tag，入隊(duì)時(shí)令tag=1，出隊(duì)時(shí)令tag=0，這樣能表示當(dāng)Q.frontQ.rear時(shí)，如果tag1，則隊(duì)滿，tag==0則隊(duì)空
鏈?zhǔn)酱鎯?chǔ)：
typedef struct LinkNode{ //定義節(jié)點(diǎn)
Elemtype data;
struct LinkNode *next;
}LinkNode;
typedef struct{ //定義隊(duì)列的首尾節(jié)點(diǎn)
Node *front,*rear;
}LinkQueue;
棧和隊(duì)列的應(yīng)用
括號(hào)匹配
表達(dá)式求值
后綴表達(dá)式：數(shù)據(jù)進(jìn)棧，操作符則彈出2個(gè)數(shù)據(jù)進(jìn)行操作再將結(jié)果進(jìn)棧
同一個(gè)問(wèn)題，遞歸算法和非遞歸算法一般來(lái)說(shuō)，非遞歸效率比較低，因?yàn)橛泻芏嘀貜?fù)計(jì)算
圖的廣度優(yōu)先算法要借助輔助隊(duì)列
將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式
轉(zhuǎn)換步驟如下:
初始化兩個(gè)棧:運(yùn)算符棧s1，儲(chǔ)存中間結(jié)果的棧s2
從右至左掃描中綴表達(dá)式
遇到操作數(shù)時(shí)，將其壓入s2
遇到運(yùn)算符時(shí)，比較其與s1棧頂運(yùn)算符的優(yōu)先級(jí)
如果s1為空，或棧頂運(yùn)算符為右括號(hào)“)”，則直接將此運(yùn)算符入棧
否則，若優(yōu)先級(jí)比棧頂運(yùn)算符的較高或相等，也將運(yùn)算符壓入s1
否則，將s1棧頂?shù)倪\(yùn)算符彈出并壓入到s2中，再次轉(zhuǎn)到(4-1)與s1中新的棧頂運(yùn)算符相比較
遇到括號(hào)時(shí)
如果是右括號(hào)“)”，則直接壓入s1
如果是左括號(hào)“(”，則依次彈出S1棧頂?shù)倪\(yùn)算符，并壓入S2，直到遇到右括號(hào)為止，此時(shí)將這一對(duì)括號(hào)丟棄
重復(fù)步驟2至5，直到表達(dá)式的最左邊
將s1中剩余的運(yùn)算符依次彈出并壓入s2
依次彈出s2中的元素并輸出，結(jié)果即為中綴表達(dá)式對(duì)應(yīng)的前綴表達(dá)式
將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式
與轉(zhuǎn)換為前綴表達(dá)式相似，步驟如下：
初始化兩個(gè)棧：運(yùn)算符棧s1和儲(chǔ)存中間結(jié)果的棧s2；
從左至右掃描中綴表達(dá)式；
遇到操作數(shù)時(shí)，將其壓s2；
遇到運(yùn)算符時(shí)，比較其與s1棧頂運(yùn)算符的優(yōu)先級(jí)：
如果s1為空，或棧頂運(yùn)算符為左括號(hào)“(”，則直接將此運(yùn)算符入棧；
否則，若優(yōu)先級(jí)比棧頂運(yùn)算符的高，也將運(yùn)算符壓入s1（注意轉(zhuǎn)換為前綴表達(dá)式時(shí)是優(yōu)先級(jí)較高或相同，而這里則不包括相同的情況）；
否則，將s1棧頂?shù)倪\(yùn)算符彈出并壓入到s2中，再次轉(zhuǎn)到(4-1)與s1中新的棧頂運(yùn)算符相比較；
遇到括號(hào)時(shí)：
如果是左括號(hào)“(”，則直接壓入s1；
如果是右括號(hào)“)”，則依次彈出s1棧頂?shù)倪\(yùn)算符，并壓入s2，直到遇到左括號(hào)為止，此時(shí)將這一對(duì)括號(hào)丟棄；
重復(fù)步驟2至5，直到表達(dá)式的最右邊；
將s1中剩余的運(yùn)算符依次彈出并壓入s2；
依次彈出s2中的元素并輸出，結(jié)果的逆序即為中綴表達(dá)式對(duì)應(yīng)的后綴表達(dá)式（轉(zhuǎn)換為前綴表達(dá)式時(shí)不用逆序）
特殊矩陣的壓縮存儲(chǔ)
對(duì)稱矩陣
三角矩陣
三對(duì)角矩陣：又稱帶狀矩陣
稀疏矩陣：三元組既可以用數(shù)組存儲(chǔ)，也可以用十字鏈表法
總結(jié)
本篇文章就到這里了，希望能給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！
- C語(yǔ)言 淺談棧與隊(duì)列的定義與操作
- C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)進(jìn)階之棧和隊(duì)列的實(shí)現(xiàn)
- C語(yǔ)言編程數(shù)據(jù)結(jié)構(gòu)棧與隊(duì)列的全面講解示例教程
- C語(yǔ)言編程數(shù)據(jù)結(jié)構(gòu)的棧和隊(duì)列
- C語(yǔ)言中棧和隊(duì)列實(shí)現(xiàn)表達(dá)式求值的實(shí)例
- C語(yǔ)言用棧和隊(duì)列實(shí)現(xiàn)的回文檢測(cè)功能示例
- C語(yǔ)言 表、棧和隊(duì)列詳解及實(shí)例代碼
- 深入淺析C語(yǔ)言中堆棧和隊(duì)列
- C語(yǔ)言中用棧+隊(duì)列實(shí)現(xiàn)隊(duì)列中的元素逆置
相關(guān)文章
關(guān)于c++11與c風(fēng)格路徑拼接的速度對(duì)比
這篇文章主要介紹了關(guān)于c++11與c風(fēng)格路徑拼接的速度對(duì)比分析，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)字符串刪除字符后逆序輸出，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-05-05
平衡二叉樹(shù)是具有平衡屬性的有序二叉樹(shù)，本文主要介紹了C語(yǔ)言中的平衡二叉樹(shù)，具有一定的參考價(jià)值，需要的小伙伴可以參考閱讀2023-04-04
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)井字棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-07-07
詳解C語(yǔ)言編程中的函數(shù)指針以及函數(shù)回調(diào)
這篇文章主要介紹了C語(yǔ)言編程中的函數(shù)指針以及函數(shù)回調(diào),函數(shù)回調(diào)實(shí)際上就是讓函數(shù)指針作函數(shù)參數(shù)、調(diào)用時(shí)傳入函數(shù)地址,需要的朋友可以參考下2016-04-04
C語(yǔ)言中求字符串長(zhǎng)度的函數(shù)的幾種實(shí)現(xiàn)方法
這篇文章主要介紹了C語(yǔ)言中求字符串長(zhǎng)度的函數(shù)的幾種實(shí)現(xiàn)方法,需要的朋友可以參考下2018-08-08
c語(yǔ)言函數(shù)棧幀的創(chuàng)建和銷毀過(guò)程詳解
我們知道c語(yǔ)言中函數(shù)都是被調(diào)用的，main函數(shù)里面能調(diào)用其他函數(shù)，其實(shí)main函數(shù)也是被別的函數(shù)調(diào)用的，下面通過(guò)本文給大家分享c語(yǔ)言函數(shù)棧幀的創(chuàng)建和銷毀過(guò)程，一起看看吧2021-08-08
C++從文本文件讀取數(shù)據(jù)到vector中的方法
這篇文章主要給大家介紹了利用C++如何從文本文件讀取數(shù)據(jù)到vector中，文章通過(guò)實(shí)例給出示例代碼，相信會(huì)對(duì)大家的理解和學(xué)習(xí)很有幫助，有需要的朋友們下面來(lái)一起看看吧。2016-10-10
這篇文章主要介紹了C++設(shè)計(jì)模式之備忘錄模式,本文講解了什么是備忘錄模式、備忘錄模式的UML類圖、備忘錄模式的使用場(chǎng)合等內(nèi)容,需要的朋友可以參考下2014-10-10
C語(yǔ)言的getc()函數(shù)和gets()函數(shù)的使用對(duì)比
這篇文章主要介紹了C語(yǔ)言的getc()函數(shù)和gets()函數(shù)的使用對(duì)比,從數(shù)據(jù)流中一個(gè)是讀取字符一個(gè)是讀取字符串,需要的朋友可以參考下2015-08-08