数据结构第3章栈和队列栈.pptxVIP

数据结构 Data Structures;;§3.1 栈的类型定义;§3.1 栈的类型定义;§3.1 栈的类型定义;栈示意图 ;栈的相关概念 ;栈与一般线性表有什么不同 ;栈的相关概念 ;思考题 一个栈的入栈序列是a, b, c, d, e，则栈的不可能的输出序列是（ ）。 ;栈的抽象数据类型定义 ;栈的物理存储 栈的物理存储可以用顺序存储结构，也可用链式存储结构。相应地，栈的存储方式也分为两种，即顺序栈和链栈。 ;顺序栈的定义 ;栈顶指针和栈中元素之间的关系 ;栈在抽象类型中的几种操作举例 ;栈在抽象类型中的几种操作举例 ;栈在抽象类型中的几种操作举例 ;栈在抽象类型中的几种操作举例 ;栈的链式存储结构 栈的链式存储结构称为链栈，它是运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在表头进行操作，故没必要附加头结点，栈顶指针就是链表的头指针。 ;栈的链式存储结构 ;链栈的类型说明如下 ;链栈的基本操作 ;链栈插入新栈顶元素（即入栈） ;链栈删除栈顶元素（即出栈） ;1.数制转换 2.括号匹配的检验 3.行编辑程序 4.迷宫求解 5.表达式求值;数制转换 ;数制转换 ;数制转换 ;括号匹配的检验 ;括号匹配的检验 ;算法思想 ;括号匹配的检验 ;行编辑程序 ;行编辑程序 ;行编辑程序 ;§3.3 栈的应用举例;迷宫求解 ;迷宫求解 ;?;求迷宫中一条从入口到出口的路径的算法 ;求迷宫中一条从入口到出口的路径的算法 ;表达式求值;表达式求值;表达式求值;§3.3 栈的应用举例;§3.3 栈的应用举例;表达式的三种标识方法;;如何从后缀式求值;如何从原表达式求得后缀式;从原表达式求得后缀式的规律为;从原表达式求得后缀式的规律为;从原表达式求得后缀式的规律为;§3.4 栈与递归的实现;例：设计一个乘法器，可以计算出两个数相乘的乘积。但是此时计算机不能提供乘法运算（仅知道任何数乘 1，其值不变），则唯一可以使用的运算方式就是加法运算。;使用递归的一个重要问题 一个递归的求解问题必然包含有终止递归的条件，当满足一定条件时就终止向下递归，从而使问题得以解决。;使用递归的一个重要问题 解决递归问题的算法称递归算法，在递归算法中需要根据递归条件直接或间接地调用算法本身，当满足某种条件时结束递归调用。当然对于一些简单的递归问题，很容易把它转换为循环问题解决，从而使编写出的算法更为有效。;实现递归;实现递归;多个函数嵌套调用的规则是;实现递归;例：采用递归算法求解正整数n的阶乘(n!) ;进行f (4)调用的系统栈的变化状态 ;进行f (4)调用的系统栈的变化状态 ;例：最大公因子问题 数学上利用辗转相除法解决。同时此种方法也称为欧几理德定理，其定义为：;写出求解最大公因子的递归函数为;汉诺( hanoi )塔问题 汉诺塔问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。;汉诺( hanoi )塔问题 假设有三个分别命名为X、Y、Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大编号为1、2、…n的圆盘。现要求将X轴上的n个圆盘移到塔座Z上并仍按同样的顺序叠排，圆盘移动时必须遵循下列规则： 1）每次只能移动一个圆盘； 2）圆盘可以插在X、Y、Z的任一塔座上； 3）任何时刻都不能将一个较大的圆盘压在较 小的圆盘上。;§3.4 栈与递归的实现;§3.4 栈与递归的实现;§3.4 栈与递归的实现;§3.4 栈与递归的实现;§3.4 栈与递归的实现;§3.4 栈与递归的实现;§3.4 栈与递归的实现;§3.4 栈与递归的实现;§3.4 栈与递归的实现;§3.4 栈与递归的实现;§3.4 栈与递归的实现;汉诺塔递归求解 移动n个盘子的汉诺塔问题需要移动的盘子数是n-1个盘子的汉诺塔问题需要移动的盘子数的2倍加1。 h(n) =2h(n-1)+1 =2h(n-1)+1 =2(2h(n-2)+1)+1 =22h(n-2)+2+1 =23h(n-3)+22+2+1 =……