第3章棧和隊列數據結構案例教程Page

2案例提出——迷宮問題迷宮問題是取自心理學的一個經典實驗。在該實驗中，把一只老鼠從一個無頂大盒子的門中放入，在盒子中設置了許多墻，對行進方向形成了多處阻擋。盒子僅有一個出口，在出口處放置以塊奶酪，吸引老鼠在迷宮中尋找道路以到達出口。對同一只老鼠重復進行上述實驗，一直到老鼠從入口走到出口，而不走錯一步。老鼠經過多次試驗最終學會走通迷宮的路線。設計一個計算機程序對任意設定的矩形迷宮如下圖所示，求出一條從入口到出口的通路，或得出沒有通路的結論。Page

33.2知識點學習

3.2.1棧棧是一種特殊的線性表，用途十分廣泛。將遞歸算法轉換成非遞歸算法時常常會用到棧，實現二叉樹的算法中也會使用棧。棧是一種只能在一端進行插入或刪除的線性表。表中允許進行插入、刪除操作的一端稱為棧頂（top），表的另一端稱為棧底（bottom）。當棧中沒有數據元素時，稱為空棧。棧的插入操作通常稱為進棧或入棧，棧的刪除操作通常稱為退棧或出棧。Page

43.2.1.2棧的順序存儲結構及其基本運算實現#defineMaxsize100;//最多元素個數typedefintElemType;//數據類型typedefstruct{ ElemTypeelem[MaxSize]; inttop; //棧頂指針}SqStack;//順序棧類型定義Page

5入棧

Page

63.2.1.3棧的鏈式存儲結構及其基本運算的實現Page

7（鏈棧中數據結點的類型LinkStack定義如下：typedefintElemType;typedefstructlinknode{ElemTypedata;//數據域structlinknode*next;//指針域}LinkStack;Page

83.2.1.4棧的應用舉例1、算術表達式的前綴與后綴表達（任何一個表達式都是由操作數、運算符或界限符組成的。在表達式求值問題中的操作數可以是常數、被說明為變量或常量的標識符、表達式；運算符指的是“+”、“-”、“*”、“/”；界限符指的是括號等字符。在本例中的表達式求值問題就是：對于一個包含“+”、“-”、“*”、“/”、正整數和圓括號的合法數學表達式，計算該表達式的運算結果。Page

9前綴轉后綴算法演示Page

10后綴轉前綴算法演示Page

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

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

133.2.2隊列隊列也具有廣泛的應用。特別是在操作系統資源分配和排隊論中大量地使用隊列。本節介紹隊列的定義、隊列的存儲結構和隊列的應用。Page

143.2.2.2隊列的順序存儲結構及其基本運算的實現順序隊列類型SqQueue定義如下：#defineMaxSize100typedefintElemType;typedefstruct{ElemTypeelem[MaxSize];intfront,rear;//隊首和隊尾指針}SqQueue;Page

15隊列操作Page

16循環隊列Page

17循環隊列滿和空指針判斷沖突Page

183.2.2.3隊列的鏈式存儲結構及其基本運算的實現隊列的鏈式存儲結構是僅在表頭刪除和表尾插入的單鏈表，因此一個棧隊列需要使用兩個指針：指向隊頭元素的隊首指針front和指向隊尾元素的隊尾指針rear。用于存儲隊列的單鏈表簡稱鏈隊。如圖3.11所示的鏈隊列。Page

19鏈隊中數據結點的類型QNode定義typedefintElemType;typedefstructqnode{ElemTypedata;structqnode*next;}QNode;//鏈隊數據結點類型定義Page

20一個鏈隊的動態變化過程Page

213.2.2.4隊列的應用舉例

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

223.3案例解決

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

233.3.2用隊列來解決迷宮問題【算法思路】用隊列解決迷宮問題，本質上是一個廣度優先算法（在教材的樹和圖章節中將學到）。這里不能