第3章 棧與隊(duì)列

第3章棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)案例教程Page

2案例提出——迷宮問題迷宮問題是取自心理學(xué)的一個(gè)經(jīng)典實(shí)驗(yàn)。在該實(shí)驗(yàn)中，把一只老鼠從一個(gè)無頂大盒子的門中放入，在盒子中設(shè)置了許多墻，對(duì)行進(jìn)方向形成了多處阻擋。盒子僅有一個(gè)出口，在出口處放置以塊奶酪，吸引老鼠在迷宮中尋找道路以到達(dá)出口。對(duì)同一只老鼠重復(fù)進(jìn)行上述實(shí)驗(yàn)，一直到老鼠從入口走到出口，而不走錯(cuò)一步。老鼠經(jīng)過多次試驗(yàn)最終學(xué)會(huì)走通迷宮的路線。設(shè)計(jì)一個(gè)計(jì)算機(jī)程序?qū)θ我庠O(shè)定的矩形迷宮如下圖所示，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。Page

33.2知識(shí)點(diǎn)學(xué)習(xí)

3.2.1棧棧是一種特殊的線性表，用途十分廣泛。將遞歸算法轉(zhuǎn)換成非遞歸算法時(shí)常常會(huì)用到棧，實(shí)現(xiàn)二叉樹的算法中也會(huì)使用棧。棧是一種只能在一端進(jìn)行插入或刪除的線性表。表中允許進(jìn)行插入、刪除操作的一端稱為棧頂（top），表的另一端稱為棧底（bottom）。當(dāng)棧中沒有數(shù)據(jù)元素時(shí)，稱為空棧。棧的插入操作通常稱為進(jìn)棧或入棧，棧的刪除操作通常稱為退?；虺鰲?。Page

43.2.1.2棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)#defineMaxsize100;//最多元素個(gè)數(shù)typedefintElemType;//數(shù)據(jù)類型typedefstruct{ ElemTypeelem[MaxSize]; inttop; //棧頂指針}SqStack;//順序棧類型定義Page

5入棧

Page

63.2.1.3棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)Page

7（鏈棧中數(shù)據(jù)結(jié)點(diǎn)的類型LinkStack定義如下：typedefintElemType;typedefstructlinknode{ElemTypedata;//數(shù)據(jù)域structlinknode*next;//指針域}LinkStack;Page

83.2.1.4棧的應(yīng)用舉例1、算術(shù)表達(dá)式的前綴與后綴表達(dá)（任何一個(gè)表達(dá)式都是由操作數(shù)、運(yùn)算符或界限符組成的。在表達(dá)式求值問題中的操作數(shù)可以是常數(shù)、被說明為變量或常量的標(biāo)識(shí)符、表達(dá)式；運(yùn)算符指的是“+”、“-”、“*”、“/”；界限符指的是括號(hào)等字符。在本例中的表達(dá)式求值問題就是：對(duì)于一個(gè)包含“+”、“-”、“*”、“/”、正整數(shù)和圓括號(hào)的合法數(shù)學(xué)表達(dá)式，計(jì)算該表達(dá)式的運(yùn)算結(jié)果。Page

9前綴轉(zhuǎn)后綴算法演示Page

10后綴轉(zhuǎn)前綴算法演示Page

11練習(xí)A*b-cA*b+(c-d*e)/fPage

12棧解決迷宮問題算法演示Page

133.2.2隊(duì)列隊(duì)列也具有廣泛的應(yīng)用。特別是在操作系統(tǒng)資源分配和排隊(duì)論中大量地使用隊(duì)列。本節(jié)介紹隊(duì)列的定義、隊(duì)列的存儲(chǔ)結(jié)構(gòu)和隊(duì)列的應(yīng)用。Page

143.2.2.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)順序隊(duì)列類型SqQueue定義如下：#defineMaxSize100typedefintElemType;typedefstruct{ElemTypeelem[MaxSize];intfront,rear;//隊(duì)首和隊(duì)尾指針}SqQueue;Page

15隊(duì)列操作Page

16循環(huán)隊(duì)列Page

17循環(huán)隊(duì)列滿和空指針判斷沖突Page

183.2.2.3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是僅在表頭刪除和表尾插入的單鏈表，因此一個(gè)棧隊(duì)列需要使用兩個(gè)指針：指向隊(duì)頭元素的隊(duì)首指針front和指向隊(duì)尾元素的隊(duì)尾指針rear。用于存儲(chǔ)隊(duì)列的單鏈表簡(jiǎn)稱鏈隊(duì)。如圖3.11所示的鏈隊(duì)列。Page

19鏈隊(duì)中數(shù)據(jù)結(jié)點(diǎn)的類型QNode定義typedefintElemType;typedefstructqnode{ElemTypedata;structqnode*next;}QNode;//鏈隊(duì)數(shù)據(jù)結(jié)點(diǎn)類型定義Page

20一個(gè)鏈隊(duì)的動(dòng)態(tài)變化過程Page

213.2.2.4隊(duì)列的應(yīng)用舉例

求解報(bào)數(shù)問題設(shè)有n個(gè)人站成一排，從左向右的編號(hào)分別為1~n，現(xiàn)在從左往右報(bào)數(shù)“1，2，1，2…”，數(shù)到“1”的人出列，數(shù)到“2”的立即站到隊(duì)伍的最右端。報(bào)數(shù)過程反復(fù)進(jìn)行，直到n個(gè)人都出列為止。要求給出他們的出列順序。Page

223.3案例解決

3.3.1用棧來解決迷宮問題【算法思路】用棧來解決迷宮問題，本質(zhì)上是一個(gè)深度優(yōu)先算法（在教材的樹和圖時(shí)將學(xué)到）。我們?cè)O(shè)置一個(gè)數(shù)組maze來表示迷宮，其中每個(gè)元素表示一個(gè)方塊的狀態(tài)，為0時(shí)表示對(duì)應(yīng)方塊是通道，為1時(shí)表示對(duì)應(yīng)方塊是墻，不可走。為了算法方便，在迷宮外圍加了一道圍墻。這樣，在不影響迷宮結(jié)構(gòu)的前提下，原數(shù)組中的每個(gè)方塊都有4個(gè)方向可判斷。本算法用到的數(shù)據(jù)結(jié)構(gòu)是順序棧存儲(chǔ)結(jié)構(gòu)，采用“窮舉求解”的方法，即從入口出發(fā)，順某一方向向前試探，若能走通，則繼續(xù)往前走，否則，原路退回，換一個(gè)方向再繼續(xù)試探，直至所有可能的通路都試探完為止。為了保證在任何位置上都能沿原路退回（稱為回溯），需要用一個(gè)后進(jìn)先出的棧來保存入口到當(dāng)前位置的路徑。Page

233.3.2用隊(duì)列來解決迷宮問題【算法思路】用隊(duì)列解決迷宮問題，本質(zhì)上是一個(gè)廣度優(yōu)先算法（在教材的樹和圖章節(jié)中將學(xué)到）。這里不能