數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用本

1、第三章 棧的應(yīng)用數(shù)制轉(zhuǎn)換“除基取余法除基取余法”算法基于原理算法基于原理除以基數(shù)取余數(shù)，逆序排列。除以基數(shù)取余數(shù)，逆序排列。例如：例如：（1348)10 = (2504)8 ，其運算過程如下： N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2計算順序計算順序輸出順序輸出順序進制轉(zhuǎn)換算法思想1.1.初始化一個空棧初始化一個空棧S S；2.2.當十進制數(shù)當十進制數(shù)N N非零時，循環(huán)執(zhí)行以下操作：非零時，循環(huán)執(zhí)行以下操作：把把N N與與8 8求余得到的八進制數(shù)壓入棧求余得到的八進制數(shù)壓入棧S S；N N更更新為新為N N與與8 8的商。的商。3.3.

2、當棧當棧S S非空時，循環(huán)執(zhí)行以下操作：非空時，循環(huán)執(zhí)行以下操作：彈出棧頂元素彈出棧頂元素e e，然后輸出，然后輸出e e。void conversion () InitStack(S); scanf (%d,&N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion余數(shù)入棧余數(shù)入棧余數(shù)出棧余數(shù)出棧括號匹配括號匹配問題括號匹配問題1.括號匹配括號匹配 ( ) , ( ( ) ), ( )2.括號不匹配括號不匹配 ( ), ( ( ) ), (

3、 ( ) )檢驗括號匹配的方法：檢驗括號匹配的方法：“期待的急迫程度期待的急迫程度”檢查括號匹配算法的設(shè)計思想檢查括號匹配算法的設(shè)計思想設(shè)一棧；設(shè)一棧；遇到左括號則入棧；遇到左括號則入棧；遇到右括號時，若棧空，則不匹配遇到右括號時，若?？?，則不匹配( (右括右括號太多號太多) )，否則，如果棧頂元素與該右括，否則，如果棧頂元素與該右括號匹配，則出棧，否則不匹配號匹配，則出棧，否則不匹配( (括號不配括號不配對對) )。輸入結(jié)束后，若棧為空，則匹配，否則輸入結(jié)束后，若棧為空，則匹配，否則不匹配不匹配( (左括號太多左括號太多) )。Status Matching()int state = 1;I

4、nitStack(S);ch=getchar();while (ch!=# & state) switch(ch) case (|:Push(S, ch); break; case ): if(!StackEmpty(S)&GetTop(S)=() Pop(S,e); else state = 0; break; case : if( !StackEmpty(S)&GetTop(S) =) Pop(S,e); else state = 0; break; ch=getchar(); if (StackEmpty(S)&state) return OK; else

5、 return ERROR;行編輯程序出現(xiàn)的問題出現(xiàn)的問題每接受一個字符立即存入存儲器嗎？每接受一個字符立即存入存儲器嗎？NONO合理的做法合理的做法設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一行設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)“#”#”為退格符，為退格符，“”為退行符。為退行符。用戶輸入用戶輸入緩存區(qū)緩存區(qū)（用棧模擬）用戶數(shù)據(jù)區(qū)用戶數(shù)據(jù)區(qū)入棧入棧出棧出棧假設(shè)從終端接受了這樣兩行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);則實際有效的是下列兩行： while (*s) putc

6、har(*s+);行編輯程序算法的設(shè)計思想行編輯程序算法的設(shè)計思想設(shè)一棧（輸入緩沖區(qū)）；設(shè)一棧（輸入緩沖區(qū)）；讀入的字符為退格符，則刪除棧頂字符；讀入的字符為退格符，則刪除棧頂字符；讀入的字符為退行符，則清空棧；讀入的字符為退行符，則清空棧；否則，讀入的字符入棧。否則，讀入的字符入棧。每處理完一行字符，將棧底到棧頂?shù)淖址刻幚硗暌恍凶址?，將棧底到棧頂?shù)淖址嫒氪鎯ζ鳎蹇諚?，開始進行下一行的存入存儲器，清空棧，開始進行下一行的字符處理，直到文件結(jié)束。字符處理，直到文件結(jié)束。void LineEdit()InitStack(S); /緩存棧Sch=getchar();while (ch != E

7、OF) /EOF為全文結(jié)束符 while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break;/ 重置S為空棧 case : ClearStack(S); break; default : Push(S, ch); break; ch = getchar(); / 接收本行下一個字符 將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；可以借助另一個輔助棧來完成可以借助另一個輔助棧來完成InitStack(S2);. /輔助棧S2while(!EmptyStack(S) /從S棧出來

8、，進入S2Pop(S,e);Push(S2,e);while(!EmptyStack(S2)Pop(S2,e);將e寫入用戶數(shù)據(jù)區(qū)ClearStack(S); ClearStack(S2);if (ch != EOF) ch = getchar(); /讀取下一行字符 DestroyStack(S); DestroyStack(S2);（算術(shù)）表達式求值算術(shù)表達式的組成算術(shù)表達式的組成操作數(shù)操作數(shù)（運算對象或運算量）運算符運算符界限符界限符（如圓括號，作用是改變運算次序）常量、變量、常量、變量、函數(shù)、表達式函數(shù)、表達式單目、雙單目、雙目目以+ +、- -、* *、/ /四種運算為例算術(shù)表達式的

9、分類算術(shù)表達式的分類根據(jù)運算符在表達式中的不同位置中綴表達式 后綴表達式 前綴表達式 例：表達式例：表達式3 * ( 5 2 )3 * ( 5 2 )3 5 2 - * 3 5 2操作數(shù)之間的相對操作數(shù)之間的相對次序不變；次序不變；運算符的相對次序運算符的相對次序可能不同；可能不同；中綴式必須有括號信息，否則運算中綴式必須有括號信息，否則運算順序改變；順序改變；前綴式：無括號；連續(xù)出現(xiàn)的兩個操作數(shù)和在它前綴式：無括號；連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前出現(xiàn)且緊靠它們的運算符構(gòu)成了一個們之前出現(xiàn)且緊靠它們的運算符構(gòu)成了一個最小最小表達式；表達式；后綴式：無括號；運算符的排列順序就是計算順后綴式：無

10、括號；運算符的排列順序就是計算順序，每個運算符加上在它之前且緊靠它的兩個操序，每個運算符加上在它之前且緊靠它的兩個操作數(shù)構(gòu)成了一個最小表達式。作數(shù)構(gòu)成了一個最小表達式。三種表達式的特點三種表達式的特點中綴表達式求值設(shè)置兩個工作棧：設(shè)置兩個工作棧：運算符棧運算符棧S1S1和和操作數(shù)棧操作數(shù)棧S2S2。S2S2也放表達也放表達式的運算結(jié)果。式的運算結(jié)果。算法思想算法思想1 1 、首先置、首先置操作數(shù)棧操作數(shù)棧S2S2為空棧，置運算符棧為空棧，置運算符棧S1S1的棧底為表達的棧底為表達式的起始符式的起始符 # (# (優(yōu)先級最低優(yōu)先級最低) )。 2 2 、依次讀入表達式、依次讀入表達式中的每個字符

11、中的每個字符chch，直至表達式結(jié)束：，直至表達式結(jié)束： w 若若chch是是操作數(shù)操作數(shù), ,則進則進S2S2棧；棧； w 若若chch是運算符，若其優(yōu)先級不高于是運算符，若其優(yōu)先級不高于S1S1棧頂運算符棧頂運算符的優(yōu)先級時，則取出棧的優(yōu)先級時，則取出棧S2S2的棧頂和次棧頂?shù)膬蓚€元素以及的棧頂和次棧頂?shù)膬蓚€元素以及棧棧S1S1的棧頂運算符，進行相應(yīng)的運算，并將結(jié)果放入棧的棧頂運算符，進行相應(yīng)的運算，并將結(jié)果放入棧S2S2中；中；w 如此下去，直至如此下去，直至chch的優(yōu)先級高于的優(yōu)先級高于S1S1棧頂運算符的優(yōu)先級，棧頂運算符的優(yōu)先級，將將chch入入S1S1棧。棧。OperandTy

