数据结构栈和队列算法应用

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{