數(shù)據(jù)結(jié)構(gòu)第3-1章

1、 實驗安排實驗安排 時間：時間：8-158-15周周 單周：周四單周：周四 5 5、6 6節(jié)節(jié) 雙周：周二雙周：周二 5 5、6 6節(jié)節(jié) 地點：地點：1 1、2 2班班 軟軟419419 3 3、4 4班班 軟軟420420 第第3 3章章 棧和隊列棧和隊列 棧和隊列是兩種常用的線性結(jié)構(gòu)棧和隊列是兩種常用的線性結(jié)構(gòu) 【學(xué)習(xí)目標(biāo)】【學(xué)習(xí)目標(biāo)】 1. 1. 掌握棧和隊列這兩種抽象數(shù)據(jù)類型的特點，并能在掌握棧和隊列這兩種抽象數(shù)據(jù)類型的特點，并能在 相應(yīng)的應(yīng)用問題中正確選用它們。相應(yīng)的應(yīng)用問題中正確選用它們。 2. 2. 熟練掌握棧類型的兩種實現(xiàn)方法。熟練掌握棧類型的兩種實現(xiàn)方法。 3. 3. 熟練掌

2、握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法。熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法。 【重點和難點】【重點和難點】 棧和隊列是在程序設(shè)計中被廣泛使用的兩種線性數(shù)據(jù)棧和隊列是在程序設(shè)計中被廣泛使用的兩種線性數(shù)據(jù) 結(jié)構(gòu)，因此本章的學(xué)習(xí)重點在于掌握這兩種結(jié)構(gòu)的特點，結(jié)構(gòu)，因此本章的學(xué)習(xí)重點在于掌握這兩種結(jié)構(gòu)的特點， 以便能在應(yīng)用問題中正確使用。以便能在應(yīng)用問題中正確使用。 線性表線性表 棧棧 隊列隊列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in

3、棧和隊列是限定插入和刪除只能在表棧和隊列是限定插入和刪除只能在表 的的“端點端點”進(jìn)行的進(jìn)行的線性表線性表限定性數(shù)據(jù)限定性數(shù)據(jù) 結(jié)構(gòu)。結(jié)構(gòu)。 3.1 3.1 棧棧 3.2 3.2 隊列隊列 3.1 棧 3.1 3.1 棧棧 定義：定義：限定僅在限定僅在表尾表尾進(jìn)行插入或刪除操作的線性表進(jìn)行插入或刪除操作的線性表。 表尾表尾( (允許插入和刪除允許插入和刪除) )棧頂，表頭棧頂，表頭棧底棧底 特點：特點：后進(jìn)先出（后進(jìn)先出（LIFO） an a1 a2 . 棧底棧底 棧頂棧頂 . 出棧出棧 進(jìn)棧進(jìn)棧 棧棧s=(a1,a2,an) 3.1.1 3.1.1 棧的定義棧的定義 3.1 3.1 棧棧 棧

4、的抽象數(shù)據(jù)類型棧的抽象數(shù)據(jù)類型 ADT Stack 數(shù)據(jù)對象數(shù)據(jù)對象： D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系： R1 | ai-1, aiD, i=2,.,n 約定約定an 端為棧頂，端為棧頂，a1 端為棧底。端為棧底。 基本操作基本操作： ADT Stack 建棧、入棧、出棧、建棧、入棧、出棧、 讀棧頂元素、判斷讀棧頂元素、判斷 棧滿或棧空等。棧滿或棧空等。 3.1 3.1 棧棧 3.1.2 3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn) 順序棧順序棧：( (棧的順序存儲結(jié)構(gòu)棧的順序存儲結(jié)構(gòu)) )利用一組利用一組地址連續(xù)地址連續(xù)的的 存儲單元依次存放自

