數(shù)據(jù)結(jié)構(gòu)-堆棧

1、第四章 堆棧和隊列提綱 4.1堆棧的概念及其運算 4.2堆棧的順序存儲結(jié)構(gòu) 4.3堆棧的鏈式存儲結(jié)構(gòu) 4.4堆棧的應(yīng)用14.1堆棧的概念及其運算堆棧的邏輯結(jié)構(gòu)堆棧：限定僅在表尾進行插入和刪除操作的線性表?？諚＃翰缓魏螖?shù)據(jù)元素的棧。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。（a1, a2, , an）棧頂棧底2abc入棧出棧棧底棧頂插入：入棧、進棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的示意圖4.1堆棧的概念及其運算棧的操作特性：后進先出34.1堆棧的概念及其運算例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂c棧頂 情況1：出棧序列

2、：c出棧序列：c、b出棧序列：c、b、a4例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂 情況2：出棧序列：b4.1堆棧的概念及其運算5棧底a出棧序列：b出棧序列：b、c出棧序列： b、 c、ac棧頂棧頂注意：棧只是對表插入和刪除操作的位置進行了限制，并沒有限定插入和刪除操作進行的時間。 情況2：例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？4.1堆棧的概念及其運算6堆棧的操作Push(S,x)Pop(S)Empty(S)Top(S)Create(S)4.1堆棧的概念及其運算7如何改

3、造數(shù)組實現(xiàn)棧的順序存儲？ 0 1 2 3 4 5 6 7 8a1確定用數(shù)組的哪一端表示棧底。附設(shè)指針top指示棧頂元素在數(shù)組中的位置。 top4.2堆棧的順序存儲結(jié)構(gòu)8出棧：top減1進棧：top加1?？眨簍op= -1 0 1 2 3 4 5 6 7 8a1topa2topa3top棧滿：top= MAX_SIZE4.2堆棧的順序存儲結(jié)構(gòu)9堆棧是否為空測試算法p70進棧算法p71退棧算法4.2堆棧的順序存儲結(jié)構(gòu)10解決方案1：直接解決：為每個棧開辟一個數(shù)組空間。 解決方案2：順序棧單向延伸使用一個數(shù)組來存儲兩個棧在一個程序中需要同時使用具有相同數(shù)據(jù)類型的兩個棧，如何順序存儲這兩個棧？會出現(xiàn)什

4、么問題？如何解決？4.2堆棧的順序存儲結(jié)構(gòu)11兩棧共享空間：使用一個數(shù)組來存儲兩個棧，讓一個棧的棧底為該數(shù)組的始端，另一個棧的棧底為該數(shù)組的末端，兩個棧從各自的端點向中間延伸。4.2堆棧的順序存儲結(jié)構(gòu)12棧1的底固定在下標為0的一端；棧2的底固定在下標為MaxSize-1的一端。 top1和top2分別為棧1和棧2的棧頂指針；MaxSize為整個數(shù)組空間的大?。▓D中用S表示）；a1 a2 aitop10 1 2 S-1top2bj b2 b1棧1底棧2底4.2堆棧的順序存儲結(jié)構(gòu)13top1= -1什么時候棧1為空？a1 a2 aitop10 1 2 S-1top2bj b2 b1top14.2

5、堆棧的順序存儲結(jié)構(gòu)14top1= -1什么時候棧1為空？a1 a2 aitop10 1 2 S-1top2bj b2 b1什么時候棧2為空？top2top2= MaxSize4.2堆棧的順序存儲結(jié)構(gòu)15top1= -1什么時候棧1為空？a1 a2 aitop10 1 2 S-1top2bj b2 b1什么時候棧2為空？top2= MaxSize什么時候棧滿？top2= top1+14.2堆棧的順序存儲結(jié)構(gòu)161. 如果棧滿，則拋出上溢異常；2. 判斷是插在棧1還是棧2； 2.1 若在棧1插入，則 2.1.1 top1加1; 2.1.2 在top1處填入x； 2.2 若在棧2插入，則 2.2.1

6、 top2減1; 2.2.2 在top2處填入x；操作接口：void Push(int i, T x) ;4.2堆棧的順序存儲結(jié)構(gòu)171. 若是在棧1刪除，則 1.1 若棧1為空棧，拋出下溢異常； 1.2 刪除并返回棧1的棧頂元素；2. 若是在棧2刪除，則 2.1 若棧2為空棧，拋出下溢異常； 2.2 刪除并返回棧2的棧頂元素；操作接口：T Pop(int i) ;4.2堆棧的順序存儲結(jié)構(gòu)18heada1a2anai鏈棧需要加頭結(jié)點嗎？如何改造鏈表實現(xiàn)棧的鏈接存儲？將哪一端作為棧頂？將鏈頭作為棧頂，方便操作。鏈棧不需要附設(shè)頭結(jié)點。4.3堆棧的鏈式存儲結(jié)構(gòu)19棧頂棧底鏈棧：棧的鏈接存儲結(jié)構(gòu)top