12、pe EvaluateExpression( ) InitStack(S1); Push(S1, #); InitStack(S2);c=getchar(); while (c!=#|GetTop(S1)!=#) if (!In(c, OP) Push(S2,c) ;c=getchar(); else / while return GetTop(S2); / EvaluateExpression switch (Precede(GetTop(S1),c) case : Pop(S1, op); Pop(S2, b); Pop(S2, a); Push(S2,Operate(a,op,b); b

13、reak; / switch舉例舉例: 3*(5-2) 步驟步驟 optroptr棧棧S1 S1 opndopnd棧棧 S2 S2 輸入字符輸入字符chch 主要操作主要操作 1 # 3*(5-2)# push(s2,3) 2 # 3 *(5-2)# push(s1,*) 3 #* 3 (5-2)# push(s1,() 4 #*( 3 5-2)# push(s2,5) 5 #*( 35 -2)# push(s1,-) 6 #*(- 35 2)# push(s2,2) 7 #*(- 352 )# operate(5,-,2 ) 8 #*( 33 )# pop(s1)消除一對括號 9 #* 33

14、 # operate(3,*,3 ) 10 # 9 # return(gettop(s2)后綴表達式求值1.運算符已經(jīng)按計算順序從左到右排好；2.沒有括號算法思想算法思想p設(shè)一棧設(shè)一棧存放操作數(shù)；存放操作數(shù)；p遇到操作數(shù)直接入棧；遇到操作數(shù)直接入棧；p遇到運算符，則取出棧頂?shù)膬蓚€數(shù)進行運遇到運算符，則取出棧頂?shù)膬蓚€數(shù)進行運算，將結(jié)果算，將結(jié)果入棧；入棧；p最終結(jié)果保存在最終結(jié)果保存在棧中（棧中唯一元素）。棧中（棧中唯一元素）。int Postfix ( )InitStack(S);/操作數(shù)棧c=getchar();while ( c != # ) if( isdigit(c) ) /操作數(shù)入棧

15、Push(S,c); else Pop(S,b); Pop(S,a);Push(S, Operate(a,c,b);c=getchar();Pop(S,result);return result;后綴表達式求值：后綴表達式求值：8 3 5 +5 6 2 / - *- #883835+83+5=8888562/6/2=38853-885-3=22*88*2=1616-8-16=-8-8棧與遞歸1.1.函數(shù)調(diào)用與返回的過程函數(shù)調(diào)用與返回的過程2.2.遞歸函數(shù)遞歸函數(shù)3.3.遞歸的設(shè)計原則遞歸的設(shè)計原則4.4.遞歸的優(yōu)點和缺點遞歸的優(yōu)點和缺點5.5.消除遞歸消除遞歸函數(shù)調(diào)用與返回的過程函數(shù)調(diào)用函數(shù)調(diào)

16、用當在一個函數(shù)的運行期間當在一個函數(shù)的運行期間調(diào)用另一個函數(shù)調(diào)用另一個函數(shù)時，在時，在運行被調(diào)用函數(shù)之前，需先完成三項任務(wù)：運行被調(diào)用函數(shù)之前，需先完成三項任務(wù)：1.1.將所有的實在參數(shù)、返回地址等將所有的實在參數(shù)、返回地址等信息信息傳遞給被傳遞給被調(diào)用函數(shù)調(diào)用函數(shù)保存保存；2.2.為被調(diào)用函數(shù)的局部變量為被調(diào)用函數(shù)的局部變量分配存儲區(qū)分配存儲區(qū)；3.3.將將控制轉(zhuǎn)移控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。到被調(diào)用函數(shù)的入口。函數(shù)調(diào)用與返回的過程函數(shù)返回函數(shù)返回從被調(diào)用函數(shù)從被調(diào)用函數(shù)返回返回調(diào)用函數(shù)調(diào)用函數(shù)之前之前，應(yīng)該完成下列，應(yīng)該完成下列三項任務(wù)：三項任務(wù)：1.1.保存保存被調(diào)函數(shù)的被調(diào)函數(shù)的計算結(jié)

17、果計算結(jié)果；2.2.釋放釋放被調(diào)函數(shù)的被調(diào)函數(shù)的數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)；3.3.依照被調(diào)函數(shù)保存的返回地址將依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移控制轉(zhuǎn)移到調(diào)到調(diào)用函數(shù)。用函數(shù)。函數(shù)函數(shù)嵌套調(diào)用嵌套調(diào)用時，時，后調(diào)用后調(diào)用的函數(shù)的函數(shù)先返回先返回。遞歸函數(shù)遞歸的定義遞歸的定義函數(shù)函數(shù)直接或間接直接或間接調(diào)用自身，稱為遞歸調(diào)用自身，稱為遞歸。(Recursion)(Recursion)遞歸的應(yīng)用遞歸的應(yīng)用1.1.問題具有遞歸的數(shù)學(xué)定義問題具有遞歸的數(shù)學(xué)定義2.2.使用了遞歸的數(shù)據(jù)結(jié)構(gòu)使用了遞歸的數(shù)據(jù)結(jié)構(gòu)3.3.問題存在遞歸的解決方法問題存在遞歸的解決方法 階乘階乘n!n!、FibonacciFibonacc

18、i數(shù)列數(shù)列 鏈表、二叉樹鏈表、二叉樹 HanoiHanoi塔問題塔問題遞歸過程的應(yīng)用（1）問題的數(shù)學(xué)定義是遞歸的問題的數(shù)學(xué)定義是遞歸的例例1 1：求：求n n的階乘的階乘n n！long Fact(int n) if (n=0) return(1); else return ( n*Fact(n-1) ); 求階乘(n!)過程的模擬n=3 n=3 fac(3)fac(3)n=2 n=2 F=3F=3* *fac(2)fac(2)n=1 n=1 F=2F=2* *fac(1)fac(1)n=0 n=0 F=1F=1* *fac(0)fac(0)fac(0)fac(0)return fac(3)=

19、3*2*1return fac(2)=2*1return fac(1)=1*1return fac(0)=1這種分解這種分解- -求解的策略叫求解的策略叫“分治法分治法”采用采用“分治法分治法”進行遞歸求解的問題需進行遞歸求解的問題需要滿足以下三個條件：要滿足以下三個條件：1.1.能將一個問題轉(zhuǎn)變成一個新問題，而新問題與能將一個問題轉(zhuǎn)變成一個新問題，而新問題與原問題的解法相同或類同，不同的僅是處理的原問題的解法相同或類同，不同的僅是處理的對象，并且這些處理對象更小且變化有規(guī)律。對象，并且這些處理對象更小且變化有規(guī)律。2.2.可以通過上述轉(zhuǎn)化而使問題簡化。可以通過上述轉(zhuǎn)化而使問題簡化。3.3.必

20、須有一個明確的遞歸出口，或成遞歸的邊界。必須有一個明確的遞歸出口，或成遞歸的邊界。void p(參數(shù)表)if(遞歸結(jié)束條件成立)可直接求解；elsep(較小的參數(shù));遞歸過程的應(yīng)用（1）問題的數(shù)學(xué)定義是遞歸的問題的數(shù)學(xué)定義是遞歸的例例2 2：計算：計算FibonacciFibonacci數(shù)列：數(shù)列：0,1,1,2,3,5,8,13,21,0,1,1,2,3,5,8,13,21,long Fib ( int n ) if ( n=1 ) return 0; if ( n=2 ) return 1; return Fib(n-1) + Fib(n-2);遞歸過程的應(yīng)用（2）數(shù)據(jù)結(jié)構(gòu)是遞歸的數(shù)據(jù)結(jié)構(gòu)

21、是遞歸的例例1 1：逆序打印鏈表中各結(jié)點的值 LL-nextvoid PrintLinkList ( LinkList L ) if ( L-next != NULL ) PrintLinkList (L-next); printf (L-next-data); 逆序打印逆序打印帶頭帶頭結(jié)點的單鏈表結(jié)點的單鏈表L!=NULL) L-data ) ;逆序打印不帶頭結(jié)點的單鏈表遞歸過程的應(yīng)用（2）數(shù)據(jù)結(jié)構(gòu)是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的例例2 2：順序打印鏈表中各結(jié)點的值 LL-nextvoid PrintLinkList ( LinkList L ) if ( L-next != NULL ) prin

