1迷宮求解2表達式求值3漢諾塔問題4楊輝三角形棧和隊列算法應用題1、迷宮問題【例1】編寫算法求解從入口到出口的迷宮路徑。

迷宮問題通常用的是“窮舉求解”的方法迷宮問題求迷宮路徑算法的基本思想是：若當前位置“可通”，則納入路徑，繼續前進;若當前位置“不可通”，則后退，換方向繼續探索;若四周“均無通路”，則將當前位置從路徑中刪除出去。迷宮問題設定當前位置的初值為入口位置；

do｛

若當前位置可通，

則｛將當前位置插入棧頂；

若該位置是出口位置，則算法結束；否則切換當前位置的東鄰方塊為新的當前位置；

｝

否則{

｝｝while(棧不空）；求迷宮中一條從入口到出口的路徑的算法：

…

…若棧不空且棧頂位置尚有其他方向未被探索，則設定新的當前位置為:沿順時針方向旋轉找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則｛刪去棧頂位置；//從路徑中刪去該通道塊

若棧不空，則重新測試新的棧頂位置，

直至找到一個可通的相鄰塊或出棧至?？?；｝若棧空，則表明迷宮沒有通路。2、表達式求值【例2-1】編寫算法試用兩個棧求解表達式求值。

例如:Exp=ab

+

(cd/e)f前綴式:+

ab

c/def中綴式:ab

+

cd/ef后綴式:ab

cde/f

+結論:1）操作數之間的相對次序不變;2）運算符的相對次序不同;3）可設兩個棧求解;表達式求值?運算符θ1和θ2之間的優先關系根據上述運算規則，在運算過程中，任意兩個前后相繼出現的運算符θ1和θ2之間的優先關系必為下面三種關系之一：

θ1<θ2，θ1的優先權低于θ2。

θ1=θ2，θ1的優先權等于θ2。

θ1>θ2，θ1的優先權高于θ2。表達式求值?算符之間的優先關系2、表達式求值【例2-2】編寫算法試用兩個棧求解后綴表達式求值。

表達式的三種標識方法：設

Exp=S1+

OP

+S2則稱

OP

+S1+S2

為前綴表示法

S1+

OP

+S2

為中綴表示法

S1+S2+

OP

為后綴表示法

后綴式的運算規則為:

運算符在式中出現的順序恰為表達式的運算順序;

每個運算符和在它之前出現

且緊靠它的兩個操作數構成一個最小表達式。表達式求得后綴式？

每個運算符的運算次序要由它之后的一個運算符來定，在后綴式中，優先數高的運算符領先于優先數低的運算符。分析“原表達式”和“后綴式”中的運算符:原表達式:a+b

cd/e

f

后綴式:abc+de/f

從原表達式求得后綴式的規律為：1)設立操作數棧；2)設表達式的結束符為“#”，

予設運算符棧的棧底為“#”；3)若當前字符是操作數，則直接發送給后綴式。4)若當前運算符的優先數高于棧頂運算符，則進棧；5)否則，退出棧頂運算符發送給后綴式；

