數(shù)據(jù)結構棧和隊列算法應用

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

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

do｛

若當前位置可通，

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

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

｝

否則{

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

…

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

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

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

例如:Exp=ab

+

(cd/e)f前綴式:+

ab

c/def中綴式:ab

+

cd/ef后綴式:ab

cde/f

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

θ1<θ2，θ1的優(yōu)先權低于θ2。

θ1=θ2，θ1的優(yōu)先權等于θ2。

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

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

Exp=S1+

OP

+S2則稱

OP

+S1+S2

為前綴表示法

S1+

OP

+S2

為中綴表示法

S1+S2+

OP

為后綴表示法

后綴式的運算規(guī)則為:

運算符在式中出現(xiàn)的順序恰為表達式的運算順序;

每個運算符和在它之前出現(xiàn)

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

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

cd/e

f

后綴式:abc+de/f

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

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

6)“(”對它之前后的運算符起隔離作用，“)”可視為自相應左括弧開始的表達式的結束符。從原表達式求得后綴式的規(guī)律為：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后綴表達式求值如何從后綴式求值？先找運算符，再找操作數(shù)例如：

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

實現(xiàn)遞歸將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存；為被調(diào)用函數(shù)的局部變量分配存儲區(qū)；將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。

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

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

………a();b();

……}//main}//a}//bMain的數(shù)據(jù)區(qū)函數(shù)a的數(shù)據(jù)區(qū)函數(shù)b的數(shù)據(jù)區(qū)

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

//圓盤移到y(tǒng),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的圓盤

//按規(guī)則搬到塔座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);第一次循環(huán)2,A,C,B1,A,B,C

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

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

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);第三次循環(huán)

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

1

1

1

1

2

1

1

3

3

1

1

4

6

4

1

……

4、楊輝三角形問題

解題分析

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

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

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

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

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

[5]

k值加1，轉(zhuǎn)[2]；

[6]刪除隊頭元素0；

[7]輸出第n行，結束。楊輝三角形問題輸出二項式系數(shù)表的第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){

//通過循環(huán)隊列求前n-1行的值

EnQueue(Q,0);

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

do{