_栈和队列分析.ppt

栈的应用举例（二）：表达式求解 一个关键问题：如何将中缀表达式转换为后缀表达式？ 答案：可以通过设置一个运算符栈来完成转换。 转换规则：从左到右遍历中缀表达式的每个数字和符号，并做以下操作： 若是数字就输出，即成为后缀表达式的一部分； 若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出（注：如果是因右括号出栈，直到出到第一个遇到的左括号为止，括号只出栈不输出），并将当前符号进栈。 如此继续，一直到最终输出后缀表达式为止。 栈的应用举例（二）：表达式求解 将中缀表达式：9+(3-1)×3+10/2，转换为后缀表达式 + 9 - （ + 9 3 1 + 9 3 1 - + 9 3 1 – 3 *+ 9 3 1 – 3 *+10 2/+ 9 3 1 – 3 *+10 / + / + 9 3 1 – 3 *+10 2 + （ 9 3 + 空栈 运 算 符 栈 * 9 3 1 - 3 + 将十进制数转换为指定数制的数，此过程可以采用求余法进行，用这个十进制数作为被除数，用指定的数基作除数，连续求余，得出的余数依由个位到十位等的顺序组成新数，即得指定数制的数。 * 中缀表达式：运算符放在两个运算对象中间; 在中缀表达式的情况下求值，既要考虑括号，优先级，还要考虑操作出现的先后顺序。但是，作为计算机，其计算过程就显的比较复杂，对于一个中缀表达式，需要不停地对表达式进行多次遍历，来查找相应的计算的信息。这样从算法复杂度上来说，是不可取的。后缀表达式：不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行（不再考虑运算符的优先规则，如：2 1 + 3 * * 求解迷宫问题的简单方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行探索，直到所有可能的通路都探索到为止。为避免走回到已经进入的点（包括已在当前路径上的点和曾经在当前路径上的点），凡是进入过的点都应做上记号。 * 求解迷宫问题的简单方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行探索，直到所有可能的通路都探索到为止。为避免走回到已经进入的点（包括已在当前路径上的点和曾经在当前路径上的点），凡是进入过的点都应做上记号 * 递归最大的优势就是，代码更简洁清晰，逻辑性强，可读性更好。当然递归函数也有自身缺点,突出缺陷是在调用自身函数时不停开辟存储空间,在占用存储空间的同时又耗费时间,简而言之,大量占用资源,运行速度相对缓慢。在小程序中使用并不会突显其缺点,在大程序中,要谨慎使用,如果使用递归请考虑开辟外存空间来降低内存消耗,同时又降低对运行速度的影响。递归算法的执行过程分递推与回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。在回归阶段，当获得最简单的情况后，逐级返回，依次获得稍复杂问题的解。递推是递归的一个阶段，递归包含着递推。 * 递归过程退回的顺序是它前行顺序的逆序。在退回过程中，可能要执行某些动作，包括恢复在前行过程中存储起来的某些数据。这种存储某些数据，并在后面又以存储的逆序恢复这些数据，以提供之后使用的需求，显然很符合栈这样的数据结构，因此，编译器使用栈实现递归就没什么好惊讶的了。简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。 * 简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。 * 第三章 栈和队列(1) 郭大庆 电子科技大学生命科学与技术学院 神经信息教育部重点实验室 约瑟夫问题 15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。 第三章 栈和队列 本章学习两种特殊的线性数据结构，它们特殊在定义的操作不同，即插入和删除操作只能在线性表的两端进行。 只能在一端进行的----- 栈 分别在两端进行的----- 队列 线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x)