数据结构第七讲.ppt

1、复习上节课的内容， 3.1堆栈3.1.1堆栈定义和操作3.1.2堆栈顺序存储结构和基本操作的实现3.1.3堆栈链存储结构和基本操作的实现3.2堆栈应用3.2.1中缀表达式3.2.2中缀表达式转换为等价后缀表达式3.2.3后缀表达式和求值3.3堆栈和递归3.3.1递归和递归程序设计3.2递归程序的执行过程3.3.3递归的应用示例3.4队列3.4.1队列3的定义和操作队列和基本操作的实现3.4.3队列的链式存储结构和基本操作的实现3.4.4队列的应用示例本章摘要， 3.1堆栈3.1.1堆栈定义和操作3.1.2堆栈顺序存储结构和基本操作的实现3.1.3堆栈链存储结构和基本操作的实现3.2堆栈应用3.

2、2.1中缀表达式3.2.2中缀表达式转换为等价后缀表达式3.2.3后缀表达式和求值3.3堆栈和递归3.3.1递归和递归程序设计3.2递归程序的执行过程3.3.3递归的应用示例3.4队列3.4.1队列3的定义和操作队列和基本运算的实现3.4.3队列的链式存储结构和基本运算的实现3.4.4队列的应用实例本章总结如下：第一，问题求解，第二，算法编写：以n的阶乘为例：的定义是：n的阶乘等于n的阶乘乘以n-1，并且公式表明，根据定义，相应的递归函数int fact (int n)如果(n=0)返回1可以自然地编写； 否则返回(n * fact(n-1)；如果一个对象部分地包含自己或者自己定义自己，那么它

3、就是递归的。3.3.1递归和递归程序设计，递归算法要点：(1)问题与其自身的子问题相似，且定义项在定义中的应用规模较小。(2)定义的术语在最小尺度上有直接解。设计递归算法的方法是：(1)找到一种方法将问题转化为原问题的子问题(例如n！=n*(n-1)！).(2)设计递归出口并确定递归终止条件(例如，求解n！当n=1时，n！=1).递归算法编写的要点和方法，例3-3使用递归算法求解斐波那契数列的第n项的值。长纤维(int n)int f；if(n=1n=2)f=1；否则f=fib(n-1)fib(n-2)；返回f；本章要点， 3.1堆栈3.1.1堆栈定义和操作3.1.2堆栈顺序存储结构和基本操作

4、的实现3.1.3堆栈链存储结构和基本操作的实现3.2堆栈应用3.2.1中缀表达式3.2.2中缀表达式转换为等价后缀表达式3.2.3后缀表达式和求值3.3堆栈和递归3.3.1递归和递归程序设计3.2递归程序的执行过程3.3.3递归的应用示例3.4队列3.4.1队列3的定义和操作队列和基本操作的实现3.4.3队列的链式存储结构和基本操作的实现3.4.4队列的应用示例3.4.4本章总结，3.3.2递归程序的执行过程(1)，为3！ 以一个例子来说明执行调用的过程，如下图所示。递归函数的递归过程：递归进入该层(ii 1层)时，系统需要做三件事：(1)保留该层的参数和返回地址(将所有实际参数、返回地址等信

5、息传递给被调用函数保存)；(2)给低级参数赋值(为被调用函数的局部变量分配存储区域)；(3)将程序转移到调谐功能的入口。在从被调用函数返回到调用函数之前，递归回退(ii 1层)系统还应完成三项任务：(1)保存被调用函数的计算结果；(2)恢复上层参数(释放已调功能的数据区)；(3)根据被调用函数保存的返回地址，将控制权转移给调用函数。，3.3.2递归程序的执行过程(2)，本章要点， 3.1堆栈3.1.1堆栈定义和操作3.1.2堆栈顺序存储结构和基本操作的实现3.1.3堆栈链存储结构和基本操作的实现3.2堆栈应用3.2.1中缀表达式3.2.2中缀表达式转换为等价后缀表达式3.2.3后缀表达式和求值3.3堆栈和递归3.3.1递归和递归程序设计3.2递归程序的执行过程3.3.3递归的应用示例3.4队列3.4.1队列3的定义和操作队列和基本操作的实现3.4.3队列的链式存储结构和基本操作的实现3.4.4队列的应用示例本章摘要，河内塔问题：有三个标有A、B和C的针，A针上有N个板，每个板都比另一个板小。 需要将A针上的所有板移动到C针。移动规则如下：1 .一次只能移动一个盘子。2.在移动过程中，大盘总是在小盘下面。3.在移动过程中，板可以放在任何针上。如果汉诺威塔的演示是n1，直接移动它，否则：1。用C销过渡，并将A销上的n1个板移动到