第3章限定性线性表.pptVIP

1）消除递归的原因： 第一：有利于提高算法时空性能 第二：无应用递归语句的语言设施环境条件 第三：递归算法是一次执行完 消除递归方法有两类 一类是简单递归问题的转换，对于尾递归和单向递归的算法，可用循环结构的算法替代。 另一类是基于栈的方式，即将递归中隐含的栈机制转化为由用户直接控制的明显的栈。 2) 简单递归的消除 单向递归 单向递归是指递归函数中虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调用函数有关，相互之间参数无关，并且这些递归调用语句处于算法的最后。 例如计算斐波那契数列的递归算法 计算斐波那契数列的递归算法如下： Fib(int n) { if（n= =0||n= =1） return n; /* 递归出口 */ else return Fib(n-1)+Fib(n-2); /* 递归调用 */ } 斐波那齐数列 Fib(N)= 0 n=0 1 n=1 Fib(N-1)+Fib(N-2) n2 Fib(5)递归调用过程示意 Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0) Fib(3) Fib(2) Fib(2) Fib(1) Fib(4) Fib(3) Fib(5) Fib(1) Fib(0) Fib(5)循环调用过程示意图 Fib(5) Fib(3) Fib(1) Fib(4) Fib(2) Fib(0) 计算斐波那契数列的非递归算法(1) int Fib(int n): { int x, y, z; if（n= =0||n= =1）return n; /*计算 Fib (0)或Fib(1) */ else { x=0, y=1; /* x= Fib (0) y= Fib (1) */ for ( i=2; i= n; i++ ) { z=y; /* z= Fib (i-1) */ y=x+y; /* y= Fib (i-1)+ Fib (i-2) 求Fib (i) */ x=z; /* x= Fib (i-1) */ } return y ; } } 计算斐波那契数列的非递归算法(2) main() { long int f1,f2; int i; f1=1;f2=1; for(i=1; i=20; i++) {printf(%12ld %12ld , f1,f2); if(i%2==0) printf(＼n); f1=f1+f2; f2=f2+f1; } } /*C程序设计 谭浩强*/ 尾递归 尾递归是指递归调用语句只有一个，而且是处于算法的最后，尾递归是单向递归的特例。 求n!非递归算法 ： long Fact (int n) { int fac=1; for(int i=1;i=n;i++) /*依次计算f(1)… f(n)*/ fac=fac* i; /* f(i)= f(i-1)*i */ return fac; } 3.2 队列 3.2.1 队列的定义 3.2.2 队列的表示和实现 3.2.3 队列的应用举例 返回主目录 3.2.1 队列的定义 队列 ： 是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出的特性。 在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。 队列的抽象数据类型定义： ADT Queue 数据元素：可以是任意类型的数据，但必须属于同一个数据 对象。 关系：队列中数据元素之间是线性关系。 基本操作： 1) InitQueue(Q)：初始化操作 2) IsEmpty(Q)：