5、棧底到棧頂?shù)臄?shù)據(jù)元素。存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。 /- 棧的順序存儲表示棧的順序存儲表示 - typedef struct SElemType *base; /棧底指針即棧的基址棧底指針即棧的基址 SElemType *top; /指向棧頂元素的上一個位置指向棧頂元素的上一個位置 int stacksize; /棧的容量棧的容量( (已分配的存儲空間已分配的存儲空間) ) SqStack; 棧頂元素的說明棧頂元素的說明 3.1 3.1 棧棧 3.1.2 3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn) 如：如：SqStack s; s為一個順序棧的變量。為一個順序棧的變量。s的存儲空間為

6、：的存儲空間為： s.base s.top s. stacksize s.base0 s.basestacksize-1 該空間的申請由該空間的申請由 初始化初始化操作實現(xiàn)操作實現(xiàn) 3.1 3.1 棧棧 ?？粘鰲＃瑒t?？粘鰲?，則下溢下溢(underflow) 棧滿入棧，則棧滿入棧，則上溢上溢(overflow) 3.1.2 3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn) base 1 2 3 4 5 0 棧空?？?top 棧頂指針棧頂指針top初值指向初值指向 棧底：棧底：top=base 1 2 3 4 5 0 進(jìn)棧進(jìn)棧 baseA top B topC topD topE topF top 出棧

7、出棧 1 2 3 4 5 0A B C D E F base top top top top top top top top top top top top 棧滿棧滿:top- base = stacksize ?？諚？?top top top top top toptop *S.top+ = ee = *- S.top 3.1 3.1 棧棧 思考思考：如果進(jìn)棧順序為：如果進(jìn)棧順序為1，2，3，4。不限制出棧。不限制出棧 的時間，則下面哪一種出棧順序不可能。的時間，則下面哪一種出棧順序不可能。 (1) 1, 2, 3, 4 (2) 2, 1, 4, 3 (3) 3, 1, 2, 4 (4) 4

