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詳解C語言編程中的函數(shù)指針以及函數(shù)回調(diào)
這篇文章主要介紹了C語言編程中的函數(shù)指針以及函數(shù)回調(diào),函數(shù)回調(diào)實際上就是讓函數(shù)指針作函數(shù)參數(shù)、調(diào)用時傳入函數(shù)地址,需要的朋友可以參考下2016-04-04C語言中求字符串長度的函數(shù)的幾種實現(xiàn)方法
這篇文章主要介紹了C語言中求字符串長度的函數(shù)的幾種實現(xiàn)方法,需要的朋友可以參考下2018-08-08c語言函數(shù)棧幀的創(chuàng)建和銷毀過程詳解
我們知道c語言中函數(shù)都是被調(diào)用的,main函數(shù)里面能調(diào)用其他函數(shù),其實main函數(shù)也是被別的函數(shù)調(diào)用的,下面通過本文給大家分享c語言函數(shù)棧幀的創(chuàng)建和銷毀過程,一起看看吧2021-08-08C++從文本文件讀取數(shù)據(jù)到vector中的方法
這篇文章主要給大家介紹了利用C++如何從文本文件讀取數(shù)據(jù)到vector中,文章通過實例給出示例代碼,相信會對大家的理解和學(xué)習(xí)很有幫助,有需要的朋友們下面來一起看看吧。2016-10-10C語言的getc()函數(shù)和gets()函數(shù)的使用對比
這篇文章主要介紹了C語言的getc()函數(shù)和gets()函數(shù)的使用對比,從數(shù)據(jù)流中一個是讀取字符一個是讀取字符串,需要的朋友可以參考下2015-08-08