《数据结构-C语言描述》课件第3章.ppt

while(!IsEmpty(Q)) /*第二个进程*/{DeleteQueue(Q,ch2);putchar(ch2); /*显示输入缓冲区的内容*/}if(ch1==′.′)break; /*整个程序结束*/}}1)消除递归的原因其一：有利于提高算法时空性能，因为递归执行时需要系统提供隐式栈实现递归，效率低且费时。其二：无应用递归语句的语言设施环境条件，有些计算机语言不支持递归功能，如FORTRAN、C语言中无递归机制。其三：递归算法是一次执行完，这在处理有些问题时不合适，也存在一个把递归算法转化为非递归算法的需求。2)简单递归（尾递归和单向递归）消除在简单情况下，将递归算法可简化为线性序列执行，可直接转换为循环实现。例：斐波那契数列图3.11Fib(5)递归调用过程示意intFib(intn){if（n==0||n==1）returnn;/*递归出口*/elsereturnFib(n-1)+Fib(n-2); /*递归调用*/}图3.11中的15个点表示15次运算。如果合并重合点，按图3.12所示粗黑线循环实现计算，共需进行5次运算。图3.12Fib(5)循环调用过程示意单向递归的一个典型例子是我们讨论过的计算斐波那契数列的算法Fib(n)。其中，递归调用语句Fib(n-1)和Fib(n-2)只与主调用函数Fib(n)有关，相互之间参数无关，并且这些递归调用语句也和尾递归一样处于算法的最后。intFib(intn):{intx,y,z;if（n==0||n==1）returnn;/*计算Fib(0),Fib(1)*/else{intx=0,y=1,z;/*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)，形成第i项*/x=z};/*x=Fib(i-1)*/}returny;}尾递归是指递归调用语句只有一个，而且是处于算法的最后。我们以阶乘问题的递归算法Fact(n)为例讨论尾递归算法的运行过程。为讨论方便，我们列出阶乘问题的递归算法Fact(n)，并简化掉参数n的出错检查语句，改写递归调用语句的位置在最后，算法如下：longFact(intn){if(n==0)return1;returnn*Fact(n-1);}循环结构的阶乘问题算法Fact(n)如下：longFact(intn){intfac=1;for(inti=1;i=n;i++)/*依次计算f(1)，…，f(n)*/fac=fac*i;/*f(i)=f(i)*i*/returnfac;}3.2队列3.2.1队列的定义队列(Queue)是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出(FistInFistOut，缩写为FIFO)的特性。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端则称为队头(front)。假设队列为q=(a1，a2，…，an)，那么a1就是队头元素，an则是队尾元素。队列中的元素是按照a1，a2，…，an的顺序进入的，退出队列也必须按照同样的次序依次出队，也就是说，只有在a1，a2，…，an-1都离开队列之后，an才能退出队列。数据元素：可以是任意类型的数据，但必须属于同一个数据对象。关系：队列中数据元素之间是线性关系。基本操作：（1）InitQueue(Q)：初始化操作。设置一个空队列。（2）IsEmpty(Q)：判空操作。若队列为空，则返回TRUE，