8、, 3, 2, 1 3.1.2 3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn) 3.1 3.1 棧棧 3.1.2 3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn) 棧的基本操作在棧的基本操作在順序棧順序棧中的實現(xiàn)中的實現(xiàn) InitStack( if (!S.base) exit (OVERFLOW); /存儲分配失敗存儲分配失敗 S.top = S.base; S.stacksize = STACK_INI_SIZE ; return OK; / InitStack 3.1 3.1 棧棧 3.1.2 3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn) 入棧入棧 算法描述：算法描述： Status Push (SqSt

9、ack return OK; /Push/Push e e插入后棧頂指針加插入后棧頂指針加1 1 if (S.top - S.base = S.stacksize) /棧滿棧滿, ,追加存儲空間追加存儲空間 S.base = (SElemType *)relloc(S.base , (STACK_INI_SIZE+STACKINCREMENT)* sizeof (SElemType); If(!S.base) exit(OVERFLOWOVERFLOW); /存儲分配失敗存儲分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT；

10、3.1 3.1 棧棧 3.1.2 3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn) 出棧出棧 算法描述：算法描述： Status Pop (SqStack /?？諚？?e = *-S.top; return OK; /Pop 棧頂指針減棧頂指針減1 1，取所指元素，取所指元素 3.1 3.1 棧棧 3.1.2 3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn) 取棧頂元素取棧頂元素 算法描述：算法描述： Status GetTop(SqStack S，SElemType /否則，返回否則，返回ERROR If(S.top=S.base) return Error; e= * (S.top-1) Return O

11、K; /GetPop 3.1 3.1 棧棧 鏈棧鏈棧(補(bǔ)充補(bǔ)充): 用鏈?zhǔn)浇Y(jié)構(gòu)來表示的棧就是用鏈?zhǔn)浇Y(jié)構(gòu)來表示的棧就是鏈棧鏈棧 (1)(1)鏈棧的構(gòu)造方式鏈棧的構(gòu)造方式: : 以頭指針為棧頂，以頭指針為棧頂，在頭指針處在頭指針處插入或刪除插入或刪除 nextdata an an-1 a1 a2 棧頂元素棧頂元素 棧底元素棧底元素 注意注意 指針指針 方向方向 通常鏈棧不設(shè)通常鏈棧不設(shè)頭結(jié)頭結(jié) 點點，因為棧頂，因為棧頂( (表表 頭）操作頻繁頭）操作頻繁 基本操作基本操作：p-data=e; p-next=top; top=p; 3.1 3.1 棧棧 鏈棧鏈棧(補(bǔ)充補(bǔ)充): v入棧：入棧： . 棧

12、底棧底 top e p top v出棧：出棧： 棧底棧底 . top q top 基本操作：基本操作：e=top-data; q=top; top=top-next; free(q); return(e); 3.1 3.1 棧棧 3.1.3 3.1.3 棧的應(yīng)用舉例棧的應(yīng)用舉例 例一：數(shù)制轉(zhuǎn)換例一：數(shù)制轉(zhuǎn)換 例二：括號匹配的檢驗例二：括號匹配的檢驗 例三：行編輯程序例三：行編輯程序 例四：迷宮求解例四：迷宮求解 例五：表達(dá)式求值例五：表達(dá)式求值 例六：漢諾塔問題例六：漢諾塔問題* 設(shè)計思路：設(shè)計思路： 用棧暫存低位值用棧暫存低位值 3.1 3.1 棧棧 例一：數(shù)制轉(zhuǎn)換例一：數(shù)制轉(zhuǎn)換 算法基于原

13、理：算法基于原理： N = (N div d)d + N mod d 求商求商 求余求余進(jìn)制進(jìn)制 例如：例如：（1348)10 = (2504)8 ，其運算過程如下，其運算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 計算順序計算順序 輸出順序輸出順序 3.1 3.1 棧棧 算法描述：算法描述： void conversion () /對于輸入的十進(jìn)制非負(fù)整數(shù)，輸出對應(yīng)的八進(jìn)制數(shù)對于輸入的十進(jìn)制非負(fù)整數(shù)，輸出對應(yīng)的八進(jìn)制數(shù) InitStack(S); /構(gòu)造空棧構(gòu)造空棧S scanf (%d,N); while (N) Pus

14、h(S, N % 8); /入棧入棧 N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( “%d”, e ); /出棧出棧 / conversion 例一：數(shù)制轉(zhuǎn)換例一：數(shù)制轉(zhuǎn)換 3.1 3.1 棧棧 例二：括號匹配的檢驗例二：括號匹配的檢驗 假設(shè)在表達(dá)式中假設(shè)在表達(dá)式中 （）或（）或（ ） 等為等為正確正確的格式，的格式， （ ）或（）或（ ）或）或 ( ) 均為均為不正確不正確的格式。的格式。 則則 檢驗括號是否匹配檢驗括號是否匹配的方法可用的方法可用“期待的期待的 急迫程度急迫程度”這個概念來描述。這個概念來描述。 “期待的急迫程度期待的急

15、迫程度” :” :即后出現(xiàn)的即后出現(xiàn)的“左括弧左括弧”， 它等待與其匹配的它等待與其匹配的“右括弧右括弧”出現(xiàn)的出現(xiàn)的“急迫急迫” 心情要比先出現(xiàn)的左括弧高。換句話說，對心情要比先出現(xiàn)的左括弧高。換句話說，對 “左括弧左括弧”來說，后出現(xiàn)的比先出現(xiàn)的來說，后出現(xiàn)的比先出現(xiàn)的“優(yōu)先優(yōu)先” 等待檢驗，對等待檢驗，對“右括弧右括弧”來說，每個出現(xiàn)的右來說，每個出現(xiàn)的右 括弧要去找在它之前括弧要去找在它之前“最后最后”出現(xiàn)的那個左括出現(xiàn)的那個左括 弧去匹配。弧去匹配。 顯然，必須將先后出現(xiàn)的左括弧依次保存，為顯然，必須將先后出現(xiàn)的左括弧依次保存，為 了了反映這個優(yōu)先程度反映這個優(yōu)先程度，保存左括弧的結(jié)

16、構(gòu)用棧，保存左括弧的結(jié)構(gòu)用棧 最合適。這樣對出現(xiàn)的右括弧來說，只要最合適。這樣對出現(xiàn)的右括弧來說，只要“棧棧 頂元素頂元素”相匹配即可。如果在棧頂?shù)哪莻€左括相匹配即可。如果在棧頂?shù)哪莻€左括 弧正好和它匹配，就可將它從棧頂刪除?；≌煤退ヅ?，就可將它從棧頂刪除。 3.1 3.1 棧棧 3.1 3.1 棧棧 例二：括號匹配的檢驗例二：括號匹配的檢驗 例如：考慮下列括號序列：例如：考慮下列括號序列： ( ) 1 2 3 4 5 6 7 8 分析：分析：當(dāng)接受了第一個括號當(dāng)接受了第一個括號“”“”后，期待與其匹配的第八后，期待與其匹配的第八 個個 出現(xiàn)，而等來的確是第二個出現(xiàn)，而等來的確是第二個“（

