數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列算法應(yīng)用

1迷宮求解2表達(dá)式求值3漢諾塔問(wèn)題4楊輝三角形棧和隊(duì)列算法應(yīng)用題1、迷宮問(wèn)題【例1】編寫(xiě)算法求解從入口到出口的迷宮路徑。

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

do｛

若當(dāng)前位置可通，

則｛將當(dāng)前位置插入棧頂；

若該位置是出口位置，則算法結(jié)束；否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；

｝

否則{

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

…

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

若棧不空，則重新測(cè)試新的棧頂位置，

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

例如:Exp=ab

+

(cd/e)f前綴式:+

ab

c/def中綴式:ab

+

cd/ef后綴式:ab

cde/f

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

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

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

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

表達(dá)式的三種標(biāo)識(shí)方法：設(shè)

Exp=S1+

OP

+S2則稱(chēng)

OP

+S1+S2

為前綴表示法

S1+

OP

+S2

為中綴表示法

S1+S2+

OP

為后綴表示法

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

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

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

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

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

cd/e

f

后綴式:abc+de/f

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

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

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

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

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

當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，

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

………a();b();

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

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

//圓盤(pán)移到y(tǒng),z作輔助塔6move(x,n,z);//將編號(hào)為n的圓盤(pán)從x移到z7hanoi(n-1,y,x,z);//將y上編號(hào)為１至n-1的

//圓盤(pán)移到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漢塔棧遞歸過(guò)程【例3-2】漢塔問(wèn)題的非遞歸算法voidhanoi1(intn,charx,chary,charz){

//將塔座x至上而下編號(hào)為1至n的圓盤(pán)

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

if(n==1){

move(x,1,z);

//將編號(hào)為1的圓盤(pán)從x移到z

return;}//if漢諾塔問(wèn)題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，結(jié)束move(temp2.x,temp2.n,temp2.z);

漢諾塔問(wèn)題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)進(jìn)棧

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

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

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

漢諾塔問(wèn)題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)進(jìn)棧}//else}//while}//hanoi1漢諾塔問(wèn)題漢塔問(wèn)題的棧遞歸模擬過(guò)程

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

2,B,A,C3,A,B,C漢諾塔問(wèn)題漢塔問(wèn)題的棧遞歸模擬過(guò)程

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漢諾塔問(wèn)題漢塔問(wèn)題的棧遞歸模擬過(guò)程

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

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

1

1

1

1

2

1

1

3

3

1

1

4

6

4

1

……

4、楊輝三角形問(wèn)題

解題分析

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

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

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

[2]當(dāng)k<n時(shí)，下一行0標(biāo)記入隊(duì)，否則，轉(zhuǎn)[6]；楊輝三角形問(wèn)題

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

[5]

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

[6]刪除隊(duì)頭元素0；

[7]輸出第n行，結(jié)束。楊輝三角形問(wèn)題輸出二項(xiàng)式系數(shù)表的第n行voidyanghui(intn){

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

InitQueue(Q,n+2);

//設(shè)置最大容量為n+2的空隊(duì)列

EnQueue(Q,0);

//添加行界值

EnQueue(Q,1);

EnQueue(Q,1);

//第一行的值入隊(duì)列

k=1;

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

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

EnQueue(Q,0);

//下一行界值“0”入隊(duì)列

do{