栈及其应用课件

栈的应用梁音地球物理与空间信息学院地球信息科学与技术系栈的概念栈(stack)就是线性表特殊的线性表一般线性表：插入和删除操作可以对线性表的任一元素进行栈：插入和删除操作只能在线性表的一端进行，而另一端是固定的。栈的概念进栈元素的顺序和出栈元素的顺序是相反的栈的很多应用都是基于这一点栈的应用数制转换括号匹配表达式求值路径搜索递归数制的转换如何将十进制数字N转换成d进制数字算法的基本原理N=(Ndivd)×d+Nmodd典型的输入序列和输出序列是相反的数制的转换算法描述：(以8进制数的转换为例)(1)初始化一个空栈S，并输入十进制数N(2)N是否等于0？是的，转到(3)；不是push(S,N%8)，N=N/8(3)栈S是否为空？不是，pop(S,e)，打印e的值；否则，结束。栈的应用数制的转换是栈最典型的应用：输入序列和输出序列是反序的。但是并非关于栈的所有应用都是这样有着严格的反序关系。很多栈的高级应用都是利用栈来实现某些状态的还原。(路径搜索和递归)括号匹配假设表达式中允许包含两种括号：[]和(),并允许这两种括号随意嵌套比如：([]())或者[([][])]都是正确的格式而[(])或(()]等等都是不正确的格式括号匹配那么如何判断一个括号表达式是否合法呢？利用栈来实现因为最后进来的括号是最需要进行匹配的那一个括号匹配算法描述：(1)表达式是否结束？(2)是的，栈S是否空？是的，输出合法表达式，否则，括号表达式不合法；(3)否，该括号是“[”或者“(”吗？是的，进栈S，否则，栈S出栈；括号匹配算法：(4)出栈的元素和当前表达式中的括号是否匹配？是的，跳到(1)，否则，表达式不合法。括号匹配假设现在表达式中只要是含有成对出现的括号，就认为是合法的表达式？比如：([]())或者[([][])]或者[(])都是合理的，而(()]是不合理的。算法该如何设计？行编辑程序一个简单的行编辑程序：接受用户从终端输入程序和数据，并存入用户数据区。用户在终端上的输入不能保证不出差错一个字符一个字符的存入数据区显然是不合适的。行编辑程序一个简单的行编辑程序：加入两个修改符号：#：表示前一个输入的字符无效（校正前一个输入字符）；@：表示当前行中的字符都无效（退行符）行编辑程序一个简单的行编辑程序：那应该如何进行字符的接受呢？较好的方法是：建立一个缓冲区，接受用户输入的一行字符，确认无误后再逐行存入用户数据区。行编辑程序一个简单的行编辑程序：那么这个缓冲区用什么样的数据结构呢？因为需要处理前面的一个字符或者一个字符行无效所以，栈是比较合适的行编辑程序一个简单的行编辑程序：将用户输入的字符先进栈；如果输入的字符是#，则，出栈一个字符；如果输入的字符是@，则，清空栈。表达式求值表达式求值是程序设计语言编译中的一个最基本问题它是栈应用的又一个典型的例子算符优先法表达式求值假设该表达式中只含有加、减、乘和除法运算，可以含有括号；运算规则：先乘除，后加减从左向右进行先括号内的，再括号外的表达式求值这里需要启用两个栈来完成这个任务：操作数栈（OPND）运算符栈（OPTR）表达式求值操作数栈（OPND）：存储表达式中的字符、数字或运算结果等。运算符栈（OPTR）：用以寄存运算符。运算符之间的优先关系表。表达式求值基本算法思想：（1）表达式是否结束？是的，OPND栈底元素就是运算结果；（2）否则，当前的输入是字符吗？是的，字符进栈OPND（3）否则，将该运算符和栈OPTR的栈表达式求值顶元素进行比较：A、如果OPTR栈顶元素优先级别低，则将该元素进栈OPTR；B、如果优先级别相等，则OPTR出栈一次；C、如果OPTR栈顶元素优先级别高，则表达式求值OPTR出栈一次，OPND出栈两次，然后进行运算，将结果进栈OPND。读入下一个字符，跳到（1）。迷宫求解入口出口迷宫求解求迷宫从入口到出口的所有路径是一个经典的程序设计问题穷举求解需要在任何位置上都能沿原路返回显然需要一个后进先出的数据结构来保存从入口到当前位置的路径背景资料MarsAutonomy（CarnegieMellonUniversity）ObstaclesAvoidancePathPlanningIntegrationPerceptionandMappingPathPlanningTwotypesofuncertainty:

Theenvironmentswillbeunknownorpartially-known.Thepositiononthesurfacewillbeknownonlyapproximately.TheyusetheD*algorithmToplanpathstothegoal

迷宫求解入口出口迷宫求解想法：从一个位置开始的下一步可以向4个方向前进2314迷宫求解想法：这4个位置有的可通，有的不可通所求解的通路应该是简单路径，所以位置的可通和不可通都是动态的若当前位置不可通，则退到前一可通位置继续搜索迷宫求解退到前一可通位置后要标记前面的不可通的位置简单路径上不能出现重复位置块重复出现的位置块也是不可通的块搜索方向的问题：有时候会大大简化搜索的进程