17、”，此時，第二個括號期待，此時，第二個括號期待 匹匹 配的程度高于第一個，第一個配的程度高于第一個，第一個“”“”只能放一邊；而迫切等只能放一邊；而迫切等 待待 與第二個括號相匹配的、第七個括號與第二個括號相匹配的、第七個括號“）”的出現(xiàn)，可等來的出現(xiàn)，可等來 的的 是第三個括是號是第三個括是號“”“”，因而，其期待匹配程度高于第二個，因而，其期待匹配程度高于第二個 ， 第二個括號讓位于第三個；直到第四個括號第二個括號讓位于第三個；直到第四個括號“”“”出現(xiàn)，第出現(xiàn)，第 三三 個括號期待得到滿足，消解之后，第二個括號期待匹配成個括號期待得到滿足，消解之后，第二個括號期待匹配成 了最急迫的任務(wù)了

18、最急迫的任務(wù) 設(shè)計思路：設(shè)計思路： 用棧暫存左括號用棧暫存左括號 3.1 3.1 棧棧 例二：括號匹配的檢驗例二：括號匹配的檢驗 算法的設(shè)計思想：算法的設(shè)計思想： 1. 1. 出現(xiàn)的凡是出現(xiàn)的凡是“左括號左括號”，則，則進(jìn)棧進(jìn)棧； 2. 2. 出現(xiàn)的是出現(xiàn)的是“右括號右括號”， 首先檢查棧是否空？首先檢查棧是否空？ 若若棧空棧空，則表明該，則表明該“右括右括號號”多余多余 否則否則和棧頂元素和棧頂元素比較？比較？ 若若相匹配相匹配，則棧頂則棧頂“左括號出棧左括號出棧” 否則表明否則表明不匹配不匹配 3.3.表達(dá)式表達(dá)式檢驗結(jié)束檢驗結(jié)束時，時， 若若?？諚？眨瑒t表明表達(dá)式中，則表明表達(dá)式中匹配正

19、確匹配正確 否則表明否則表明“左括號左括號”有余有余 3.1 3.1 棧棧 例二：括號匹配的檢驗例二：括號匹配的檢驗 算法描述算法描述 （作（作 業(yè)）業(yè)） 3.1 3.1 棧棧 例三：行編輯程序例三：行編輯程序 “每接受一個字符即存入存儲器每接受一個字符即存入存儲器” ” ? ? 并不恰當(dāng)！并不恰當(dāng)！ 在用戶輸入一行的過程中，允許用戶輸入出差錯，在用戶輸入一行的過程中，允許用戶輸入出差錯， 并在發(fā)現(xiàn)有誤時可以并在發(fā)現(xiàn)有誤時可以及時更正及時更正。 合理的作法是：合理的作法是： 設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一一 行行字符，然后逐行存入用戶數(shù)據(jù)區(qū)字符，

