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