数据结构第3章栈和队列合编.ppt

第三章 栈和队列 【课前思考】 1. 什么是线性结构？ 2. 你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,…,n 的次序往上叠的，那么使用时候的次序应是什么样的？ 3. 在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？ 第三章 栈和队列 栈和队列与线性表相比，是限定性的线性表结构。 栈的特点：栈必须按“后进先出”的规则进行操作 队列特点：必须按“先进先出”的规则进行操作。 　 插 入 删 除　　线性表： Insert (L ,i ,x)　　Delete (L , i)　　　　　 　 (1≤i≤n+1)　 　(1≤i≤n)　　栈：　　Insert (L, n+1 ,x) 　Delete (L , n)　　　队列：　Insert (L, n+1 ,x)　 Delete (L ,1) 本章小结 课后习题 【基础知识题】 3.2.4 表达式求值问题 任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成。 其中 操作数：常数、标识符 运算符：算术运算符、关系运算符和逻辑运算符 基本界限符：左右括弧、表达式结束符等 以简单的二元运算符的算术表达式 二元表达式： 操作数1 （S1）操作符（OP）操作数2 （S2） 其中：操作数可以是简单变量，也可以是表达式； 而简单变量可以是标识符，也可以是无符号整数。 问题分析： 由于算术运算的规则是：先乘除后加减、先左后右和先括弧内后括弧外，不按其中运算符出现的先后次序。 那么怎么办？其中一个方法是先将它转换成另一种形式。 在计算机中，对这种二元表达式可以有三种不同的标识方法。 　　假设 Exp = S1 + OP + S2 则称 OP + S1 + S2 为表达式的前缀表示法（简称前缀式） 　称 S1 + OP + S2 为表达式的中缀表示法（简称中缀式） 　称 S1 + S2 + OP 为表达式的后缀表示法（简称后缀式） 例如： 　　若 ????????????????????????????　 则它的 　　前缀式为： ?????????????????????　　中缀式为： ?????????????????????　　后缀式为： ????????????????????? 综合比较它们之间的关系可得下列结论： 　1．三式中的 “操作数之间的相对次序相同”； 　2．三式中的 “运算符之间的的相对次序不同”； 　3．中缀式丢失了括弧信息，致使运算的次序不确定； 　4．前缀式的运算规则为：连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式； 　5．后缀式的运算规则为：　　·运算符在式中出现的顺序恰为表达式的运算顺序；　　·每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式； 　　以下就分如何按后缀式进行运算和如何将原表达式转换成后缀式两个问题进行讨论。 如何按后缀式进行运算？　　　　“先找运算符，后找操作数。” 如： 后缀式 参看动画flash3-3-5 运算过程为： 对后缀式从左向右“扫描”，遇见操作数则暂时保存，遇见运算符即可进行运算；此时参加运算的两个操作数应该是在它之前刚刚碰到的两个操作数，并且先出现的是第一操作数，后出现的是第二操作数。 由此可见，在运算过程中保存操作数的结构应该是个栈。 如何由原表达式转换成后缀式？　 先分析一下原表达式和后缀式两者中运算符出现的次序有什么不同。 ???? 例一　　原表达式： ?????????????????????　　　后缀式： ????????????????????? ???? 例二　　原表达式： ????????????????????　　　后缀式： ????????????????????? 先分析一下原表达式和后缀式两者中运算符出现的次序有什么不同。 ???? 例一　　原表达式： ?????????????????????　　　后缀式： ????????????????????? ???? 例二　　原表达式： ????????????????????　　　后缀式： ????????????????????? 给每个运算符赋以一个优先数的值，如下所列：　　　运算符 ????????????