第三课栈与队列 - 数据结构.pptVIP

第3章 限定性线性表——栈和队列 [教学目标] 　 栈和队列是两种限定性线性表，在编译程序、操作系统等各种软件系统中应用广泛。熟练掌握逻辑、存储结构。 [重点、难点] 要求重点掌握利用栈和队列解决实际问题的方法。 [教学方法] 用栈和队列的典型应用引出栈和队列的抽象数据类型定义、分别用顺序结构和单链表结构实现栈和队列，栈与递归的实现。 2. 表达式求值 1) 无括号算术表达式求值 表达式运算及运算符优先级 3+4*5 # +- */ ** ① 0 1 2 3 ② 置空栈OVS、OPTR 进OVS 读字符W 退OVS顶、次顶，OPTR顶 将T(i)=OVS新顶 进OPTR栈 W是操作符 N 结束 N Y N Y Y Y W=‘#’’ OPTRZ栈空 Y W优先级≤OPTR栈顶优先级 N 无括号算术表达式的处理过程如右图 返回主目录 2) 算术表达式处理规则 规定优先级表； (2) 设置两个栈：OVS(运算数栈)和OPTR(运算符栈)； (3) 自左向右扫描，遇操作符则与OPTR栈顶优先级比较：当前操作符OPTR栈顶则进OPTR栈；当前操作符≤ OPTR栈顶，OVS栈顶、次顶和OPTR栈顶，退栈形成运算T（i）， T（i）进OVS栈。 返回主目录 例：实现A/B↑C+D*E#的运算过程时栈区变化情况 返回主目录 3) 带括号算术表达式 实现算符优先算法时需要使用两个工作栈：一个称作运算符栈operator；另一个称作操作数栈operand。 算法的基本过程如下： A.初始化操作数栈operand和运算符栈operator，并将表达式起始符“#”压入运算符栈； B.读入表达式中的每个字符，若是操作数则直接进入操作数栈operand，若是运算符，则与运算符栈operator的栈顶运算符进行优先权比较，并做如下处理： 返回主目录 ?? (1) 若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进operator栈； (2) 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入θ，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、b进行θ运算后，将运算结果作为中间结果推入operand栈； (3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。 当operator栈的栈顶元素和当前读入的字符均为“#”时，说明表达式起始符“#”与表达式结束符“#”相遇，整个表达式求值完毕。 返回主目录 3.1.4 栈与递归的实现 递归 :在定义自身的同时又出现了对自身的调用。 直接递归函数:如果一个函数在其定义体内直接调用自己，则称直接递归函数。 间接递归函数：如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称间接递归函数。 返回主目录 1.具有递归特性的问题 1）递归定义的数学函数 如二阶Fibonacci数列： Ackerman函数： Fib(n)= 0 若n=0 1 若n=1 Fib(n-1)+Fib(n-2) 其它情况 Ack(m,n)= n+1 当m=0时 Ack(m-1,1) 当m≠0, n=0时 Ack(m-1,Ack(m,n-1)) 当m≠0, n≠0时 Ackerman函数可用一个简单的C语言函数描述: int ack(int m,int n) { if(m==0) return n+1; else if (n==0) return ack(m-1,1); else return ack(m-1, ack(m,n-1)); } 我们在后续章节将要学习的一些数据结构，如广义表、二叉树、树等结构其本身均具有固有的递归特性，因此可以自然地采用递归法进行处理。 2）递归数据结构的处理 3）递归求解方法 许多问题的求解过程可以用递归分解的方法描述，一个典型的例子是著名的汉诺塔问题（hanoi）问题。 n阶Hanoi塔问题：假设有三个分别命名为X,Y和Z的塔座，在塔座X上插有n个直径大小各不相同、从小到大编号为1，2,... ，n的圆盘。现要求将塔座X上的n个圆盘移至塔座Z上，并仍按同样顺序叠排。 （1） 每次只能移动一个圆盘； （2） 圆盘可