22、tf (L-next-data); PrintLinkList (L-next); 順序打印帶頭順序打印帶頭結(jié)點的單鏈表結(jié)點的單鏈表遞歸過程的應(yīng)用（3）問題存在遞歸的解決方法問題存在遞歸的解決方法例例1 1：Hanoi塔問題n n階階HanoiHanoi塔問題塔問題：假設(shè)有三個分別命名為X,Y,Z的塔座，在X塔座上插有n個直徑大小各不相同，依小到大編號為1，2，,n的圓盤，要求：把X上的n個圓盤移到Z上，排列順序相同，移動規(guī)則為：1.1.每次只能移動一個圓盤；每次只能移動一個圓盤； 2.2.圓盤可以在任一塔上做多次移動；圓盤可以在任一塔上做多次移動； 3.3.在任何時刻，大盤不能壓在小盤的上面

23、。在任何時刻，大盤不能壓在小盤的上面。XYZ問題存在遞歸的解決方法 Hanoi (n, x, y, z)表示解決n個盤子的漢諾塔問題（從x搬到z，可以借助y）。解決方法：解決方法：若若n=1，直接將盤子，直接將盤子從從x搬到搬到z即即可；可；否則，可以分解為如下步驟：否則，可以分解為如下步驟：Hanoi ( n-1, x, z, y )Hanoi ( n-1, x, z, y )move ( n, x, z )move ( n, x, z )Hanoi ( n-1, y, x, z )Hanoi ( n-1, y, x, z )Hanoi算法實現(xiàn)void void HanoiHanoi ( i

24、nt ( int n n, char , char x x, char , char y y, char , char z z) ) if ( n=1 ) if ( n=1 ) move ( n, x, z ); move ( n, x, z ); else else Hanoi Hanoi ( n-1, x, z, y ); ( n-1, x, z, y ); move ( n, x, z ); move ( n, x, z ); HanoiHanoi ( n-1, y, x, z ); ( n-1, y, x, z ); 123465789 演示Hanoi塔中遞歸工作棧變化過程0 3 a