20、然后逐行存入用戶數(shù)據(jù)區(qū); 并假設(shè)并假設(shè)“#”為為 退格符，退格符，“”為退行符為退行符。 3.1 3.1 棧棧 例三：行編輯程序例三：行編輯程序 假設(shè)從終端接受了這樣兩行字符：假設(shè)從終端接受了這樣兩行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+); 則實際有效的是下列兩行：則實際有效的是下列兩行： while (*s) putchar(*s+); 3.1 3.1 棧棧 例三：行編輯程序例三：行編輯程序 while (ch != EOF) /EOF為全文結(jié)束符為全文結(jié)束符 while (ch != n) /判斷是否換行判斷是否換行 switch (ch) ca

21、se # : Pop(S, c); break; case : ClearStack(S); break;/ 重置重置S為空棧為空棧 default : Push(S, ch); break; ch = getchar(); / 從終端接收下一個字符從終端接收下一個字符 將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)； ClearStack(S); / 重置重置S為空棧為空棧 if (ch != EOF) ch = getchar(); 3.1 3.1 棧棧 例四：迷宮求解例四：迷宮求解(窮舉求解窮舉求解) # # #$# # #$# # $ $# #

22、# # # # # # # # # # 出口出口 入口入口 1-東 2-南 3-西 4-北 # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 1 1 1 1 2 2 2 2 2 3 2 1 3 3 1 3 4 4 2 4 1 2 5 1 2 6 4 1 6 3 1 5 3 1 4 4 3 $ $ $ 藍(lán)-坐標(biāo)，紅-方向 3.1 3.1 棧棧 例四：迷宮求解例四：迷宮求解 算法的基本思想是：算法的基本思想是： 若當(dāng)前位置若當(dāng)

23、前位置“可通可通”，則納入路徑，繼，則納入路徑，繼 續(xù)前進(jìn)續(xù)前進(jìn); 若當(dāng)前位置若當(dāng)前位置“不可通不可通”，則后退，換方，則后退，換方 向繼續(xù)探索向繼續(xù)探索; 若四周若四周“均無通路均無通路”，則將當(dāng)前位置從，則將當(dāng)前位置從 路徑中刪除出去。路徑中刪除出去。 3.1 3.1 棧棧 例四：迷宮求解例四：迷宮求解 設(shè)定當(dāng)前位置的初值為入口位置；設(shè)定當(dāng)前位置的初值為入口位置； do 若若當(dāng)前位置可通當(dāng)前位置可通， 則則將當(dāng)前位置將當(dāng)前位置插入棧頂插入棧頂； 若若該位置是出口位置，該位置是出口位置，則則算法結(jié)束；算法結(jié)束； 否則切換否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；當(dāng)前位置的東鄰方塊為新的當(dāng)前位

