数据结构第四章

1、第四章栈、队列和递归本章所讨论的栈和队列是上一章所讨论的线性表的特殊情况，即限制存取位置的线性表限制存取位置的线性表。线性表、栈栈和队列的数据元素和逻辑结构均相同，只是线性表是可在任意位置插入和删除的线性结构，栈是只可在表头位置插入和删除的线性结构，队列是只可在表尾位置插入、在表头位置删除的线性结构。 递归递归不是一种数据结构，而是一种有效的算法设计方法。递归在许多实际系统中都有应用。这里主要介绍递归的概念、递归的过程与递归工作栈，并讨论了用循环实现递归过程，还讨论了迷宫问题。4.1 栈 栈栈（stack）是一种常用的重要的数据结构，其应用十 分广泛。 栈可以定义为只允许在表的末端进行插入和删

2、除的线 性表。 允许插入和删除的一端叫做栈顶栈顶（top），不允许插入 和删除的另一端叫做栈底栈底(bottom)。 无元素的栈为空栈空栈。设有空栈S，进栈时，按照A、B、C的顺序不断地向栈S中插入元素（即进栈，也称压入），则出现如图4-1所示的结果。 出栈时只能按C、B、A的顺序不断地删除元素（即出栈，也称弹出）。由此可以看出，后进者先出，因此栈又叫做后进先出后进先出（Last In First Out，LIFO）线性表。进栈如图4-2所示。出栈如图4-3所示。栈的两种抽象数据类型：采用顺序存储方式的顺序栈（如图4-1）和采用链式存储方式的链式栈。4.1.1 顺序栈顺序栈顺序栈（seqent

3、ial stack）就是用顺序存储方式存储的栈。在下面顺序栈的类定义中是用数组数组存储元素的。数组名为stackamaxsize ，maxsize是最大允许存放元素的个数。变量top表示栈顶部元素的位置，初始值为1，表示空栈。先给出顺序栈的抽象数据类型的描述，然后给出顺序栈的类定义与实现。顺序栈的抽象数据类型的描述：ADT seqstack isData 栈顶指示、存放栈元素的数组和栈元素个数的最大数 Operation seqstack /构造函数 输入： 栈元素个数的最大数size 初始化栈：栈顶指示置为-1，创建存储栈的数组，栈 元素个数的最大数maxsize置为size seqstac

4、k /析构函数 删除存储栈元素的数组 push 输入： 要进栈的项item 前置条件：栈未满 动作： 把item压入栈顶 输出： 无 后置条件：栈顶增加了一个新元素，栈顶指示加1pop 输入： 无 前置条件：栈非空 动作： 弹出栈顶元素 输出： 返回栈顶元素的值 后置条件：删除栈顶元素，栈顶指示减1gettop 输入： 无 前置条件：栈非空 动作： 取栈顶数据元素 输出： 返回栈顶数据元素 后置条件：无empty 输入： 无 前置条件：无 动作： 检查栈顶指示是否等于-1 输出： 栈空时返回1，否则返回0 后置条件：无 full 输入： 无 前置条件：无 动作： 检查栈顶指示是否等于maxsi

5、ze-1 输出： 栈满时返回1，否则返回0 后置条件：无 clear 输入： 无 前置条件：无 动作： 清空栈 输出： 无 后置条件：栈顶指示为-1 End ADT seqstack顺序栈的类定义。template class seqstack /顺序栈的类定义private:int top; /栈顶指示type * stacka; /数组名int maxsize; /栈最大可容纳元素个数public:seqstack( int size ); /构造函数seqstack( ) delete stacka; /析构函数void push (const type & item); /元素

6、item进栈type pop(void ); /数据元素出栈，返回之type gettop( ); /读栈顶数据元素并返回int empty (void) const return top = -1; /栈空返回1，否则返回0int full ( )const return top = maxsize-1; /* 如果栈中元素个数等于maxsize，则返回1，否则返回0 */void clear(void) top = -1; /清空栈;下面给出顺序栈的典型成员函数的实现。先给出顺序栈的构造函数，它动态地建立栈空间，其最大尺寸maxsize由函数参数size给出，并令top等于1，置栈为空。如

