第七講 棧的應用

第三章棧和隊列棧的應用2023/2/51濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系2復習與回顧棧的特點棧的基本術語鏈棧順序棧2濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系3

棧的應用舉例一、數(shù)制轉(zhuǎn)換二、括號匹配的檢驗三、表達式求值四、實現(xiàn)遞歸

本講內(nèi)容3濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系4

算法基于原理：“除基取余法”

即：除以基數(shù)取余數(shù)，逆序排列。

一、數(shù)制轉(zhuǎn)換4濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系5

例如：（1348)10=(2504)8，其運算過程如下：

N

Ndiv8

Nmod8

13481684

168210

2125

202計算順序輸出順序5濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系6voidconversion(){

InitStack(S);

scanf("%d",N);while(N){

Push(S,N%8);N=N/8;}while(!StackEmpty(S))

{

Pop(S,e);printf("%d",e);}}//conversion6濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系7二.括號匹配的檢驗括號匹配問題括號匹配{[()]}，((){})，()括號不匹配(()，()]，([)]檢驗括號匹配的方法：“期待的急迫程度”檢查括號匹配的算法設一棧遇到左括號則入棧，遇到右括號時，若?？?，則不匹配(右括號太多)；否則，如果棧頂元素與該右括號匹配，則出棧；否則不匹配(括號不配對)。輸入結束后，若棧為空，則匹配，否則不匹配(左括號太多)。7濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系81.算術表達式的組成操作數(shù)（運算對象或運算量）運算符界限符（如圓括號，作用是改變運算次序）

其中操作數(shù)可以是常量、變量、函數(shù)、表達式運算符有單目、雙目，我們僅以+、-、*、/四種運算為例三.（算術）表達式的求值8濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系92.常見表達式有幾種:

(根據(jù)運算符在表達式中的不同位置)

3*(5–2)中綴表達式3*(5–2)后綴表達式前綴表達式352-**3-529濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系10三種表達式的特點操作數(shù)之間的相對次序不變運算符的相對次序可能不同中綴式：必須有括號信息，否則運算順序改變前綴式：無括號；連續(xù)出現(xiàn)的兩個操作數(shù)和在它們之前出現(xiàn)且緊靠它們的運算符構成了一個最小表達式后綴式：無括號；運算符的排列順序就是計算順序，每個運算符加上在它之前且緊靠它的兩個操作數(shù)構成了一個最小表達式。10濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系113.后綴表達式的計算（僅討論個位數(shù)運算）

算法自左至右讀取表達式中的字符設一棧存放操作數(shù)當讀到運算符時，則取出棧頂?shù)膬蓚€數(shù)進行運算，將結果入棧最終結果保存在棧中。11濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系12intPostfix(){ InitStack(S); read(c); while(c

!=

'='){

if(isdigit(c)){ read(v);

Push(S,v); }

else

{ Pop(S,b);

Pop(S,a); Push(S,Operate(a,c,b)); } read(c); }

Pop(S,result); returnresult;}12濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系13后綴表達式求值

用實型數(shù)棧S存放計算后綴式的中間及最終結果，求值算法可描述如下:

棧初始化。從左到右掃描后綴表達式，重復下述兩步操作，直到表達式尾。①從表達式中取出下個TOKEN(操作數(shù)、運算符)②CASETOKENOF

操作數(shù)：將操作數(shù)直接入棧S;

運算符：出棧兩個操作數(shù)，對其進行TOKEN操作，結果壓入棧S

當遇到后綴表達式結束，棧頂?shù)闹稻褪墙Y果(應是棧中唯一元素)。13濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系14835+562/-*-#

求值883835+83+5=8888562/6/2=38853-885-3=22*88*2=1616-8-16=-8-814濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系154.中綴表達式轉(zhuǎn)化為后綴表達式分析

中綴表達式1+2*3+(4*5+6)*7后綴表達式123*+45*6+7*+算法讀到操作數(shù)時立即輸出運算符存放在棧中，遇到運算符時，彈出當前棧頂運算符直到遇到優(yōu)先級更低的運算符為止。15濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系16中綴表達式轉(zhuǎn)為后綴表達式

設中綴表達式和后綴表達式分別在數(shù)組IFX和PFX中，用棧S實現(xiàn)中綴式轉(zhuǎn)為后綴式，對IFX中表達式從左到右掃描，設TOKEN是掃描讀到的符號，轉(zhuǎn)換算法可描述如下。棧初始化。從左到右掃描數(shù)組IFX，重復下述兩步操作，直到表達式尾。

16濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系17

①從IPX中取出TOKEN(數(shù)字、運算符、左括號、右括號)；②CASETOKENOF

‘(’：壓入棧S;

操作數(shù)：將操作數(shù)直接送入PFX，后面加一個空格;

運算符：如?？栈騎OKEN比棧頂元素優(yōu)先級高，將TOKEN進棧；否則，將棧內(nèi)優(yōu)先級高于或等于TOKEN的運算符，退棧并將退棧元素送入PFX；

‘)’：退棧并將退棧元素送PFX，直到碰到左括號，左括號退棧不送PFX。結束符號:連續(xù)退棧并送退棧元素到PFX，直至棧空。17濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系18舉例：將中綴表達式

8-(3+5)*(5-6/2)#

轉(zhuǎn)為后綴表達式883

835

835+

835+5

835+56

835+562

835+562/-

835+562/-*-

18濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系19表達式轉(zhuǎn)換的簡單方法中綴表達式轉(zhuǎn)為后綴表達式有三步：（1）將中綴表達式中所有的子表達式按計算規(guī)則用嵌套括號括起來；（2）順序?qū)⒚繉ㄌ栔械倪\算符移到相應括號的后面；（3）刪除所有括號。

例如，將中綴表達式8-(3+5)*(5-6/2）轉(zhuǎn)為后綴表達式。按如上步驟：執(zhí)行完上面第一步后為：(8-((3+5)*(5-(6/2))))；執(zhí)行完上面第二步后為：(8((35)+(5(62)/)-)*)-；執(zhí)行完上面第三步后為：835+562/-*-19濱州學院計算機科學技術系2023/2/5濱州學院計算機科學技術系20作業(yè)用棧實現(xiàn)將中綴表達式

10+(18+9*3)/15-6#

轉(zhuǎn)換成后綴表達式并進行后綴表達式的計算，分別畫出兩個步驟中的棧的變化示意圖。20濱州學院計算機科學技術系四.

棧與遞歸1.函數(shù)調(diào)用與返回的過程2.遞歸函數(shù)3.遞歸的設計原則4.遞歸的優(yōu)點和缺點5.消除遞歸21濱州學院計算機科學技術系1.函數(shù)調(diào)用與返回的過程（1）函數(shù)調(diào)用

當在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，

需先完成三項任務：將返回地址、所有實參等信息傳遞給被調(diào)用函數(shù)保存；為被調(diào)用函數(shù)的局部變量分配存儲區(qū)；將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。22濱州學院計算機科學技術系1.函數(shù)調(diào)用與返回的過程（2）函數(shù)返回

從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應該完成下列三項任務：保存被調(diào)函數(shù)的計算結果；釋放被調(diào)函數(shù)保存局部變量的數(shù)據(jù)區(qū)；依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。函數(shù)嵌套調(diào)用時，后調(diào)用的函數(shù)先返回。23濱州學院計算機科學技術系intmain(){ intn=10; intsn;

sn=sum(n); cout<<sn<<endl;}intsum(intn){ inti,s=0;

for(i=1;i<n;i++) s+=i; returns;}intmain(){ intn=10; intsn;

sn=sum(n); cout<<sn<<endl;}intsum(intn){ inti,s=0;

for(i=1;i<n;i++) s+=i; returns;}main:n=10main:sn=sum:n=10goto:5sum:i=sum:s=0sum:i=11sum:s=55main:sn=55main()sum()24濱州學院計算機科學技術系2.遞歸函數(shù)函數(shù)直接或間接調(diào)用自身，稱為遞歸(Recursion)。何時應用遞歸？問題具有遞歸的數(shù)學定義使用了遞歸的數(shù)據(jù)結構問題存在遞歸的解決方法25濱州學院計算機科學技術系遞歸過程的應用（1）（1）問題的數(shù)學定義是遞歸的：求n的階乘n!

longFact(intn){if(n==1)return(1);elsereturn(n*Fact(n-1));}26濱州學院計算機科學技術系遞歸過程的應用（1）（1）問題的數(shù)學定義是遞歸的：計算Fibonacci數(shù)列：0,1,1,2,3,5,8,13,21,…longFib(intn){if(n==1)return0;if(n==2)return1;returnFib(n-1)+Fib(n-2);}27濱州學院計算機科學技術系遞歸過程的應用（1）（1）問題的數(shù)學定義是遞歸的：計算xn（n為整數(shù)，n≥0）28濱州學院計算機科學技術系遞歸過程的應用（1）（1）問題的數(shù)學定義是遞歸的：計算xn（n為整數(shù)，n≥0）doublePower(doublex,intn){if(n==0)return1;if(n==1)returnx;if(n%2==0)returnPower(x*x,n/2);elsereturnx*Power(x*x,n/2);}例如計算X64只需要6次乘法29濱州學院計算機科學技術系voidPrintLinkList(LinkListL){if(L!=NULL){printf(L->data);if(L->next!=NULL){PrintLinkList(L->next);}}}LL->next…以后將要學習的廣義表、樹和二叉樹等結構也具有遞歸的特點，所以常常使用遞歸算法。遞歸過程的應用（2）（2）數(shù)據(jù)結構是遞歸的：

打印鏈表中各結點的值30濱州學院計算機科學技術系遞歸過程的應用（3）問題存在遞歸的解決方法n階Hanoi塔問題：假設有三個分別命名為X,Y,Z的塔座，在X塔座上插有n個直徑大小各不相同，依小到大編號為1，2，…,n的圓盤，要求：把X上的n個圓盤移到Z上，排列順序相同，移動規(guī)則為：每次只能移動一個園盤；園盤可以在任一塔上做多次移動；在任何時刻，大盤不能壓在小盤的上面。XYZ31濱州學院計算機科學技術系棧與遞歸的實現(xiàn):Hanoi數(shù)學歸納法n=1,OK;設n=k時，若可以以Y為輔助塔，把k個盤從X移動到Z;當n=k+1時，方法：把X中k個盤，以Z為輔助塔，移動到Y;把X中第k+1個盤，移動到Z;把Y中k個盤，以X為輔助塔，移動到Z;32濱州學院計算機科學技術系問題存在遞歸的解決方法

Hanoi(n,a,b,c)表示解決n個盤子的漢諾塔問題（從a搬到c，可以借助b）。解決方法：若n=1，直接將盤子從a搬到c即可；否則，可以分解為如下步驟：Hanoi(n-1,a,c,b)move(n,a,c)Hanoi(n-1,b,a,c)voidHanoi(intn,chara,charb,charc){if(n==1)move(n,a,c);else{Hanoi(n-1,a,c,b);move(n,a,c);

Hanoi(n-1,b,a,c);}}33濱州學院計算機科學技術系3.遞歸的設計原則如果遞歸設計不當…容易造成無窮遞歸，最終會耗盡應用程序的?？臻g，導致棧溢出錯誤，使程序失敗。//無窮遞歸的例子//講不完的故事voidStory(){print(“從前有座山，山上有個廟，廟里有個和尚在講故事：”);

Story();}34濱州學院計算機科學技術系3.遞歸的設計原則（1）基準情形必須存在不用繼續(xù)遞歸即可解決的情況。（2）不斷推進對于需要遞歸解決的情況，每一次遞歸都要使得求解朝著基準情況的方向推進。（3）遞歸可行性假設所有的遞歸調(diào)用都能運行。（4）合成效益解決一個問題時，切勿在不同的遞歸調(diào)用中做重復的工作。35濱州學院計算機科學技術系一個不符合合成效益法則的例子：longFib(intn){if(n==1)return0;if(n==2)return1;returnFib(n-1)+Fib(n-2);}Fib(5)Fib(4)Fib(3)Fib(3)Fib(2)Fib(2)Fib(1)Fib(2)Fib(1)36濱州學院計算機科學技術系4.遞歸的優(yōu)點和缺點優(yōu)點：遞歸函數(shù)結構清晰，程序易讀，正確性容易證明。缺點：反復的遞歸函數(shù)調(diào)用使得執(zhí)行效率較低。37濱州學院計算機科學技術系5.消除遞歸為什么消除遞歸？某些語言不支持函數(shù)的遞歸調(diào)用。在某些關鍵部分，遞歸算法影響了執(zhí)行的效率。如何消除遞歸？（1）轉(zhuǎn)化為遞推（循環(huán)）。（2）自己管理一個遞歸工作棧。38濱州學院計算機科學技術系（1）遞歸和遞推使用遞推可以有效減少函數(shù)遞歸調(diào)用的次數(shù)，節(jié)省了時間和空間。//遞推計算n!longFact(intn){longfactor=1;for(inti=1;i<n;i++)factor=i*factor;