数据结构栈和队列算法应用ppt课件.ppt

《数据结构栈和队列算法应用ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1迷宫求解2表达式求值3汉诺塔问题4杨辉三角形栈和队列算法应用题1、迷宫问题【例1】编写算法求解从入口到出口的迷宫路径。迷宫问题通常用的是“穷举求解”的方法迷宫问题求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。迷宫问题设定当前位置的初值为入口位置；do｛若当前位置可通，则｛将当前位置插入栈顶；若该位置是出口位置，则算法结束；否则切换当前位置的东邻方块为新的当前位置；｝否则{｝｝while(栈不空）；求迷宫中一条从入口到出口的路径的算法：……若栈不空且栈顶位置尚

2、有其他方向未被探索，则设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则｛删去栈顶位置；//从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；｝若栈空，则表明迷宫没有通路。2、表达式求值【例2-1】编写算法试用两个栈求解表达式求值。例如:Exp=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd/ef后缀式:abcde/f+结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;3）可设两个栈求解;表达式求值•运算符θ1和θ2之间的优先关系根据上

3、述运算规则，在运算过程中，任意两个前后相继出现的运算符θ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为后缀表示法后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。表达式求得后缀式？每

4、个运算符的运算次序要由它之后的一个运算符来定，在后缀式中，优先数高的运算符领先于优先数低的运算符。分析“原表达式”和“后缀式”中的运算符:原表达式:a+bcd/ef后缀式:abc+de/f从原表达式求得后缀式的规律为：1)设立操作数栈；2)设表达式的结束符为“#”，予设运算符栈的栈底为“#”；3)若当前字符是操作数，则直接发送给后缀式。4)若当前运算符的优先数高于栈顶运算符，则进栈；5)否则，退出栈顶运算符发送给后缀式；6)“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为：voidtransform(ch

5、arsuffix[],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;

6、defult:while(Gettop(S,c)&&(precede(c,ch))){Pass(Suffix,c);Pop(S,c);}if(ch!=#)Push(S,ch);break;}//switch后缀表达式求值如何从后缀式求值？先找运算符，再找操作数例如：abcde/f+abd/ec-d/e(c-d/e)f3、汉诺塔问题【例3-1】编写算法递归求解汉诺塔问题。实现递归将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完

7、成三项任务：保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回调用函数之前，应该完成下列三项任务：多个函数嵌套调用的规则是：内存管理实行“栈式管理”后调用先返回！例如：voidmain(){voida(){voidb(){………a();b();……}//main}//a}//bMain的数据区函数a的数据区函数b的数据区递归工作栈：递归过程执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示