7、anan-1a1heada1a2anai兩種示意圖在內(nèi)存中對應(yīng)同一種狀態(tài)topa1an-1an棧頂棧底4.3堆棧的鏈式存儲結(jié)構(gòu)204.3堆棧的鏈式存儲結(jié)構(gòu) 入棧：p75 出棧：p75操作接口：214.3堆棧的鏈式存儲結(jié)構(gòu)順序棧和鏈棧的比較時間性能：相同，都是常數(shù)時間O(1)?？臻g性能：順序棧：有元素個數(shù)的限制和空間浪費的問題。鏈棧：沒有棧滿的問題，只有當內(nèi)存沒有可用空間時才會出現(xiàn)棧滿，但是每個元素都需要一個指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷?？傊?，當棧的使用過程中元素個數(shù)變化較大時，用鏈棧是適宜的，反之，應(yīng)該采用順序棧。221 遞歸的定義子程序（或函數(shù)）直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自己，

8、是一種描述問題和解決問題的基本方法。 2 遞歸的基本思想問題分解：把一個不能或不好解決的大問題轉(zhuǎn)化為一個或幾個小問題，再把這些小問題進一步分解成更小的小問題，直至每個小問題都可以直接解決。 4.4堆棧的應(yīng)用遞歸233 遞歸的要素遞歸邊界條件：確定遞歸到何時終止，也稱為遞歸出口；遞歸模式：大問題是如何分解為小問題的，也稱為遞歸體。 4.4堆棧的應(yīng)用遞歸244.4堆棧的應(yīng)用遞歸遞歸算法int fact ( int n ) if ( n = 0 ) return 1; else return n * fact (n-1);-*=時當時當)!1(1!n1n1nnn例1 階乘函數(shù)254.4堆棧的應(yīng)用遞歸

9、遞歸的經(jīng)典問題漢諾塔問題 在世界剛被創(chuàng)建的時候有一座鉆石寶塔（塔A），其上有64個金碟。所有碟子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩個鉆石寶塔（塔B和塔C）。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔A上的碟子移動到塔C上去，其間借助于塔B的幫助。每次只能移動一個碟子，任何時候都不能把一個碟子放在比它小的碟子上面。當牧師們完成任務(wù)時，世界末日也就到了。264.4堆棧的應(yīng)用遞歸漢諾塔問題的遞歸求解:如果 n = 1，則將這一個盤子直接從 塔A移到塔 C 上。否則，執(zhí)行以下三步： 將塔A上的n-1個碟子借助塔C先移到塔B上； 把塔A上剩下的一個碟子移到塔C上； 將n-1個碟

10、子從塔B借助于塔A移到塔C上。 274.4堆棧的應(yīng)用遞歸284.4堆棧的應(yīng)用遞歸 void Hanoi(int n, char A, char B, char C) if (n=1) Move(A, C); else Hanoi(n-1, A, C, B); Move(A, C); Hanoi(n-1, B, A, C); 294.4堆棧的應(yīng)用遞歸遞歸函數(shù)的內(nèi)部執(zhí)行過程 運行開始時，首先為遞歸調(diào)用建立一個工作棧，其結(jié)構(gòu)包括值參、局部變量和返回地址； 每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當前值以及調(diào)用后的返回地址壓棧； 每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)

11、為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。30Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move (A,C)Move (A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move (C,B)Hanio(1,C,A,B)Move (A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move (B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move (A,C)Hanio(2,B,A,C)Move (B,A)Hanio(1,A,B,C)結(jié)束314.4堆棧的應(yīng)用表達式求值中綴表達

12、式后綴表達式后綴表達式特點后綴表達式中不出現(xiàn)括號后綴表達式與中綴表達式的運算對象的先后次序相同，只是所讀到的運算符的先后次序可能有所改變324.4堆棧的應(yīng)用表達式求值后綴表達式實例ABCE/-E*+ 對應(yīng)中綴表達式 A+(B-C/D)*E(2)ABCD/F*-E*+X+對應(yīng)中綴表達式A+(B-C/D*F)*E+X334.4堆棧的應(yīng)用后綴表達式求值后綴表達式計算算法：Procedure EVAL(E) /E為后綴表達式top0loopx NEXT_TOKEN(E)case:x=“#”:return:x=運算對象:call PUSH(STACK,M,top,x):else: 從堆棧中取出相應(yīng)的運算

13、對象進行由x執(zhí)行的運算并將結(jié)果入棧endforeverend344.4堆棧的應(yīng)用中綴表達式轉(zhuǎn)換算法思想p81-82關(guān)鍵點：運算符堆棧運算符優(yōu)先關(guān)系表354.4堆棧的應(yīng)用中綴表達式轉(zhuǎn)換運算優(yōu)先級當前運算符棧頂運算符364.4堆棧的應(yīng)用中綴表達式轉(zhuǎn)換算法： /將中綴表達式E轉(zhuǎn)換為后綴表達式Procedure POSTFIX(E)STACK1=“#”top1loopx NEXT_TOKEN(E)case:x=“#”:while top1 doprint(STACKtop) /輸出棧頂運算符call POP(STATCK,top) /退棧endprint(“#”);return:x是運算對象:print(x)/直接輸出運算對象endforeverend374.4堆棧的應(yīng)用中綴表達式轉(zhuǎn)換:x=“）”