24、置； 否則否則 while (棧不空）棧不空）； 3.1 3.1 棧棧 例四：迷宮求解例四：迷宮求解 若若棧不空且棧頂位置尚有其他方向未被探索，棧不空且棧頂位置尚有其他方向未被探索， 則則設(shè)定新的當(dāng)前位置為設(shè)定新的當(dāng)前位置為: 沿順時針方向旋轉(zhuǎn)沿順時針方向旋轉(zhuǎn) 找到的找到的棧頂位置的下一相鄰塊；棧頂位置的下一相鄰塊； 若若棧不空但棧頂位置的四周均不可通，棧不空但棧頂位置的四周均不可通， 則則刪去棧頂位置；刪去棧頂位置；/ / 從路徑中刪去該通道塊從路徑中刪去該通道塊 若若棧不空，棧不空，則則重新測試新的棧頂位置，重新測試新的棧頂位置， 直至直至找到一個可通的相鄰塊或出棧至?？?；找到一個可通的相

25、鄰塊或出棧至?？?； 若若?？諚？眨瑒t表明迷宮沒有通路。，則表明迷宮沒有通路。 3.1 3.1 棧棧 例五：表達(dá)式求值例五：表達(dá)式求值 表達(dá)式求值表達(dá)式求值是棧應(yīng)用的典型例子是棧應(yīng)用的典型例子 (1)(1)表達(dá)式求值必須滿足算術(shù)四則運算規(guī)則：表達(dá)式求值必須滿足算術(shù)四則運算規(guī)則： a. a. 先乘除，后加減先乘除，后加減 b. b. 從左算到右從左算到右 c. c. 先括號內(nèi)，后括號外先括號內(nèi)，后括號外 (2)(2)任何一個表達(dá)式由：任何一個表達(dá)式由：操作數(shù)、運算符、界限符操作數(shù)、運算符、界限符 組成組成 (3)(3)運算符和界限符統(tǒng)稱運算符和界限符統(tǒng)稱算符算符。 根據(jù)上面的運算規(guī)則，在運算的每一

26、步中，任意兩個根據(jù)上面的運算規(guī)則，在運算的每一步中，任意兩個 相繼出現(xiàn)的算符相繼出現(xiàn)的算符 1 1和和 2 2之間的優(yōu)先關(guān)系至多是下面之間的優(yōu)先關(guān)系至多是下面三三 種關(guān)系種關(guān)系之一：之一： 1 1 1 2 : 2 : 1 1的優(yōu)先權(quán)高于的優(yōu)先權(quán)高于 2 2 3.1 3.1 棧棧 例五：表達(dá)式求值例五：表達(dá)式求值（下表給出了算符之間的優(yōu)先級）（下表給出了算符之間的優(yōu)先級） v 由上表可看出，右括號由上表可看出，右括號 ) 和井號和井號 # 作為作為 2時時級別最級別最 低；低； v 由由c 規(guī)則規(guī)則得出：得出： * ，/， + ，-為為 1時的優(yōu)先權(quán)低于時的優(yōu)先權(quán)低于，高，高 于于 v 由由b

27、規(guī)則規(guī)則得出：得出： = 表明括號內(nèi)的運算已完成；表明括號內(nèi)的運算已完成； = 表明表達(dá)式求值完畢。表明表達(dá)式求值完畢。 + 2 1 - - * * / / ( ( ) ) # # + - + - * * / ( ) # / ( ) # = = = 3.1 3.1 棧棧 例五：表達(dá)式求值例五：表達(dá)式求值 為了實現(xiàn)為了實現(xiàn)算符優(yōu)先算法算符優(yōu)先算法，可以設(shè)定兩個工作棧：，可以設(shè)定兩個工作棧： 存放操作數(shù)或運算結(jié)果，存放操作數(shù)或運算結(jié)果， OPTR存放運算符號。存放運算符號。 算法思想：算法思想： 1 1）首先置）首先置為空棧，表達(dá)式的起始符為空棧，表達(dá)式的起始符# #為運算符棧為運算符棧 OPTR

28、的棧底元素；的棧底元素； 2 2）依次讀入表達(dá)式中的每個字符，）依次讀入表達(dá)式中的每個字符， 若運算符是若運算符是#或棧頂是或棧頂是#，結(jié)束計算，返回，結(jié)束計算，返回OPNDOPND棧頂值。棧頂值。 ifif（是操作數(shù)）是操作數(shù)） 則則PUSH（ ，操作數(shù)操作數(shù)）； ifif（是運算符）是運算符） 則與則與OPTR棧頂元素棧頂元素 1進(jìn)行比較，按優(yōu)先級進(jìn)行比較，按優(yōu)先級( (規(guī)定規(guī)定 詳見詳見P53P53表表3.13.1）進(jìn)行操作；）進(jìn)行操作； ifif棧頂元素棧頂元素 運算符運算符，則退棧、按棧頂計算，將結(jié)果壓入，則退棧、按棧頂計算，將結(jié)果壓入棧棧。 判判C C是否是否 操作符操作符 3.1

