棧和隊列B課件

問：為什么要設計堆棧？它有什么獨特用途？簡化了程序設計的問題；遞歸運算的有力工具；用于保護現場和恢復現場；調用函數或子程序非它莫屬。答：第三章棧和隊列1棧和隊列B

括號匹配的檢驗————P49

設計思路：用棧暫存左括號例3：行編輯程序————P49

設計思路：用棧存放輸入的字符例4：表達式求值—————P52

設計思路：用棧暫存運算符例5：漢諾儀（Hanoi）塔-——P55

設計思路：用棧實現遞歸調用例2：3.2棧的應用舉例

2棧和隊列B例2：括號匹配的檢驗3棧和隊列BvoidLineEdit()

算法3.2

{InitStack(s);ch=getchar();

while(ch!=EOF){

while(ch!=EOF&&ch!=‘/n’){

switch(ch){case‘#’:Pop(S,c);break;case‘@’:ClearStack(S);break;default:Push(S,ch);break;}ch=getchar();}將從棧底到棧頂的字符傳送到調用過程的數據區(qū)；

ClearStack(S);if(ch!=EOF)ch=getchar();}DestroyStack(S);}//LineEdit4棧和隊列B例4表達式求值問題的提出：

設計一個小計算器:對鍵入的表達式進行求值。高級語言中的賦值語句：變量=表達式；Y=2;Z=3;X=y+z*2;如何對表達式求值呢？？5棧和隊列B表達式求值的算法是“算符優(yōu)先法”。例如：3*（7–2）（1）要正確求值，首先了解算術四則運算的規(guī)則：

a.從左算到右

b.先乘除，后加減

c.先括號內，后括號外由此，此表達式的計算順序為：

3*（7–2）=3*5=156棧和隊列B（2）比較優(yōu)先權關系根據上述三條運算規(guī)則，在運算的每一步中，對任意相繼出現的算符

1和

2

，都要比較優(yōu)先權關系。算符優(yōu)先法所依據的算符間的優(yōu)先關系見教材P53表3.1

（是提供給計算機用的表！）棧的應用（表達式求值）7棧和隊列B算符優(yōu)先關系表

表達式中任何相鄰運算符c1、c2的優(yōu)先關系有：

c1<c2：c1的優(yōu)先級低于c2

c1=c2：c1的優(yōu)先級等于c2

c1>c2：c1的優(yōu)先級高于c2+

c2

c1

-*/()#+-*/()#>><<<>>>><<<>>>>>><>>>>>><>><<<<<=>>>>>><<<<<=算符間的優(yōu)先關系表注：c1

c2是相鄰算符，c1在左，c2在右由表可看出，右括號)和井號#作為

2時級別最低；由c規(guī)則得出：*，/，+，-為

1時的優(yōu)先權低于‘（’，高于‘）’由a規(guī)則得出：‘（’=‘）’表明括號內運算已算完?！?’=‘#’表明表達式求值完畢。8棧和隊列B（3）算法思想：設定兩棧：操作符棧OPTR，操作數棧OPND棧初始化：設操作數棧OPND為空；操作符棧OPTR的棧底元素為表達式起始符‘#’；依次讀入字符：是操作數則入OPND棧，是操作符則要判斷：

if

操作符<棧頂元素，則退棧、計算，結果壓入OPND棧；操作符=棧頂元素且不為‘#’，脫括號（彈出左括號）；操作符>棧頂元素，壓入OPTR棧。棧的應用（表達式求值）9棧和隊列B棧的應用（表達式求值）OPTROPNDINPUTOPERATE3*(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#Operate(3*5)#15#GetTop(opnd)10棧和隊列BStatusEvaluateExpression(OperandType&result){InitStack(OPND);InitStack(OPTR);Push(OPTR,’#’);c=getchar();while((c!=‘#’)||(GetTop(OPTR)!=‘#’)){if(!In(c,OP){Push(OPND,c);c=getchar();}elseswitch(precede(GetTop(OPTR),c)){case‘<’:Push(OPTR,c);c=getchar();break;case‘=’:Pop(OPTR);c=getchar();break;

case‘>’:Pop(OPTR,theta);Pop(opnd,b);Pop(opnd,a);

result=Operate(a,theta,b);Push(OPND,result);break;}//switch}//whilereturn(GetTop(OPND));}//EvaluateExpression11棧和隊列B例5漢諾儀（Hanoi）塔傳說在創(chuàng)世紀時，在一個叫Brahma的寺廟里，有三個柱子，其中一柱上有64個盤子從小到大依次疊放，僧侶的工作是將這64個盤子從一根柱子移到另一個柱子上。

移動時的規(guī)則：

每次只能移動一個盤子；只能小盤子在大盤子上面；可以使用任一柱子。當工作做完之后，就標志著世界末日到來。分析：設三根柱子分別為x，y,z,盤子在x柱上，要移到z柱上。1、當n=1時，盤子直接從x柱移到z柱上；2、當n>1時,則①設法將前n–1個盤子借助z，從x移到y柱上，把盤子n從x移到z柱上；②把n–1個盤子從y移到z柱上。xyznn–112棧和隊列BVoidHanoi(intn,charx,chary,charz){//將n個編號從上到下為1…n的盤子從x柱，借助y柱移到z柱

if(n==1)move(x,1,z);//將編號為1的盤子從x柱移到z柱

else{Hanoi(n-1,x,z,y);

//將n-1個編號從上到下為1…n-1的盤子從x柱，借助Z柱移到Y柱

move(x,n,z);//將編號為n的盤子從x柱移到z柱

Hanoi(n-1,y,x,z);//將n-1個編號從上到下為1…n-1的盤子從y柱，借助x柱移到z柱

}}//Hanoi13棧和隊列B3.3棧與遞歸一般函數的調用機制A(){…B();…}C(){……}B(){…C();…}調用調用返回返回函數調用順序ABC函數返回順序CBA后調用的函數先返回

函數調用機制可通過棧來實現計算機正是利用棧來存儲函數的返回地址及所有實參14棧和隊列B3.3棧與遞歸當一個函數調用另一個函數時，在調用之前系統要做3件事：1.將所有的實在參數、返回地址等信息傳遞給被調用函數保存；2.為被調用函數的局部變量分配存儲空間；（入棧）3.將控制轉移到被調用函數的入口。1.保存被調用函數的計算結果；2.釋放被調用函數的數據區(qū)；（出棧）3.依照被調用函數保存的地址將控制轉移到調用函數。返回時，系統要做3件事：15棧和隊列B3.3棧與遞歸

1．什么是遞歸遞歸是一個很有用的工具，在數學和程序設計等許多領域中都用到了遞歸。遞歸定義：簡單地說，一個用自己定義自己的概念,稱為遞歸定義。例n!=1*2*3*4*(n-1)*nn!遞歸定義n!=1當n=0時

n!=n(n-1)!當n>0時用(n-1)!定義n!16棧和隊列B2.遞歸函數：一個直接調用自己或通過一系列調用間接調用自己的函數稱為遞歸函數。A（）{…A();…}B(){C(){…