6)“(”對它之前后的運算符起隔離作用，“)”可視為自相應左括弧開始的表達式的結束符。從原表達式求得后綴式的規律為：voidtransform(charsuffix[],charexp[]){InitStack(S);Push(S,#);p=exp;ch=*p;

while(!StackEmpty(S)){if(!IN(ch,OP))Pass(Suffix,ch);else{}

if(ch!=#){p++;ch=*p;}else{Pop(S,ch);Pass(Suffix,ch);}

}//while}//CrtExptree……switch(ch){

case

(

:Push(S,ch);break;

case

)

:

Pop(S,c);

while(c!=

()

{Pass(Suffix,c);Pop(S,c)}

break;

defult:while(Gettop(S,c)&&(precede(c,ch)))

{Pass(Suffix,c);Pop(S,c);}

if(ch!=

#)Push(S,ch);

break;

}

//switch后綴表達式求值如何從后綴式求值？先找運算符，再找操作數例如：

abcde/f+abd/ec-d/e(c-d/e)f3、漢諾塔問題【例3-1】編寫算法遞歸求解漢諾塔問題。

實現遞歸將所有的實在參數、返回地址等信息傳遞給被調用函數保存；為被調用函數的局部變量分配存儲區；將控制轉移到被調用函數的入口。

當在一個函數的運行期間調用另一個函數時，在運行該被調用函數之前，

需先完成三項任務：保存被調函數的計算結果；釋放被調函數的數據區；依照被調函數保存的返回地址將控制轉移到調用函數。從被調用函數返回調用函數之前，應該完成下列三項任務：多個函數嵌套調用的規則是：內存管理實行“棧式管理”后調用先返回！例如：voidmain(){voida(){voidb(){

………a();b();

……}//main}//a}//bMain的數據區函數a的數據區函數b的數據區

遞歸工作棧：遞歸過程執行過程中占用的數據區。遞歸工作記錄：每一層的遞歸參數合成一個記錄。當前活動記錄：棧頂記錄指示當前層的執行情況。當前環境指針：遞歸工作棧的棧頂指針。遞歸函數執行的過程可視為同一函數進行嵌套調用，例如：1voidhanoi(intn,charx,chary,charz){//將塔座x上按直徑由小到大且至上而下編號為1至n//的n個圓盤按規則搬到塔座z上，y可用作輔助塔座。2if(n==1)3move(x,1,z);//將編號為１的圓盤從x移到z4else{5hanoi(n-1,x,z,y);//將x上編號為１至n-1的

//圓盤移到y,z作輔助塔6move(x,n,z);//將編號為n的圓盤從x移到z7hanoi(n-1,y,x,z);//將y上編號為１至n-1的

//圓盤移到z,x作輔助塔8}9}101voidhanoi(intn,charx,chary,charz){2if(n==1)3move(x,1,z);4else{5hanoi(n-1,x,z,y);6move(x,n,z);7hanoi(n-1,y,x,z);8}9}10漢塔棧遞歸過程【例3-2】漢塔問題的非遞歸算法voidhanoi1(intn,charx,chary,charz){

//將塔座x至上而下編號為1至n的圓盤

//按規則搬到塔座z上，y可作輔助塔座。

if(n==1){

move(x,1,z);

//將編號為1的圓盤從x移到z

return;}//if漢諾塔問題ElemTypetemp,temp2;Initstack(S);temp.n=n;temp.x=x;temp.y=y;temp.z=z;push(S,temp);while(!StackEmpty(S)){pop(S,temp2);if(temp2.n==1)//n==1，結束move(temp2.x,temp2.n,temp2.z);

漢諾塔問題else{

temp.n=temp2.n-1;temp.x=temp2.y;

temp.y=temp2.x;temp.z=temp2.z;

push(S,temp);//(n-1,y,x,z)進棧

temp.n=1;temp.x=temp2.x;

temp.y=temp2.y;temp.z=temp2.z;

push(S,temp);//(1,x,y,z)進棧

漢諾塔問題temp.n=temp2.n-1;temp.x=temp2.x;temp.y=temp2.z;temp.z=temp2.y;

push(S,temp);//(n-1,x,z,y)進棧}//else}//while}//hanoi1漢諾塔問題漢塔問題的棧遞歸模擬過程

hanoi(3,A,B,C);第一次循環2,A,C,B1,A,B,C

2,B,A,C3,A,B,C漢諾塔問題漢塔問題的棧遞歸模擬過程

hanoi(3,A,B,C);第二次循環

2,B,A,C1,A,B,C1,A,C,B1,C,A,B1,A,B,C

2,B,A,C漢諾塔問題漢塔問題的棧遞歸模擬過程

hanoi(3,A,B,C);第三次循環

1,B,C,A1,B,A,C1,A,B,C漢諾塔問題【例4】設計算法輸出二項式系數表（楊輝三角）的第n行序列。

1

1

1

1

2

1

1

3

3

1

1

4

6

4

1

……

4、楊輝三角形問題

解題分析

（1）問題的數學解法這是一個初等數學中討論的問題。系數表中的第k行有k+1個數，除了第一個和最后一個數為1之外，其余的數則為上一行中位其左、右的兩數之和。

楊輝三角形問題（2）選取數據結構一種最直接的想法是利用兩個數組，其中一個存放已經計算得到的第k行的值，然后輸出第k行的值同時計算第k+1行的值，并且這兩個數組在計算過程中需相互交換。若引入“循環隊列”，則可以省略一個數組的輔助空間，而且可以利用隊列的操作，使程序結構變得清晰，問題簡化。楊輝三角形問題（3）算法描述每行添加一個數字0，即作為行標記，又參與計算。

[1]初始化隊列，第1行（0，1，1）入隊，計數器k賦初值1；

[2]當k<n時，下一行0標記入隊，否則，轉[6]；楊輝三角形問題

[3]刪除隊頭元素，并將其值與當前隊頭元素的值相加的和插入隊列；[4]判斷是否換行，若否，轉[3]；

[5]

k值加1，轉[2]；

[6]刪除隊頭元素0；

[7]輸出第n行，結束。楊輝三角形問題輸出二項式系數表的第n行voidyanghui(intn){

//輸出楊輝三角形的第n(n>1)行

InitQueue(Q,n+2);

//設置最大容量為n+2的空隊列

EnQueue(Q,0);

//添加行界值

EnQueue(Q,1);

EnQueue(Q,1);

//第一行的值入隊列

k=1;

楊輝三角形問題while(k<n){

//通過循環隊列求前n-1行的值

EnQueue(Q,0);

//下一行界值“0”入隊列

do{