29、 3.1 棧棧 例五：表達(dá)式求值例五：表達(dá)式求值 算法描述：算法描述： Status EvaluateExpression( OperandType InitStack(OPTR);Push(OPTR ,#); =getchar(); while(c!=#) c=getchar(); else switch(precede(GetTop(OPTR) , c) case : Pop(OPTR ,theta); Pop(OPND,b);a=Pop(); thetabreak; /switch /while result=GetTop(OPND); /EvaluateExpression 運算符與棧

30、頂比運算符與棧頂比 較并查較并查3.13.1表表 3.1 3.1 棧棧 例五：表達(dá)式求值例五：表達(dá)式求值 例：對表達(dá)式例：對表達(dá)式3*（7 2 ）求值）求值 OPTROPNDINPUTOPERATE 3*(7-2)#Push(opnd,3) # *(7-2)#3#Push(optr,*) #,*3(7-2)#Push(optr,() #,*,(37-2)#Push(opnd,7) #,*,(3,7-2)#Push(optr,-) #,*,(,3,72)#Push(opnd,2) #,*,(,3,7,2)#Operate(7-2) #,*,(3,5)#Pop(optr) #,*3,5#Opera

31、te(3*5) #15#GetTop(opnd) 練習(xí)：練習(xí)： 3+4-(6-9/2)+7*5# (參照例參照例3-1) 3.1 3.1 棧棧 例六：漢諾塔問題例六：漢諾塔問題* 漢諾漢諾（ Hanoi）塔塔 傳說在創(chuàng)世紀(jì)時，在一個叫傳說在創(chuàng)世紀(jì)時，在一個叫Brahma的寺廟里，有三的寺廟里，有三 個柱子，其中一柱上有個柱子，其中一柱上有6464個盤子從小到大依次疊放，僧個盤子從小到大依次疊放，僧 侶的工作是將這侶的工作是將這6464個盤子從一根柱子移到另一個柱子上。個盤子從一根柱子移到另一個柱子上。 移動時的規(guī)則：移動時的規(guī)則： v 每次只能移動一個盤子；每次只能移動一個盤子； v 只能小盤

32、子在大盤子上面；只能小盤子在大盤子上面； v 可以使用任一柱子。可以使用任一柱子。 當(dāng)工作做完之后，就標(biāo)志著世界末日到來。當(dāng)工作做完之后，就標(biāo)志著世界末日到來。 x y zx y z n 1 n 3.1 3.1 棧棧 例六：漢諾塔問題例六：漢諾塔問題* 分析：分析： 設(shè)三根柱子分別為設(shè)三根柱子分別為 x, y, z , x, y, z , 盤子在盤子在 x x 柱上，要移柱上，要移 到到z z 柱上。柱上。 1 1、當(dāng)、當(dāng) n=1 n=1 時，盤子直接從時，盤子直接從 x x 柱移到柱移到 z z 柱上；柱上； 2 2、當(dāng)、當(dāng) n1 n1 時時, , 則則: : 設(shè)法將前設(shè)法將前 n 1 n

33、1 個盤子個盤子 從從 x x 移到移到 y y 柱上（借助柱上（借助z z），）， 則則 盤子盤子 n n 就能從就能從 x x 移到移到 z z 柱上；柱上； 再設(shè)法把再設(shè)法把n 1 n 1 個盤子個盤子 從從 y y 移到移到 z z 柱上柱上( (這又是一這又是一 個與原來相同的問題，只是規(guī)模少了）個與原來相同的問題，只是規(guī)模少了） 。 x y zx y z n 1 n 遞歸函數(shù)遞歸函數(shù)：一個直接調(diào)用自己或通過一系列：一個直接調(diào)用自己或通過一系列 的調(diào)用語句間接調(diào)用自己的函數(shù)的調(diào)用語句間接調(diào)用自己的函數(shù) 3.1 3.1 棧棧 例六：漢諾塔問題例六：漢諾塔問題* 算法描述：算法描述： Void Hanoi ( int n, char x, char y, char z ) 1 /將將n n個編號從上到下為個編號從上到下為1 1n n的盤子從的盤子從x x柱，借助柱，借助y y柱移到柱移到z z柱柱 2 if ( n = = 1 ) 3 move ( x , 1 , z ) ; /將編號為將編號為1 1的盤子從的盤子從x x柱移到柱移到