数据结构 课件 栈的应用举例

《数据结构 课件 栈的应用举例》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、例二、数制转换例三、括号匹配的检验例四、迷宫求解例五、表达式求值例一、大整数相加大整数相加相加从低位开始,输出从高位开始用两个栈保存操作数（大整数）结果保存到结果栈数制转换的原理为：N=(Ndivd)×d+Nmodd例如：（1348)10转换成(2504)8的运算过程如下：NNdiv8Nmod8计算顺序输出顺序134816841682102125202数制转换voidconversion(){//显示和输入的十进制数对应的八进制数值InitStack(S);scanf("%d",N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Po

2、p(S,e);printf("%d",e);}}//conversion检验含两种括弧的表达式中括弧匹配的正确性。如表达式中（［］（））或［（［］［］）］等为正确的匹配，［（］）或（［（）]或[()])均为不正确的匹配。检验括弧匹配的方法可用“按期待的急迫程度进行处理”描述之。[例如考虑下列括号序列：([][())]]可见，括弧匹配也遵循“后进先出”的规律。如何表示下列“不匹配”的情况？到来的右括弧非是所“期待”的;来了一个“不速之客”;直到结束，也没有等到“期待”的匹配;算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空？若栈空，则表明该“右括弧”多余否则和栈

3、顶元素比较，若相匹配，则“左括弧出栈”否则表明不匹配3）表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余。boolmatching(charexp[],intn){//检测长度为n的字符序列exp中的括弧是否匹配inti=0;mat=true;InitStack(S);while(i

4、se)……计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道。迷宫问题#################Q#########################Q#######结论:1．从入口进入迷宫之后，不管在迷宫的哪一个位置上，都是先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北的方向，依着某个走得通的方向继续往前直到出口为止；2．如果

5、在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通；迷宫问题(八个方向)EntranceExitMaze[m][p]四周加墙ExitMaze[m+2][p+2]移动方向(八个方向)X[i][j][i+1][j][i][j+1][i][j-1][i+1][j-1][i+1][j+1][i-1][j+1][i-1][j][i-1][j-1]NESWNESESWNW八个方向移动表方向qMove[q].aMove[q].bN-10NE-11E

6、01SE11S10SW1-1W0-1NW-1-1Structoffsets{inta,b;}offsetsmove[8]enumdirections{N,NE,E,SE,S,SW,W,NW};迷宫问题通常解决迷宫问题时常用堆栈来储存已走过之路径的方向和坐标.structItems{intx,y;//已经走过的某位置intdir;//从该位置出发,按顺时针//仍未走过的下一个方向}迷宫问题使用另外一个mark[m+2][p+2]维度的数组来记录哪些位置已经走访过,该数组初始化为0,一旦某个位置被访问,则相应位置为1.求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;若当

7、前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。算法伪代码与实现见课本114程序3.153.16栈变化分析1,1,2i=0j=0d=0g=0h=0i=1j=1d=2g=1h=2i=1j=1d=3g=2h=21,1,4i=2j=2d=0g=2h=21,1,4i=2j=2d=0g=1h=21,1,4i=2j=2d=1g=1h=3说明:1.栈中结点代表曾经走的位置,以及从该位置出发,还未试探的下