武汉理工大学-信息工程学院-数据结构-ppt-课件ch03-2-栈和队列2-栈的应用

第3章栈和队列-栈的应用数据结构讲义信息工程学院魏洪涛Email:[e-mail]迷宫求解右下左上演示求迷宫路径算法的基本思想若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。求迷宫中一条从入口到出口的路径的算法设定当前位置的初值为入口位置；do{1，若当前位置可通，则将其纳入栈中2，若当前位置不可通2.1若栈不空且栈顶位置尚有其他方向未被探索，则转向其它方向2.2若栈不空但栈顶位置的四周均不可通，则将当前位置从栈中删除。}while(栈不空)若当前位置可通//用一个函数判断是否可通｛1.1，将当前位置插入栈顶并留下标记；//调用入栈操作和留下标记函数1.2，if(该位置是出口位置)算法结束；else切换当前位置的东邻方块为新的当前位置；//调用函数取得下一块为当前位置若当前位置不可通{2.1if(栈不空且栈顶位置尚有其它方向未被探索)设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；2.2if(若栈不空但栈顶位置的四周均不可通）｛删去栈顶位置；若栈不空，则重新测试新的栈顶位置,直至找到一个可通的相邻块或出栈至栈空；｝迷宫求解示例代码Ch3_maze.c表达式计算例如：3*（7–2）（1）要正确求值，首先了解算术四则运算的规则：a.从左算到右b.先乘除，后加减c.先括号内，后括号外由此，此表达式的计算顺序为：3*（7–2）=3*5=15（2）根据上述三条运算规则，在运算的每一步中，对任意相继出现的运算符1和2，都要比较优先权关系。（3）算法思想：•设定两栈：操作符栈OPTR，操作数栈NUM•栈初始化：置栈OPTR和栈NUM为空；•当字符没读取完毕或者操作符栈不空：•当字符没读取完毕，而且该字符是操作数，则直接把该字符入栈•当栈空或者操作符栈顶元素，操作符入栈•右括号遇到左括号，栈OPTR退括号•当字符读取完毕或者操作符栈顶元素，OPTR栈退栈得到一个操作符，NUM栈退栈两次得到两个操作数，计算，把结果压入NUM栈表达式计算的操作演示表达式计算示例代码ch3_express.c皇后问题皇后问题的操作演示作业&实验:栈与队列的应用假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序任意，即([]())或[([][])]等都为正确的格式，而[(])为不正确的格式。利用栈编程序检验表达式中的括号是否合法。可以利用示例程序中栈的实现，作业只写自己的代码。利用已有代码做完整实验。实验报告中写主要代码，调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析，结果分析，算法的时空分析和改进设想，经验与体会等。