Hu JunfengHu JunfengHu JunfengHu Junfeng栈的应用 与 队列2008/03/211Hu JunfengHu JunfengHu JunfengHu Junfeng从原表达式求得后缀式的规则1) 设立操作符栈2)设表达式的结束符为“#”, 设运算符栈的栈底为“#”；3)若当前字符串是个操作数 则直接发送给后缀式。否则：若当前运算符的优先数高于栈顶运算符，则进栈；否则：退出栈顶运算符发送给后缀式； goto step3; 4) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。相遇则自动取消。2Hu JunfengHu JunfengHu JunfengHu Junfeng21+运算符优先关系表3Hu JunfengHu JunfengHu JunfengHu Junfeng优先关系矩阵int presdence ( int op1, int op2) int precede77=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,2,2,2,2,2,2, 0,0,0,0,0,2,4;return precedeop1op2; 4Hu JunfengHu JunfengHu JunfengHu Junfeng从中缀表达式求得后缀式的规则1) 设立操作符栈2)设表达式的结束符为“#”, 设运算符栈的栈底为“#”；3)若当前字符串是个操作数 则直接发送给后缀式。否则：若当前运算符的优先数高于栈顶运算符，则进栈；否则：退出栈顶运算符发送给后缀式； goto step3; 4) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。相遇则自动取消。5Hu JunfengHu JunfengHu JunfengHu Junfeng中缀表达式转换成后缀表达式3 * ( 7 + 3 * 6 / 2 5 ) #栈顶栈外栈顶 栈顶元素push();否则pop();# 优先级最低。push();pop();6Hu JunfengHu JunfengHu JunfengHu Junfeng后缀表达式的求值过程。 使用一个存放算子（运算分量）的 栈。 求值过程顺序扫描后缀表达式，每 次遇到算子便将它推入栈中； 遇到运算符时，就从栈中弹出两个 整数(算子)进行计算，而后再把结 果推入栈中。 到扫描结束时，留在栈顶的整数就 是所求表达式的值。4 12 3+ 3 5 * / -7Hu JunfengHu JunfengHu JunfengHu Junfeng关于带括号的表达式的计算-（+#341* 6 ) / 3 #operator stack operand stackexpression?push(data); Push(oper); getResult();checkIn (oper);8Hu JunfengHu JunfengHu JunfengHu Junfeng关于表达式的几个愚昧的问题 为什么要先乘除后加减 为什么说中缀表达式的运算顺序是不确定的 为什么说一个合法的前缀或后缀表达式的运算顺 序一定是唯一确定的。 中缀表达式和后缀表达式是一一对应的吗？9Hu JunfengHu JunfengHu JunfengHu Junfeng栈的应用：抓狂的老鼠Hu JunfengHu JunfengHu JunfengHu Junfeng问题分析 鼠目寸光 只能看到眼前的东西 面临多种选择 有无法抗拒的诱惑11Hu JunfengHu JunfengHu JunfengHu Junfeng解决方案 前进，还是前进 汲取教训，不犯重复的错误 具体： 依次探查所有可能的没有被探查过的方向 对探查过的位置进行标记 记录走过的路，以便回头12Hu JunfengHu JunfengHu JunfengHu Junfeng数据结构设计 地图数组int mapij;（0-通，1-不通） 过往路径记录（栈） 方向：1-2-3-4： ， , 13Hu JunfengHu JunfengHu JunfengHu Junfeng算法设计 走一步，记一步。 方向试探 前进 push (current) 无法前进 current = pop ( )14Hu JunfengHu JunfengHu JunfengHu Junfeng求解迷宫中一条路径的方法：从入口开始，对每个当前位置沿（E,S,W,N)四 个方向逐一进行试探，当选定一个可通行的方向后 ，把当前所在位置及所选的方向记录下来，然后从 下一个位置开始继续探索；若在当前位置探索不到 可通行的方向，则沿原路一步一步退回来，每后退 一步，接着在该点试尚未试过的一个方向。如此重 复直到到达出口。 用一个栈记录走过的位置，栈中每个元素包括三 项，分别记录当前位置的行坐标、列坐标以及在该 位置上所选的方向（即directon数组的下标值）。 15Hu JunfengHu JunfengHu JunfengHu Junfeng在某一位置（i, j)进行试探:N (i-1,j) w (i,j-1) (i, j) E (i,j+1) S (i+1,j) drection42令k取0,1,2,3之一，则试探位置为：g = i + directionk0; h = j + directionk1;16Hu JunfengHu JunfengHu JunfengHu Junfeng队列部分的内容： 队列的引入与抽象数据类型定义 队列的存储结构与实现 队列的应用17Hu JunfengHu JunfengHu JunfengHu Junfeng队列的特点队列是一种特殊的线性表，只允许在表的一端有插入操作，而 在另一端有删除操作。队头：允许删除的这一端叫队列的头。队尾：允许插入的这一 端叫队列的尾。空队列：当队列中没有任何元素时，称为空队列。进队/出队：队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。18Hu JunfengHu JunfengHu JunfengHu Junfeng队列的基本概念：队列也称作先进先出表（First In First Out，FIFO表）。支持队尾插入，队头删除操作。a0 a1 a2 an-1入队列队 头队 尾出队列队列的示意图19Hu JunfengHu JunfengHu JunfengHu Junfeng队列ADTADT Queue isoperationsQueue createEmptyQueue (void ); /创建一个空队列。int isEmptyQueue ( Queue qu ); / 判队列qu是否为空队列。void enQueue ( Queue qu, DataType x );/往队列qu尾部插入一个值为x的元素。void deQueue ( Queue qu ); /从队列qu头部删除一个元素。DataType frontQueue ( Queue qu ); /求队列qu头部元素的值。end ADT Queue 20Hu JunfengHu JunfengHu JunfengHu Junfeng基于顺序存储结构的队列实现a1a2a3a4anfrontrearenQueue: rear +;qBufferrear = inData; deQueue: outData = qBufferrear;rear +; 21Hu JunfengHu JunfengHu JunfengHu Junfeng基于环形存储结构的队列实现a1a2a3a4anfrontrearmod MAXSIZE enQueue: rear = (rear + 1)%MAXSIZEqBufferrear = inData; deQueue: outData = qBufferrear;rear = (rear + 1)%MAXSIZE ; 22Hu JunfengHu JunfengHu JunfengHu Junfeng基于环形存储结构的队列实现把数组paqu-qMAXNUM从逻辑上看成一个环，这种队列称为环 形队列。当表中已有MAXNUM 1个结点时，如果还要插入，paqu-r和paqu-f就会重合，而这与空队列的情形相混。为区分空队列与满队列两种情况的环形队列，一般是牺牲队列 中的一个结点，当队列中已有MAXNUM1个结点时就称满，再要 插入就发生溢出.23Hu JunfengHu JunfengHu JunfengHu Junfengpaqu-rpaqu-f图(a) 空队列a1a2a7 a6a5a4a3paqu-fpaqu-r图(b) 队列满，判断 (paqu-r +1) = = paqu-f环形队列24Hu JunfengHu JunfengHu JunfengHu Junfeng顺序结构队列的类型定义25Hu JunfengHu JunfengHu JunfengHu Junfeng顺序结构队列的操作定义（ADT）26Hu JunfengHu JunfengHu JunfengHu Junfeng顺序结构队列操作的实现27Hu JunfengHu JunfengHu JunfengHu Junfeng顺序结构队列 操作的实现28Hu JunfengHu JunfengHu JunfengHu Junfeng顺序结构队列操作的实现29Hu JunfengHu JunfengHu JunfengHu Junfeng链接结构队列的数据结构设计尾部插入 头部删除。r - link = newNode; r = newNode; newNode.link = NULL;ptr = f;f = f - next; free ( ptr );空链表？30Hu JunfengHu JunfengHu JunfengHu Junfeng链接结构队列操作的实现31Hu JunfengHu JunfengHu JunfengHu Junfeng队列的应用 缓冲区与随机过程 用于匹配不同速率需求与服务 用于格式转换a1a2a3a4an稳定的服务提供随机到来的服务请求32Hu JunfengHu JunfengHu JunfengHu Junfeng队列的应用 理发店问题模拟仿真33Hu JunfengHu JunfengHu JunfengHu Junfeng理发店问题模拟仿真（问题分析） K个理发师 一条长凳（L个位置） n多顾客 顾客随机来到，服务时间也不一样 能否通过计算机仿真来得到：平均等待时间？ 服务策略是否最优？34Hu JunfengHu JunfengHu JunfengHu Junfeng三种不同的策略 先到先服务 小人物优先 时间片轮转服务35Hu JunfengHu JunfengHu JunfengHu Junfeng问题： 顾客如何表达？ 顾客流如何表达？ 模拟服务流程如何实现？36Hu JunfengHu JunfengHu JunfengHu Junfeng队列的应用 理发店问题模拟仿真C1C2C3Cnstruct int inTime;int servTime;int waitTime; C