《栈的应用》PPT课件.ppt

栈的应用 与 队列,2009/03/17,2,内容：,作业讲评 表达式计算 队列 队列应用,3,链接结构栈:,4,5,bbs,6,7,8,删帖：,9,10,回帖：,11,关于编程环境,微软学生资源： /m_directdownload/introduction.aspx,12,关于网络编程,2-3人 / vs2008 课堂报告 + 4分,13,栈的应用 表达式求值（续）,表达式的三种标识方法: Exp = a b + (c d / e) f 前缀式: + a b c / d e f 中缀式: a b + c d / e f 后缀式: a b c d e / f + 中缀式丢失了括弧信息，致使运算的次序不能先确定。,14,关于表达式的几个问题,为什么要先乘除后加减? 为什么计算中要把中缀表达式转换为后缀（RPN）、前缀表达式? 为什么说一个合法的前缀或后缀表达式的运算顺序一定是唯一确定的?,15,后缀式的运算,后缀式的运算规则为: 运算符在式中出现的顺序恰为 表达式的运算顺序; 每个运算符和在它之前出现，且紧靠它的两个操作数构成一个最小表达式（算子）。,例： 31 * ( 5 22 ) + 70 31 5 22 - * 70 +,16,后缀表达式的求值过程。,使用一个存放算子（运算分量）的栈。 求值过程顺序扫描后缀表达式，每次遇到算子便将它推入栈中； 遇到运算符时，就从栈中弹出两个整数(算子)进行计算，而后再把结果推入栈中。 到扫描结束时，留在栈顶的整数就是所求表达式的值。,+ 3 5 * / -,17,/by 00720106 顾森,18,19,从中缀表达式求得后缀式的规则,1) 设立操作符栈 2)设表达式的结束符为“#”, 设运算符栈的栈底为“#”； 3)若当前字符串是个操作数 则直接发送给后缀式。 否则：若当前运算符的优先数高于栈顶运算符，则进栈； 否则：退出栈顶运算符发送给后缀式； goto step3; 4) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。相遇则自动取消。,20,中缀表达式转换成后缀表达式 3 * ( 7 + 3 * 6 / 2 5 ) #,栈顶栈外,栈顶栈外,#,*,(,+,*,/,-,！,操作数：放过。 操作符：与栈顶元素比较， 优先级 栈顶元素 push(); 否则 pop(); # 优先级最低。,push();,pop();,21,运算符优先关系表,22,优先关系矩阵,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; ,23,关于带括号的表达式的计算,* 6 ) / 3 #,operator stack,operand stack,expression,?,?,?,push(data); Push(oper); getResult();,checkIn (oper);,栈的应用：抓狂的老鼠,25,问题分析,鼠目寸光 只能看到眼前的东西 面临多种选择,26,解决方案,前进，还是前进 汲取教训，不犯重复的错误 具体： 依次探查所有可能的没有被探查过的方向 对探查过的位置进行标记 记录走过的路，以便回头,27,数据结构设计,地图数组int mapij;（0-通，1-不通） 过往路径记录（栈） 方向：1-2-3-4： ， ， ,28,算法设计,走一步，记一步。 方向试探 前进 push (current) 无法前进 current = pop ( ),29,求解迷宫中一条路径的方法： 从入口开始，对每个当前位置沿（E,S,W,N)四个方向逐一进行试探，当选定一个可通行的方向后，把当前所在位置及所选的方向记录下来，然后从下一个位置开始继续探索；若在当前位置探索不到可通行的方向，则沿原路一步一步退回来，每后退一步，接着在该点试尚未试过的一个方向。如此重复直到到达出口。 用一个栈记录走过的位置，栈中每个元素包括三项，分别记录当前位置的行坐标、列坐标以及在该位置上所选的方向（即directon数组的下标值）。,30,在某一位置（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;,31,32,33,队列部分的内容：,队列的引入与抽象数据类型定义 队列的存储结构与实现 队列的应用,34,队列的特点,队列是一种特殊的线性表，只允许在表的一端有插入操作，而在另一端有删除操作。 队头：允许删除的这一端叫队列的头。 队尾：允许插入的这一 端叫队列的尾。 空队列：当队列中没有任何元素时，称为空队列。 进队/出队：队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。,35,队列的基本概念： 队列也称作先进先出表（First In First Out，FIFO表）。支持队尾插入，队头删除操作。,a0 a1 a2 an-1,入队列,队头,队尾,出队列,队列的示意图,36,队列ADT,ADT Queue is operations Queue 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,37,基于顺序存储结构的队列实现,front,rear,enQueue: rear +; qBufferrear = inData; ,deQueue: outData = qBufferfront; front +; ,38,基于环形存储结构的队列实现,front,rear,mod MAXSIZE,enQueue: rear = (rear + 1)%MAXSIZE qBufferrear = inData; ,deQueue: outData = qBufferrear; front = (front + 1)%MAXSIZE ; ,39,基于环形存储结构的队列实现,把数组paqu-qMAXNUM从逻辑上看成一个环，这种队列称为环形队列。 当表中已有MAXNUM 1个结点时，如果还要插入， paqu-r和paqu-f就会重合，而这与空队列的情形相混。 为区分空队列与满队列两种情况的环形队列，一般是牺牲队列中的一个结点，当队列中已有MAXNUM1个结点时就称满，再要插入就发生溢出.,40,环形队列,41,顺序结构队列的类型定义,42,顺序结构队列的操作定义（ADT）,43,顺序结构队列操作的实现,44,顺序结构队列 操作的实现,45,顺序结构队列操作的实现,46,链接结构队列的数据结构设计,尾部插入 头部删除。,r - link = newNode; r = newNode; newNode.link = NULL;,ptr = f; f = f - next; free ( ptr );,空链表？,47,链接结构队列操作的实现,48,队列的应用 缓冲区与随机过程,用于匹配不同速率需求与服务 用于格式转换,稳定的服务提供,随机到来的服务请求,49,队列的应用 理发店问题模拟仿真,50,理发店问题模拟仿真（问题分析）,K个理发师 一条长凳（L个位置） n多顾客 顾客随机来到，服务时间也不一样 能否通过计算机仿真来得到：平均等待时间？ 服务策略是否最优？,51,三种不同的策略,先到先服务 小人物优先 时间片轮转服务,52,问题：,顾客如何表达？ 顾客流如何表达？ 模拟服务流程如何实现？,53,队列的应用 理发店问题模拟仿真,struct int inTime; int servTime