25、b c返址 n x y z6 2 a c b6 1 a b c acabcb8 1 c a b ac6 1 b c aba bc8 1 a b cac 8 2 b a c 遞歸工作遞歸工作棧棧遞歸過程執(zhí)行過程中占用的數(shù)據(jù)區(qū)遞歸的設(shè)計原則如果遞歸設(shè)計不當如果遞歸設(shè)計不當.容易造成容易造成無窮遞歸無窮遞歸，最，最終會耗盡應(yīng)用程序的棧終會耗盡應(yīng)用程序的?？臻g，導(dǎo)致空間，導(dǎo)致棧溢出錯誤棧溢出錯誤，使程序失敗。，使程序失敗。？/ 無窮遞歸的例子/ 講不完的故事void StoryStory () printf ( “從前有座山，山上有個廟，廟里有個和尚在講故事：” ); Story();Story();

26、遞歸的設(shè)計原則（1 1）基準情形）基準情形必須存在不用繼續(xù)遞歸即可解決的情況。（2 2）不斷推進）不斷推進對于需要遞歸解決的情況，每一次遞歸都要使得求解朝著基準情況的方向推進。（3 3）設(shè)計法則）設(shè)計法則假設(shè)所有的遞歸調(diào)用都能運行。（4 4）合成效益）合成效益解決一個問題時，切勿在不同的遞歸調(diào)用中做重復(fù)的工作。Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(1)Fib(2)Fib(1)用這個函數(shù)計算Fib(40)Fib(40)竟然用了83758375毫秒毫秒!一個不符合合成效益法則的例子long long FibFib( ( intint n ) n ) if

27、( n=1 ) return 0; if ( n=1 ) return 0; if ( n=2 ) return 1; if ( n=2 ) return 1; return return Fib(n-1)Fib(n-1)+ +Fib(n-2)Fib(n-2); ; 遞歸的優(yōu)點和缺點優(yōu)點優(yōu)點缺點缺點遞歸函數(shù)遞歸函數(shù)結(jié)構(gòu)清晰結(jié)構(gòu)清晰，程序易讀，正確性容易證明，程序易讀，正確性容易證明反復(fù)的遞歸函數(shù)調(diào)用使得執(zhí)行反復(fù)的遞歸函數(shù)調(diào)用使得執(zhí)行效率較低效率較低消除遞歸為什么消除遞歸？為什么消除遞歸？1.1.某些語言不支持函數(shù)的遞歸調(diào)用某些語言不支持函數(shù)的遞歸調(diào)用2.2.在某些關(guān)鍵部分，遞歸算法影響了執(zhí)行的效率在某些關(guān)鍵部分，遞歸算法影響了執(zhí)行的效率如何消除遞歸？如何消除遞歸？1.1.轉(zhuǎn)化為轉(zhuǎn)化為循環(huán)遞推循環(huán)遞推2.2.自己管理一個自己