《栈的应用》PPT课件

《《栈的应用》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈的应用与队列2009/03/17内容：作业讲评表达式计算队列队列应用2链接结构栈:ki+2ki+1kik0plstacktopinfolink34bbs567删帖：89回帖：10关于编程环境微软学生资源：http://www.msuniversity.edu.cn/m_directdownload/introduction.aspx11关于网络编程2-3人asp.net/vs2008课堂报告+4分12栈的应用——表达式求值（续）表达式的三种标识方法:Exp=ab+(cd/e)f前缀式:+abc/def中缀式:ab+cd

2、/ef后缀式:abcde/f+中缀式丢失了括弧信息，致使运算的次序不能先确定。13关于表达式的几个问题为什么要先乘除后加减?为什么计算中要把中缀表达式转换为后缀（RPN）、前缀表达式?为什么说一个合法的前缀或后缀表达式的运算顺序一定是唯一确定的?14后缀式的运算后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现，且紧靠它的两个操作数构成一个最小表达式（算子）。例：31*(5–22)+7031522-*70+-22531*22-173115后缀表达式的求值过程。使用一个存放算子（运算分量）的栈。

3、求值过程顺序扫描后缀表达式，每次遇到算子便将它推入栈中；遇到运算符时，就从栈中弹出两个整数(算子)进行计算，而后再把结果推入栈中。到扫描结束时，留在栈顶的整数就是所求表达式的值。4123+35*/-16//by00720106顾森1718从中缀表达式求得后缀式的规则1)设立操作符栈2)设表达式的结束符为“#”,设运算符栈的栈底为“#”；3)若当前字符串是个操作数则直接发送给后缀式。否则：若当前运算符的优先数高于栈顶运算符，则进栈；否则：退出栈顶运算符发送给后缀式；gotostep3;4)“(”对它之前后的运算符起隔离作用，“)”可视为自相

4、应左括弧开始的表达式的结束符。相遇则自动取消。19中缀表达式转换成后缀表达式3*(7+3*6/2–5)#栈顶>栈外栈顶<栈外#*(+*/-！操作数：放过。操作符：与栈顶元素比较，优先级>栈顶元素push();否则pop();#优先级最低。push();pop();2021+运算符优先关系表21优先关系矩阵intpresdence(intop1,intop2){intprecede[7][7]={1,1,0,0,0,1,1,1,1,0,0,0,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,0,0,0,0,0,3,2,2

5、,2,2,2,2,2,2,0,0,0,0,0,2,4};returnprecede[op1][op2];}22关于带括号的表达式的计算-（+#341*6)/3#operatorstackoperandstackexpression???push(data);Push(oper);getResult();checkIn(oper);23栈的应用：抓狂的老鼠问题分析鼠目寸光—只能看到眼前的东西面临多种选择25解决方案前进，还是前进汲取教训，不犯重复的错误具体：依次探查所有可能的没有被探查过的方向对探查过的位置进行标记记录走过的路，以便回头26

6、数据结构设计地图数组intmap[i][j];（0-通，1-不通）过往路径记录（栈）方向：1-2-3-4：<0,1>，<1,0>，<0-1><-10>,27算法设计走一步，记一步。方向试探前进push(current)无法前进current=pop()28求解迷宫中一条路径的方法：从入口开始，对每个当前位置沿（E,S,W,N)四个方向逐一进行试探，当选定一个可通行的方向后，把当前所在位置及所选的方向记录下来，然后从下一个位置开始继续探索；若在当前位置探索不到可通行的方向，则沿原路一步一步退回来，每后退一步，接着在该点试尚未试过的一个方

7、向。如此重复直到到达出口。用一个栈记录走过的位置，栈中每个元素包括三项，分别记录当前位置的行坐标、列坐标以及在该位置上所选的方向（即directon数组的下标值）。29在某一位置（i,j)进行试探:N(i-1,j)w(i,j-1)(i,j)E(i,j+1)S(i+1,j)drection[4][2]令k取0,1,2,3之一，则试探位置为：g=i+direction[k][0];h=j+direction[k][1];303132队列部分的内容：队列的引入与抽象数据类型定义队列的存储结构与实现队列的应用33队列的特点队列是一种特殊的线性表

8、，只允许在表的一端有插入操作，而在另一端有删除操作。队头：允许删除的这一端叫队列的头。队尾：允许插入的这一端叫队列的尾。空队列：当队列中没有任何元素时，称为空队列。进队/出队：队列的插入操作通