7、分配不成功则打印分配失败信息，否则正常结束。 template seqstack : seqstack (int size): top(-1) , maxsize (size) /建立一个最大尺寸为size的空栈 stacka = new typemaxsize; /创建存储栈的数组 if (stacka = NULL)/分配不成功 cerr动态存储分配失败！endl; exit(1); 实现进栈、出栈和取栈顶元素的操作：template void seqstack : push(const type & item)/若栈已满，出错处理；否则把元素item入栈if (full( )/栈

8、已满cerr栈已满，不能入栈！endl;exit(1);top+;/栈未满，入栈stackatop = item;template type seqstack : pop( )/栈空时出错，否则出栈，并返回栈顶元素if (empty( ) /栈空cout栈已空！endl;exit(1); type data = stackatop; /栈不空，取栈顶元素top - ;return data; /返回栈顶元素 template type seqstack : gettop( )/若栈不空，返回栈顶元素的值if (empty( ) /栈空cerr栈空！endl; exit(1);return st

9、ackatop; /返回栈顶元素的值4.1.2 链式栈链式栈链式栈（linked stack）就是用链式存储方式存储的栈。在同时使用多个栈的情况下，与顺序栈相比，可以共享存储。下面用不带头结点的单链表表示链式栈，如图4-4所示。把链表的表头作为链式栈的栈顶，因此进栈与出栈即插入与删除，都是在链表的表头进行操作。(1) 链式栈及其结点的抽象数据类型的描述：ADT node isData 链表结点的数据域和指针域Operation node /构造函数 用于构造结点end ADT node ADT linkstack isData 栈顶指针Operation linkstack 构造函数 初始化栈

10、，置空栈 push 输入： 要进栈的项item 前置条件：无 动作： 把item压入栈顶 输出： 无 后置条件：栈顶增加了一个结点，栈顶指针指向新结点 pop 输入： 无 前置条件：栈非空 动作： 弹出栈顶元素 输出： 返回栈顶元素的值 后置条件：删除栈顶元素 end ADT linkstack (2) 链式栈及其结点的模板类定义与实现：template class linkstack; /前视定义template class node /链式栈结点类定义 friend class linkstack; private: type data; /结点数据 node * next; /结点指针

11、public: n o d e ( t y p e d = 0 , n o d e * l s = NULL):data(d),next(ls) ; /构造函数;template class linkstack /链式栈类定义private:node * top; /栈顶指针，即链头指针public: linkstack( ):top(NULL) ; /构造函数，置空表void push(const type& item); /进栈int pop(void); /出栈，返回栈顶元素的值; template void linkstack : push (const type& i

12、tem) /item进栈top = new node (item, top);template type linkstack : pop( ) /出栈，并返回栈顶元素的值if (top = NULL) /空栈cout栈已空!endl;exit( 1);node * p = top;type item = top-data; /取栈顶元素的值top = p-next; /重新定义头结点delete p;return item; /返回栈顶元素的值 4.1.2 表达式的计算表达式的计算是编译系统中的基本问题之一，也是顺序栈的一个非常重要的应用。计算机进行算术运算通常是用栈来实现的，这里将重点讨论利

13、用后缀表达式求值。1. 表达式表达式常用的表达式是中缀表示。如： (A+B)*C+D/E (4-1)表4-1给出了C+中部分操作符的优先级，其中1是最高优先级。可以认为括号“( )”是超优先级，即高于1级。有多层括号时，总是从最内层的括号开始。运算符的优先级相同时，则自左向右计算。为了确定表达式(4-1)的值，首先计算A+B的和，结果为T1，然后将T1乘以C，结果为T2，之后再计算D*E的积，结果为T3，最后是T2与T3相加得结果T4。2.2. 后缀表示法后缀表示法表达式的后缀表示要求每个操作符出现在它的操作数之后。例如。中缀表达式：A*BC，对应的后缀形式为：AB*C。中缀表达式(4.1)的

14、后缀表达式为： AB+C*DE/+ (4-2)分析上述后缀表达式的计算过程。假定每次计算出一个值，并将该值放入暂存单元Ti中，i1。按从左到右的次序依次读入后缀表达式(4-2)，遇到的第一个操作符是+，在该操作符之前的两个操作数是A和B，由此A+B的结果存于T1中。对整个后缀表达式的计算过程如表4-2所示。最终的计算结果存放在T4中。含括号的中缀表达式(4-1)与不含括号的后缀表达式(4-2)的计算结果是一样的。后缀表示法有两大优点：不需要使用括号 ；不用考虑操作符的优先级。后缀表达式的计算过程是：从左向右扫描；遇操作数，则将操作数放入栈中；遇操作符，根据操作符性质(一元或二元)从栈中取出正确

15、数目的操作数，完成此操作符的运算、运算结果放入栈中；直至对整个表达式扫描完毕（假设表达式以#结束）。后缀表达式(4-2)的计算过程可以用表4-3给出。采用顺序栈的模板类定义，给出计算后缀表达式的算法：采用顺序栈的模板类定义，给出计算后缀表达式的算法：void eval (postexp e) /* 此处后缀表达式e的项term可以是操作符operator、操作数operand或表达式结束符# */ seqstack stack; /栈对象初始化 for (term x = nextterm (e) ; x != # ; x = nextterm (e) /nextterm(e )是取表达式e

16、的下一项 if (x is an operand) stack .push(x) /x是操作数，则x入栈 else /x是操作符 根据x 的性质从栈中取出正确数目的操作数； /出栈 完成此操作符的运算，设结果为temp; stack.push(temp); /运算结果入栈 term x= stack.pop(); 3. 中缀转换为后缀中缀转换为后缀 在中缀和后缀形式中，操作数的顺序是相同的。如要把中缀表达式转换为后缀表达式，在对中缀表达式进行扫描时，将遇到的操作数直接输出，而将操作符(包括括号)存入一个栈中。在之后的扫描过程中，在恰当的时刻按一定准则将栈中的操作符输出。表4-4给出了包括加、减

17、、乘、除、左括号、右括号和结束符的运算符间的优先级关系表。表中，x1代表栈顶运算符，x2代表当前扫描读到的运算符。 对表4-4中符号的说明： （1）由于后缀表达式无括号，当x1为“（”，x2为“）”时，用标记“”，此时去掉该对括号。 （2）当x1为“”，x2为“”时，用标记“”，此时结束处理。 （3） 表中值为空，表示不允许出现此种情况。当中缀表达式转换为后缀表达式时，先给中缀表达式末尾加一个结束符“”，设x1为当前栈顶运算符的变量，x2为当前扫描读到的单词，具体扫描的算法如下： (1) 操作符栈初始化，将结束符#进栈，读入中缀表达式的首字符x2。 (2) 重复执行以下步骤，直到x2 #，且栈

18、顶的操作符x1也是#时，停止循环。 若x2是操作数时直接输出，并接着读表达式的下一个单词x2。 否则 （x2是操作符） 若x1的优先级x2的优先级，将x2进栈，然后读下一个单词x2；若x1的优先级x2的优先级，将x1退栈并作为后缀表达式的一个单词输出，然后接着比较新的栈顶运算符x1的优先级与x2的优先级；若x1的优先级=x2的优先级，且x1为（，x2为），将x1退栈，然后读下一个单词x2。利用上述算法，把中缀表达式（4-1）变换成后缀表达式（4-2）的过程如表4-5所示。假定表4-4所表示的优先级关系由函数preority-comp计算，其结果为 ，或=。下面给出实现上述算法的函数postfi

19、x。void postfix(expression e) /中缀表达式转换为后缀表达式seqstack stack; /初始化栈对象stack.push (#); /#先入栈term x1=gettop( ); /取栈顶元素for (term x2 = nextterm (e) ; x2 != #;) /直到读完表达式/nextterm(e)是读表达式的下一个单词if (x2 is an operand) coutx2; /x2是操作数，则输出 x2 = nextterm (e) ;/读表达式的下一个单词else if preority-comp(x1, x2)= /x1的优先级x2的优先级

20、x1=stack.pop( ); /退栈 coutx1; x1=stack.gettop( ); /取栈顶元素else if preority-comp（x1, x2）= /x1、x2都是右括号 stack.pop( ); /去掉栈顶的左括号 x1=stack.gettop( ); /取栈顶元素 x2 = nextterm (e) ;/读表达式的下一个单词该算法对输入表达式只进行从左向右的一次扫描。处理每个操作数的时间复杂度为O(1)。每个操作符进栈和出栈各一次，因此处理每个操作符的时间复杂度也是O(1)。若n是表达式中单词的长度，则总的时间复杂度为O(n)。另外还有一种中缀表达式转换成后缀表

21、达式的算法可简单地描述为：(1)给中缀表达式中的每一步操作加上括号。(2)每个操作符移到对应该操作的右边括号外。(3)删掉所有括号。下面举例作简要说明：中缀表达式(4.1)是： (A+B)*C+D/E加上括号应是： (A+B)*C)+(D/E)把操作符移到相应括号外： (AB)+C)*(DE)/)+去掉所有的括号： AB+C*DE/+4.1 队列队列队列(queue)是一种先进先出先进先出(First In First Out，FIFO)的线性表。它只允许在表的一端插入元素，而在另一端删除元素。在队列中，允许插入的一端叫做队尾队尾(rear)，允许删除的一端叫做队头队头(front)。假设队列

22、为q = (a1, a2 , , an )，那么a1是队头元素，an是队尾元素。队列中的元素是按照a1, a2 , , an的顺序进入的，退出队列也只能按照这个顺序退出。如图4-5所示。这与日常生活中所见到的“排队”现象是一样的。 队列的存储表示也有两种方式：一种是顺序方式，另一种是链接方式。 4.2.1 循环队列队列的顺序存储表示是利用一维数组存储的。设置两个指针front和rear，分别指示队列的队头元素和队尾元素位置。约定：队头指针front指示队头元素所在位置的前一位置；队尾指针rear指示的是实际的队尾元素位置。初始时队列为空，设front=rear=-1。当要添加一个元素到队列时，

23、让队尾指针rear加1，再将新元素添加到rear所指位置。当要退出队头元素时，先把队头front指针加1，再把front所指的位置上的元素值返回。如图4-6所示，假设有4个存储空间的队列，队列的最大长度maxsize为4，即队列中最多允许存储4个元素。初始时队列为空，接着有4个元素A、B、C、D依次入了队列，然后A、B又依次出队列。 由于存在假溢出，实际软件系统中不使用上述顺序队列，而是使用下面所要讨论的顺序循环队列，即把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列，简称为循环队列。当队尾指针rear或队头指针front达到maxsize1后，再进一个位置，就自动到0，这可以利用

24、求模求模(或取余)(%)运算来实现。例如maxsize4，rear3，若再加1 ，则rear = (rear1)%40，即队尾指针的下一个取值为0。 对于循环队列，为了处理起来方便，设初始时为空队列空队列，front=rear=0。当要添加第一个元素到队列时，队尾指针rear加1等于1，要加入队列的元素放在序号1处。此时front=0，指示队头元素所在位置的前一位置，rear=1，指示的是实际的队尾元素位置，这与前面的约定是一致的。判断循环队列的队列满和队列空：考虑front指针和rear指针的初始化值，设循环队列的maxsize6，令frontrear0，其状态如图4-7( a)所示；当数据

25、元素A、B、C、D、E、F入队列后，循环队列满，此时有rearfront0，其状态如图4-7(b)所示。可见队列空与队列满都有rear=front。解决的方法通常是少用一个存储空间，以队尾指针rear加1等于队头指针作为队列满的条件。此时，队头指针front实际所指的是队头元素所在位置的前一位置，所以队列满的情形实际上空了一个位置。这样，就可以给出循环队列满和空的两个不同的判定条件。循环队列满的条件为：(rear1)%maxsize=front循环队列空的条件仍为：rear=front循环队列的抽象数据类型的描述：ADT cirqueue isData 队头、队尾指针，存放队列元素的数组，队列

26、元素个数的最大数为maxsize-1Operation cirqueue /构造函数 输入： 队列元素的最大个数加1(即size) 初始化队列，队头、队尾指针置为0，创建存储队列的 数组，队列元素个数的最大数加1(即maxsize)置为size cirqueue /析构函数 删除存储队列元素的数组EnQueue 输入： 要入队列的项item 前置条件：队列未满 动作： 把item入队列尾 输出： 无 后置条件：队列尾增加了一个新元素，队尾指针 加1，取模 DeQueue 输入： 无 前置条件：队列非空 动作： 退出队头元素 输出： 返回队头元素的地址 后置条件：删除队头元素，队头指针加1，取模

27、IsEmpty 输入： 无 前置条件：无 动作： 检查队头和队尾指针是否相等 输出： 队列空时返回1，否则返回0 后置条件：无Isfull 输入： 无 前置条件：无 动作：检查队尾指针加1再与maxsize取模是否等于队头指针 输出： 队列满时返回1，否则返回0 后置条件：无end ADT cirqueue循环队列的类定义和实现。template class cirqueue /循环队列的类定义 private: int rear , front; type * queue; /存放队列元素的数组 int maxsize; /队列最大可容纳元素个数为maxsize-1 public: cirq

28、ueue ( int size = 10); cirqueue ( )DeQueue queue; int Isfull( ) const return (rear+1)%maxsize = front; / 队列满则返回1，否则返回0 void EnQueue (const type & item); / 若队列不满，则把item入队列，否则队列溢出处理 type * DeQueue (type & ) ; / 若队列不空，则退出队头元素，并返回其地址，否则返回NULL int IsEmpty ( ) const return front = rear; / 队列空否。若队列

29、空，则函数返回1，否则返回0; template cirqueue : cirqueue (int size):front (0), rear (0), maxsize (size) /建立一个最多可容纳maxsize-1个元素的空队列 queue = new type maxsize; if (queue = NULL)cerr动态存储分配失败!endl;exit (1);template void cirqueue : EnQueue (const type & item) /item入循环队列if (Isfull ( ) cerr队列已满，不能入队列!endl; exit (1)

30、; rear = (rear+1) %maxsize; /队尾指针加1，取模 queue rear = item; /item插入队尾 template type * cirqueue : DeQueue (type & x)/*若队列不空，则删除队头元素，并返回其地址，否则返回NULL */ if (IsEmpty ( )return NULL; /若队列空，则函数返回0 front = (frront+1)%maxsize; /队头指针加1，取模 x = queue front; /取被删元素return &x;4.2.2 链队列队列的另一种存储表示是链表存储方式，最合适的

31、就是不带头结点的单链表，如图4-8所示 队列的头指针front指向单链表的第一个结点，队列的尾指针指向单链表的最后一个结点。出队出队也就是删除第一个结点，入队入队也就是在单链表尾追加一个结点。用单链表表示的链队列特别适合于数据元素变动比较大的情形，而且不存在队列满而产生溢出的情况。 链队列及其结点的抽象数据类型的描述如下：ADT node isData 链队列结点的数据域；链队列结点的指针域Operation node 初始化值： 数据项da和ne 动作： 构造结点end ADT node ADT linkqueue isData 队头指针，队尾指针Operation linkqueue 初始

32、化值：NULL；NULL 动作： 使队头指针和队尾指针为空指针 EnQueue 输入： 要插入的项item 前置条件：无 动作： 建立新结点，插入在尾结点之后 输出： 无 后置条件：表中增加一个新结点，队尾指针指向此结点 DeQueue 输入： 无 前置条件：链队列非空 动作： 删除队头结点 输出： 成功返回1，否则返回0 后置条件：表中减少一个结点，队头指针后移一个位置Clear 输入： 无 前置条件：无 动作： 循环删除链队列的队头结点 输出： 无 后置条件：空链队列IsEmpty 输入： 无 前置条件：无 动作： 检查链队列的队头指针是否空 输出： 链队列空时返回1，否则返回0 后置条件

33、：无end ADT linkqueue链队列的类定义：链队列的类定义：template class linkqueue;template class node /链式队列结点类定义friend class linkqueue ;private:type data;node * next;public: node(type da =0, node * ne = NULL): data(da), next(ne) /构造函数;template class linkqueue /链式队列的类定义private:node * front, * rear ; /队头、队尾指针public:linkque

34、ue( ): rear (NULL) , front(NULL) ; /构造函数，建立空队列linkqueue( );void EnQueue(const type & item); /将item加入队列中int DeQueue( ); /*若队列非空，则删除队头元素，并返回1，否则返回0 */void clear ( ); /与linkqueue ( )相同int IsEmpty( )const return front = NULL; /队列空否;template linkqueue : linkqueue( )node * p;while (front != NULL) /逐个删

35、除队列中的结点 p = front; front = front-next; delete p; template void linkqueue : EnQueue (const type & item) /将新元素item插入到队列的队尾 if (front = NULL) /空队列，新结点既是队头，又是队尾 front = rear = new node (item , NULL); else /非空队列，在队尾追加新结点 rear = rear-next = new node (item, NULL); /*建立以item为数据的新结点，使原队尾的next域指向此结点，同时使队尾

36、指针也指向此结点。*/template int linkqueue : DeQueue ( ) /删除队头结点，并返回1，否则返回0if (IsEmpty( ) return 0; /空队列 node * p = front; /队列不空，暂存队列头结点 front = front -next; delete p;return 1;4.3 递归 4.3.1 递归的概念递归的概念递归（recursion）在数学及程序设计中是一种很重要的工具。递归的定义：若一个对象部分地包含它自己，或用它自己给自己定义，则这个对象是递归的；若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。在以下两种情况

37、下，常常用到递归的方法。1. 定义是递归的许多对象的定义是递归的，像阶乘函数，斐波那契数列等。例如，阶乘的定义是： 时当时当0n)!1n(n0n1!n又例如，链表结点的定义，也是递归的。链表结点node的定义由数据域data和指针域next组成，而指针next则由node定义。再例如，单链表的递归定义可以写为：（1）单个结点，其指针域next的值为NULL，是一个单链表；（2）一个结点，其指针域next指向一个单链表，整个仍是一个单链表。2. 问题的解法是递归的汉诺塔问题是递归求解的一个典型问题，汉诺塔问题是：设有3根标号为A、B、C的针，在A 针上穿有n个盘子，一个比一个小。要求把A针上的盘

38、子全部移到C针上。移动的规则是：（1）一次只能移动一个盘子；（2）移动过程中大盘子不能放在小盘子上面；（3）在移动过程中盘子可以放在A、B、C的任意一根针上。问题的解法为如果n = 1，则将这一个盘子直接从A针移到C针上。否则执行以下三步： （1） 用C针做过渡，将A针上的（n-1）个盘子移到B针上； （2） 将A针上最后一个盘子直接移到C针上； （3） 用A针做过渡，将B针上的(n-1)个盘子移到C针上。移动过程如图4-9所示，图中n = 4。 移动n个盘子的汉诺塔问题归结为移动（n-1）个盘子的汉诺塔问题。与此类似，移动（n-1）个盘子的汉诺塔问题又可归结为移动（n-2）个盘子的汉诺塔问题

39、，最后总可以归结到只移动一个盘子的汉诺塔问题。求解汉诺塔问题的算法求解汉诺塔问题的算法# include void Hanoi (int n, char A, char B, char C) /把n 个盘子从A针借助B针移到C针上if (n = 1 ) /递归出口，一个盘子直接移动 coutMoveAtoCendl;else Hanoi (n-1 , A , C , B); /将上面n-1个盘子移到B针上coutMoveAtoCendl; /最后一个移到C针上Hanoi (n-1, B,A,C); /将B针上的n-1个盘子移到C针上4.3.2 递归过程与递归工作栈对一个非递归函数的调用，在函数

40、调用前要保存以下三方面的信息：(1) 返回地址；(2) 本函数调用时，与形参结合的实参值。包括函数名和函数参数；(3) 本函数的局部变量值。当函数调用返回时，要释放当初保存的实参值和局部变量值，然后按保存的返回地址返回。对于一个递归函数的调用，在函数调用前也要保存上述三方面的信息。但因为递归函数的自调用特性，上述所保存的信息将由于函数不断地调用自身而互相重叠，如没有合适的存储结构来保存，这些信息就无法使用。在高级语言的处理程序中，使用了一个“递归工作栈”来进行处理。每一层递归调用所需保存的信息构成一个工作记录，每一个工作记录包括与前述类似的三方面的信息：(1) 返回地址；即上一层中本次调用自身

41、的语句的后继语句处；(2) 本次函数调用时，与形参结合的实参值，包括函数名、引用参数和值参数等；(3) 本层的局部变量值。在每进入一层递归时，系统就要建立一个新的工作记录，把上述项目登入，加到递归工作栈的栈顶。每退出一层递归 ，就从递归工作栈退出一个工作记录，栈顶的工作记录必定是当前正在执行的这一层的工作记录，也称其为“活动记录。下面以计算阶乘的递归函数为例，对于n 为 3时，分析递归函数的执行过程，以及递归函数调用时递归工作栈的变化过程。根据阶乘的定义阶乘递归函数设计如下：long fact (int n) if (n = 0) return 1; /递归出口else return n *

42、fact(n-1); /递归调用 计算3的阶乘时，递归函数调用的执行过程如图4-10所示。图中的x是自变量，y是x的阶乘，都是中间变量。图中箭头旁的数值代表函数的返回值y，最终fact(3) = 6。时当时当0n)!1n(n0n1!n当递归调用返回时，返回到上一层递归调用的下一语句，而这个返回位置正好是算法的结束处。这样，每次递归调用时保存的返回地址就不使用了。n=3的阶乘递归函数调用的系统栈区的动态变化过程如图4-11所示，图中符号 “*”表示值尚未知。 4.3.3 消除递归递归算法是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题，用递归算法来分析比较有效，用递归算法

43、来描述也比较自然、易理解。但递归算法的时间效率通常比较差。因此，在求解某些问题时，人们希望用递归算法来分析问题，用非递归算法来求解问题；另外，有些计算机语言不支持递归功能，这就需要把递归算法转化为非递归算法。把递归算法转化为非递归算法通常采用如下两种方法： (1) 对于尾递归和单向递归的算法，可用循环结构的算法来替代；(2) 自己用栈来模拟系统运行时的栈，保存有关的信息，从而用非递归算法来模拟递归算法。 1 尾递归和单向递归的消除尾递归和单向递归的消除 尾递归尾递归是指在递归算法的函数中，递归调用语句只有一个，而且是处在函数的最后，如前述的求解阶乘的函数。 由于当递归调用返回时，是返回到上一层

44、递归调用的下一语句，而这个返回位置正好是算法的结束处。 因此，每次递归调用时保存的返回地址就不使用了，事实上，函数返回值和函数的参数也是不使用的。 由此可知，对于尾递归形式的算法，不必利用系统的运行时的栈来保存各种信息。尾递归形式的算法可以很方便地用循环结构的形式来替代。阶乘的求解可以写成如下循环结构的非递归算法long fact(int n) int product=1; for (int i=1; i=2的情况for (int i = 2; i= n; i+)current = twoback+oneback; twoback = oneback; oneback = current;re

45、turn current;2用栈模拟系统运行时的栈把一个非单向递归算法转换成非递归算法，必须使用一个栈来模拟系统运行递归算法时的栈，从而消除递归。现以4.3.1中汉诺塔问题为例来讨论这种方法。在4.3.1中给出的求解汉诺塔问题的递归算法中有两处递归调用语句，再加上主调用函数，所以在非递归模拟算法中应有三个模仿的返回地址。这三个返回地址分别返回主调用函数、第一次递归调用处和第二次递归调用处，用L1、L2和L3来分别对应这三个返回地址。另外，还使用了一个取值为1，2，3的变量模仿返回地址。在非递归模拟算法中每次需要保存四个参数和一个模仿返回地址，用来模拟系统运行时的栈是一个顺序栈。struct D

46、atatypes short int retAddr; /模仿返回地址 int nDisk; /参数n char SourcePeg; /参数A char AuxPeg; /参数B char DestPeg; /参数C ; /定义顺序堆栈类的Datatype#include”SeqStack.h” /包括顺序堆栈类void SimuTowers(int n, char A, char B, char C)Datatype currArea; /当前工作区SeqStack s; /模拟系统运行时的堆栈char temp;short int i;/当前工作区初始化currArea.retAddr

47、=1;currArea.nDisk =n;currArea.SourcePeg =A;currArea.AuxPeg =B;currArea.DestPeg =C; s.Push(currArea); /当前工作区入栈 /以下为模拟出口start: if (currArea.nDisk=1) cout”Move Disk 1 from Peg”currArea.SourcePeg ”to Peg”currArea.DestPegendl; i=currarea.retAddr; currArea=s.Pop(); /出栈恢复当前工作区switch(i) case 1: goto L1; cas

48、e 2: goto L2; case3: goto L3; /以下模拟递归自调用过程s.Push(currArea); /当前工作区入栈currArea.nDisk-;temp=currArea.AuxPeg;currArea. AuxPeg =currArea.DestPeg;currArea.DestPeg;=temp;currArea.retAddr=2;goto start;/以下模拟返回第一次递归调用L2:cout“Move Disk”currArea.nDisk “ from Peg” currArea.SourcePeg”to Peg” currArea.DestPegendl;s.Push(currArea); /当前工作区入栈currArea.nDisk-;temp=currArea.SourcePeg;currArea.SourcePeg=currArea.AuxPeg;currArea.AuxPeg=temp;currArea.retAddr=3;goto start;/以下模拟返回第二次递归调用L3: i=currArea.retAddr; currArea=s.