第6章 递 归 6.1 递归的概念 6.2 递归算法的设计 6.3 递归过程和递归工作栈 6.4 递归算法的效率分析

Presentation on theme: "第6章 递 归 6.1 递归的概念 6.2 递归算法的设计 6.3 递归过程和递归工作栈 6.4 递归算法的效率分析"— Presentation transcript:

1 第6章 递 归 6.1 递归的概念 6.2 递归算法的设计 6.3 递归过程和递归工作栈 6.4 递归算法的效率分析
第6章 递 归 6.1 递归的概念 6.2 递归算法的设计 6.3 递归过程和递归工作栈 6.4 递归算法的效率分析 6.5 转化递归算法为非递归算法 6.6 回溯法

2 6.1 递归的概念 递归（Recurtion）是一种有效的算法设计方法。递归的数学定义是：若一个对象部分地包含他自身，或要用他自身给自己下定义，则称这个对象是递归的对象。递归算法的定义是：若一个算法直接地或间接地调用自己，则称这个算法是递归算法。简单地说，递归算法就是有自调用的算法。

3 递归分两种情况： 1.定义是递归的 许多对象的定义是递归的。例如，许多数学概念的定义就是递归的。阶乘函数的常见定义是： 当n=0时 (6―1) 当n＞0时

4 显然，这是一个循环过程定义。一旦n给定，我们就可由这个循环过程定义得出n!。例如，n=4，则有4!=4×3×2×1。
观察上边的等式，有4!=4×3！。 因此我们有阶乘函数的另一种定义为： 当n=0时 (6―2) 当n＞0时

5 这种定义方法用阶乘函数自己定义了阶乘函数（只是阶乘值更小一些），我们称(6―2)式的定义法是递归定义法。
另一个用递归方法定义的数学概念例子是斐波那契数列。斐波那契数列Fib(n)的递归定义是： 当n=0或n=1 (6―3) n＞1

6 又例如我们在第4章讨论过的链表结点也是一种递归定义。我们去掉链表结点类的成员函数，把链表结点改写成只包含数据域data和指针域next的结构体，便可以更清楚地理解链表结点定义的递归性。链表结点的结构体定义如下： struct ListNode { Datatype data; ListNode*next; };

7 在上述链表结点结构体的定义中，结构体ListNode的定义中用到了它自身，即指针域next是一种指向自身类型的指针。
仔细分析可以发现链表的定义是递归的，第7章将要讨论的树和二叉树的定义也都是递归的。

8 2.问题的解法是递归的 有些问题的解法是递归的。一个典型的例子是折半查找算法。折半查找算法也称作二分查找算法。它要解决的问题是：在一个有序（不失一般性设为由小到大的正序）的线性表a中查找是否存在一个数据元素x。 C ++ 语言的折半查找算法如下： int BSearch(elemtypea［］,elemtypex,intlow,inthigh) //在下界为low、上界为high的数组a中，折半查找数据元素x { int mid;

9 if(low>high)return-1;//查找失败出口
mid=(low+high)/2;//查 找区间折半 if(x==a［mid］)returnmid;//查找成功出口  //若x<a［mid］,在下界为low上界、为mid-1的数组a中，折半查找数据元素x if(x<a［mid］) return(BSearch(a,x,low,mid-1));

10 //若x>a［mid］,在下界为mid+1、上界为high的数组a中，折半查找数据元素x
Else return(BSearch(a,x,mid+1,hig h)); }

11 另一个典型的例子是汉诺塔问题的求解。汉诺塔问题是：设有3根标号为A，B，C的柱子，在A柱上放着n个盘子，每一个都比下面的略小一点，要求把A柱上的盘子全部移到C柱上。移动的规则是：（1）一次只能移动一个盘子；（2）移动过程中大盘子不能放在小盘子上面；（3）在移动过程中盘子可以放在A，B，C的任意一个柱子上。

12 这个问题用常规的非递归方法求解甚至不能首先确定问题的解是否存在，我们用递归方法分析考虑如下。设盘子的总数为n，我们给A柱上的盘子从上至下编号为１到ｎ。当n=1时，问题可直接求解，即我们可直接把A柱上的盘子移到C柱上；当n>1时，移动由以下三步组成：   （１）用C柱做过渡把A柱上的ｎ－１个盘子移到Ｂ柱上； （２）把A柱上的最后一个盘子移到Ｃ柱上； （３）用Ａ柱做过渡把Ｂ柱上的ｎ－１个盘子移到Ｃ柱上。

13 图6―1 n=4的汉诺塔问题移动过程

14 上述n个盘子的汉诺塔问题的递归求解思路是：把移动n个盘子的汉诺塔问题归结为移动n-1个盘子的汉诺塔问题，把移动n-1个盘子的汉诺塔问题归结为移动n-2个盘子的汉诺塔问题，……把移动2个盘子的汉诺塔问题归结为移动1个盘子的汉诺塔问题；对于1个盘子的汉诺塔问题如前所述可直接求解。在1个盘子的汉诺塔问题解决后，可以解决2个盘子的汉诺塔问题，……在n-1个盘子的汉诺塔问题解决后，可以解决n个盘子的汉诺塔问题，这样n个盘子的汉诺塔问题最终就得以解决。

15 6.2 递归算法的设计 递归算法就是算法中有直接或间接调用算法本身的算法。递归算法的设计方法和上述问题的递归解法的分析思路类同，是一种分而治之的算法设计方法。递归算法或者称为分而治之算法的思想是：对于一个较为复杂的问题，把原问题分解成几个相对简单且类同的子问题，这样原问题的解决就变成了对子问题的解决，而子问题的子子问题最终是可以直接求解的。

16 并不是每个问题都适宜于用递归算法求解。适宜于用递归算法求解的问题应具有如下三点基本要素：
（1）问题具有某种可借用的类同自身的子问题描述的性质； （2）相对于原问题来说，子问题将更加简化； （3）某一有限步的子问题（也称作本原问题）有直接的解存在。

17 这三点基本要素是一个问题存在递归算法的充分必要条件。当一个问题存在这三点基本要素时，设计该问题的递归算法的方法是：
（1）把对原问题的求解分解成对子问题的求解； （2）设计递归出口，即求解本原问题。  下面两个例子具体示范了问题的递归算法设计方法。

18 例6―1 根据阶乘的递归定义设计求n的阶乘的递归算法。n的阶乘的递归定义为：
阶乘递归函数设计如下： ＃include<stdlib.h> ＃include<iostream.h> long Fact (intn) {

19 intx; longinty;  if(n<0) { cout<<"参数n错"<<endl; exit(1); }  if(n==0)return1; //递归出口  x=n-1; y=Fact(x);//求解子问题

20 returnn*y; //对原问题的求解是在对子问题求解的基础上实现的
} 为使初学者能透彻理解递归算法，我们给出一个以n=3调用阶乘递归函数的主函数如下，然后我们分析上述递归函数的执行过程。

21 main( ) { Long int fn; fn=Fact(3); cout<<"fn ="<<fn<<endl; } 该程序对阶乘递归函数调用的执行过程如图6―2所 示。图中，带箭头的弧线旁的数值代表函数的返回值， 最终有fn=6。

22 图6―2 n=3的阶乘递归函数执行过程

23 每次进入下一次Fact( )函数调用前，由于当前的操作尚未执行完，因此需要保存当前工作的参数，然后才能进入下一次Fact( )函数调用。此时除函数名Fact、参数n需保存外，局部变量x和y也需保存。支持递归函数设计的C++语言（以及其他一些高级语言）是用一个堆栈来实现各次递归调用前的参数保存的。当Fact()函数要进行下一次递归调用时，

24 系统首先把前述的4个参数通过进栈操作保存到堆栈中；当Fact( )函数调用遇到递归出口语句（即当n=0）时，递归调用结束；在每次返回上一次递归函数调用前，系统首先通过退栈操作把保存在堆栈中的参数恢复出来。n=3的阶乘递归函数调用的系统堆栈区的动态变化过程如图6―3所示，图中符号*表示值尚未知,堆栈采用第3章讨论的顺序堆栈。

25 图6―3 n=3的阶乘递归函数调用系统堆栈变化过程

26 例6―2设计汉诺塔问题的递归算法。汉诺塔问题重述如下：设有3根标号为A，B，C的柱子，在A柱上放着n个盘子，每一个都比下面的略小一点，要求把A柱上的盘子全部移到C柱上。移动的规则是：（1）一次只能移动一个盘子；（2）移动过程中大盘子不能放在小盘子上面；（3）在移动过程中盘子可以放在A，B，C的任意一个柱子上。首先，分析汉诺塔问题可知，盘子的个数n是必须的一个输入参数，对n个盘子,可从上至下依次编号为1,2,…,n；其次，输入参数还需有3个柱子的代号,我们令3个柱子的参数名分别为fromPeg,auxPeg和toPeg；

27 最后，汉诺塔问题的求解是一个处理过程，因此算法的输出是n个盘子从柱子fromPeg借助柱子auxPeg移动到柱子toPeg的移动步骤。我们设计每一步的移动为如下形式：
Move Disk I from Peg X to Peg Y 结合上一节我们讨论过的汉诺塔问题的递归求解思路，汉诺塔问题的递归算法可设计如下： ＃include<iostream.h> void Towers(int n,char fromPeg,charau xPeg,char to Peg)

28 //把n个盘子从fromPeg借助auxPeg移至toPeg
{ if(n==1) //递归出口 cout <<"MoveDisk1fromPeg"<<fromPeg <<"toPeg"<<toPeg<<endl; return; }   //把n-1个盘子从fromPeg借助toPeg移至auxPeg Towers(n-1,fromPeg,toPeg,auxPeg);

29 //把盘子n由fromPeg直接移至toPeg
cout <<"Mov eDisk"<<n<<"fromPeg" <<fromPeg<<"toPeg"<<to Peg<<endl; //把n-1个盘子再从auxPeg借助fromPeg移至toPeg Towers( n-1,auxPeg,fromPeg,toPeg);

30 我们设计如下的主程序： Void main ( void) { Int n;  cout<<"输入盘子个数:"; cin>>n;  Towers(n,′A′,′B′,′C′); }

31 程序的一次运行如下： 输入盘子个数:4 Move Disk 1 from Peg A to Peg B Move Disk 2 from Peg A to Peg C Move Disk 1 from Peg B to Peg C Move Disk 3 from Peg A to Peg B Move Disk 1 from Peg C to Peg A Move Disk 2 from Peg C to Peg B Move Disk 4 from Peg A to Peg C

32 Move Disk 2 from Peg B to Peg A
Move Disk 1 from Peg C to Peg A Move Disk 3 from Peg B to Peg C Move Disk 1 from Peg A to Peg B Move Disk 2 from Peg A to Peg C Move Disk 1 from Peg B to Peg C

33 6.3 递归过程和递归工作栈 我们知道，对一个非递归函数的调用，在函数调用前要保存以下三方面的信息： （1）返回地址；
6.3 递归过程和递归工作栈 我们知道，对一个非递归函数的调用，在函数调用前要保存以下三方面的信息： （1）返回地址； （2）本函数调用时与形参结合的实参值，包括函数名和函数参数； （3）本函数的局部变量值。 当函数调用返回时，要首先释放当89初保存的实参值和局部变量值，然后按保存的返回地址返回。

34 对一个递归函数的调用，在函数调用前也要保存上述三方面的信息，但因为递归函数的自调用特性，上述保存信息的方法将由于函数不断地自调用，返回地址、实参值和局部变量值互相重叠，因此不能使用。递归函数保存上述三方面信息的方法是使用一个称作“运行时栈”的堆栈。每一层递归调用所需保存的信息构成一个工作记录，在每进入下一层递归调用时就建立一个新的工作记录，并把这个工作记录进栈到运行时栈，成为运行时栈的新栈顶；每退出一层递归调用，就从“运行时栈”退栈一个工作记录。因为栈顶的工作记录必定是当前正在运行层的工作记录，所以栈顶的工作记录又称为活动记录。

35 6.4 递归算法的效率分析 汉诺塔问题来源于印度的一个古老传说。汉诺塔问题的原始问题是：传说印度婆罗门庙里有一个塔台，台上有3根标号为A，B，C的用钻石做成的柱子，在A柱上放着64个金盘，每一个上面的全盘都比下面的略小一点。移动金盘的条件是：一次只能移动一个金盘，移动过程中大金盘不能放在小金盘上面。庙里的僧人一直移动不停。传说断言当把A柱上的金盘全部移到C柱上的那一天就是世界的末日。

36 我们再来讨论斐波那契数列的计算问题。斐波那契数列Fib(n)的递归定义是：

37 上述定义可直接转变为递归求值过程，递归的出口条件是Fib(0)=0，Fib(1)=1；当n>1时，递归调用公式为Fib(n)=Fib(n-2)+Fib(n-1)，因此，求第n项斐波那契数列的递归函数如下： long Fib(int n) { if(n==0||n==1)return n; //递归出口 else return Fib(n-1)+Fib(n-2);//递归调用  }

38 上述递归函数求Fib(5)的递归计算过程如图6―4所示。由图可见，若要求Fib(5)，要先求Fib(4)和Fib(3)；而求Fib(4)时需先求Fib(3)和Fib(2)；求Fib(3)时需先求Fib(2)和Fib(1)；如此等等，总共需计算Fib(4)1次，计算Fib(3)2次，计算Fib(2)3次，计算Fib(1)5次，计算Fib(0)3次，累计递归调用的次数为15=24-1。

39 按归纳法可得出求斐波那契数列的递归函数Fib(n)的递归调用次数等于2n-1；若把图6―4左下角的两个子树Fib(1)和Fib(0)放到右下角的结点Fib(1)下，则图6―4是一棵完全二叉树，由完全二叉树的性质也可得出求斐波那契数列的递归函数Fib(n)的递归调用次数等于2n-1（关于完全二叉树和完全二叉树的性质将在下一章讨论）。因此，上述计算斐波那契数列的递归函数Fib(n)的时间复杂度为O(2n)。对于计算斐波那契数列Fib(n)问题，我们也可根据6―3式写出循环方式求解的函数如下：

40 图6―4 Fib(5)的递归调用树

41 longFib2(int n) { if(n==0||n==1)return n;  else long int oneBack=1,twoBack=0,curren t; for(inti=2;i<=n;i++) current=oneBack+twoBack;

42 twoBack=oneBack; oneBack=current; } return current; }

43 显然，上述循环方式的计算斐波那契数列的函数Fib2(n)的时间复杂度为O(n)。对比Fib2(n)和递归结构的Fib(n)可发现，循环方式的Fib2(n)算法在递推计算第n项的斐波那契数列时保存了当前已经计算得到的第n-1项和第n-2项的斐波那契数列，因此其时间复杂度为O(n)；而递归方式的Fib(n)算法要计算第n项的斐波那契数列必须首先计算第n-1项和第n-2项的斐波那契数列，而某次递归计算得出的斐波那契数列，如Fib(3)无法保存，下一次要用到时还需要递归计算，因此其时间复杂度为O(2n)。

44 对于同一个问题，递归算法的时间复杂度是O(2n)，而循环算法的时间复杂度是O(n)，可见，求解斐波那契数列问题的循环算法效率要比递归算法效率高很多。一般情况下，若循环方式的算法和递归方式的算法均能求解该问题，通常循环方式算法的时间复杂度要比递归方式算法的时间复杂度低很多很多。

45 6.5 转化递归算法为非递归算法 总结我们本章至此讨论过的递归算法，可得出递归算法的两个特性：
（1）递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方法，对求解某些复杂问题，递归算法分析问题的方法是十分有效的。 （2）递归算法的时间效率通常非常差，其时间效率经常是实际应用中不可忍受的。

46 因此，第一，对求解某些问题时，我们希望用递归算法分析问题，用非递归算法具体求解问题；第二，有些计算机语言不支持递归功能，我们需要把递归算法转换为非递归算法；第三，递归算法是一次执行完的，这在处理有些问题(例如，7.5节将要讨论的二叉树分步遍历问题)时不合适。这样，也存在一个把递归算法转化为非递归算法的问题。

47 把递归算法转化为非递归算法有如下三种基本方法：
（1）对于尾递归和单向递归的算法，可用循环结构的算法替代。 （2）自己用堆栈模拟系统的运行时栈，通过分析只保存必须保存的信息（因而可小幅度提高时间效率），从而用非递归算法替代递归算法。 （3）利用堆栈保存参数，由于堆栈的后进先出特性吻合递归算法的执行过程，因而可以用非递归算法替代递归算法。

48 6.5.1 尾递归和单向递归的消除 尾递归是递归调用语句只有一个，而且是处于算法的最后。我们以阶乘问题的递归算法Fact(n)为例讨论尾递归算法的运行过程。为讨论方便，我们再次列出阶乘问题的递归算法Fact(n)，并简化掉参数n的出错检查语句，改写递归调用语句的位置在最后，算法如下： long Fact(intn) { if(n==0)return1; return n*Fact(n-1); }

49 分析上述算法可以发现，当递归调用返回时，返回到上一层递归调用的下一语句，而这个返回位置正好是算法的末尾。也就是说，以前每次递归调用时保存的返回地址、函数返回值和函数参数等实际上在这里根本就没有被使用。因此，对于尾递归形式的递归算法，不必利用系统的运行时栈保存各种信息。尾递归形式的算法实际上可变成循环结构的算法。循环结构的阶乘问题算法Fact2(n)如下：

50 longFact2(intn) { Int fac=1; for(inti=1;i<=n;i++) fac=fac*i; Return fac; }

51 尾递归是单向递归的特例。单向递归是指递归函数中虽然有一处以上的递归调用语句，但各次递归调用语句的参数只和主调用函数有关，相互之间参数无关，并且这些递归调用语句也和尾递归一样处于算法的最后。单向递归的一个典型例子是我们讨论过的计算斐波那契数列的递归算法Fib(n)。其中，递归调用语句Fib(n-1)和Fib(n-2)只和主调用函数Fib(n)有关，相互之间参数无关，并且这些递归调用语句也和尾递归一样处于算法的最后。

52 我们再次列出斐波那契数列的递归算法Fib(n)如下：
long Fib(int n) { if(n==0||n==1)return n; //递归出口 else return Fib(n-1)+Fib(n-2); //递归调用 } 循环结构的斐波那契数列的算法Fib2(n)前面已经列出，此处不再列出。

53 6.5.2 模拟系统的运行时栈消除递归现以汉诺 塔问题的递归算法为例，讨论模拟系统的运行时栈把递归算法转换为非递归算法的问题。  例6―3 模拟系统的运行时栈把汉诺塔问题的递归算法转换为非递归算法。 我们再次列出汉诺塔问题的递归算法如下： ＃include<iostream.h> void Towers(int n,char fromPeg,char auxPeg,char toPeg)  { if(n==1)

54 { cout <<"MoveDisk1fromPeg"<<fromPeg <<"toPeg"<<toPeg<<endl; return; } Towers(n-1,fromPeg,toPeg,auxPeg);cout <<"MoveDisk"<<n<<"fromPeg"<<fromPeg<<"toPeg"<<toPeg<<endl; Towers(n-1,auxPeg,fromPeg,toPeg);  }

55 由于汉诺塔问题的递归算法中有两处递归调用，再加上主调函数，所以非递归模拟算法中也应有三个模仿返回地址。三个返回地址分别为返回主调函数、返回第一次递归调用处和返回第二次递归调用处。在模拟算法中，这三个返回地址分别对应三个语句标号lable1、lable2和lable3，我们再用取值为1，2，3的一个变量模仿返回地址，因而在模拟递归算法中共有四个参数。(局部变量在整个递归调用中未发生变化，不用保存。)所以，非递归模拟算法中每次需保存算法的四个参数和一个模仿返回地址。

56 本应用例子从另一个角度也可看作是3. 3节学过的顺序堆栈类的应用。我们用3
本应用例子从另一个角度也可看作是3.3节学过的顺序堆栈类的应用。我们用3.3节的顺序堆栈类来模拟系统运行时栈，其数据元素类型Datatype定义如下： struct Datatype { short int retAddr; //模仿返回地址 int nParam; //参数n char fromParam; //参数fromPeg char auxParam; //参数auxPeg char to Param; //参数toPeg };

57 完整的汉诺塔问题用顺序堆栈类来模拟系统运行时栈的算法如下：
struct Datatype { short int retAddr; int nParam;  char fromParam; char auxParam; char toParam; }; //定义顺序堆栈类的Datatype

58 ＃include"SeqStack.h“ //包括顺序堆栈类
Void SimTowers(int n,char fromPeg,char auxPeg,char toPeg) { Datatype currArea;//当前工作区 SeqStacks;//模拟系统运行时堆栈的堆栈 chartemp; shortinti;

59 //当前工作区初始化 currArea.retAddr =1; currArea.n Param=n; currArea.fromParam=fromPeg; currArea.a uxParam=auxPeg; currArea.toParam=toPeg; s.Push(currArea); //当前工作区入栈

60 //以下为模拟出口 start: if(currArea.nParam==1) { cout <<"MoveDisk1fromPeg"<<currArea.fromParam  <<"toPeg"<<currArea.toParam<<endl; i=cu rrArea.retAddr; currArea=s.Pop(); //出栈恢复当前工作区 switch(i)

61 { case 1:gotolable1; case2:gotolable2; case3:gotolable3; }  //以下模拟递归自调用过程 s.Push(currArea); //当前工作区入栈 currArea.nParam --;

62 Temp =currAre a.auxParam; currArea.auxParam =currArea.toParam; currArea.toP Aram =temp; currArea.retAddr =2; Goto start;

63 //以下模拟返回第一次递归调用 lable2: cout <<"MoveDisk"<< currArea.nParam<<"fromPeg" <<currArea.fromParam<<"t oPeg" <<currArea.toParam<<endl; s.Push(currArea); //当前工作区入栈 currArea.nParam --; temp =currArea.fromParam;

64 currArea.fromParam =currArea.auxParam;
currArea.auxParam =temp; currArea.retAddr =3;   gotostart;  //以下模拟返回第二次递归调用 lable3: i=currArea.retAddr; currArea=s.Pop(); //出栈恢复当前工作区

65 switch(i) { case1:gotolable1; case 2:gotolable2; case3:gotolable3; }  //以下模拟返回主调函数 lable1: return;

66 这个模拟汉诺塔问题的递归算法的系统运行时栈工作流程的算法虽然是非递归的，但却和原递归算法的系统内部执行流程类似。由于汉诺塔问题本身的算法复杂度就是O(2n)，所以这个模拟算法的时间复杂度也是O(2n)。

67 6.6 回溯法 回溯法是求解复杂问题的又一种有效的方法。回溯法的思想是：对一个包括有很多结点，每个结点有若干个搜索分支的问题，设计算法为一个搜索过程，当搜索到某个结点，发现无法再继续搜索下去时，就让搜索过程回溯退到该结点的前一结点，继续搜索这个结点的其他尚未搜索过的分支；

68 如果发现这个结点也无法再继续搜索下去时，就让搜索过程回溯退到这个结点的前一结点继续这样的搜索过程；这样的搜索过程一直继续到搜索到问题的解, 或搜索完了全部可搜索分支没有解存在为止。

69 当问题有若干个解存在时，回溯法保证找到问题的一个解，但回溯法不能保证找到问题的最优解。
由于回溯法每前进一步在新的结点上进行的搜索过程和前一个结点的搜索过程类同，且使整个问题的搜索范围缩小一步，所以回溯法的算法本质上是一个递归算法。 下面我们以迷宫问题为例进一步讨论回溯法的思想和算法设计方法。

70 例6―4迷宫问题。一个迷宫是一些互相连通的交叉路口的集合，给定一个迷宫入口，一个迷宫出口，当从入口到出口存在通路时输出其中的一条通路，当从入口到出口不存在通路时输出无通路存在。对于像图6―5所示的迷宫，每个交叉路口除进来的路外有三个路口，分别是向左、向前和向右，我们假设迷宫中不存在环路。编制计算机模仿的迷宫问题算法并用图6―5验证。

71 要用计算机模仿迷宫问题，首先要把迷宫问题数值化。我们把每个路口定义成一个包括left、forward和right三个域的结构体。如果某个域的值为1表示该方向上有通路可继续走一步；如果某个域的值为0表示该方向上已无通路；全部这样的路口数值的集合就描述了一个具体的迷宫问题。此外，为算法设计方便，再在数值集合的前边加上路口的个数，在数值集合的后边加上迷宫的出口编号。这样，图6―5的数值化模拟文件"Maze1.dat"如下：

72 图6-5 迷宫问题的一个例子

73 6     0 0 0  文件的第一行是迷宫的路口个数，这里路口共有6个。 第二到第七行是编号1到编号6的6个路口的状态。例如， 第2行的020表示编号1的路口的状态是向左不通，向前通 到2号路口，向右不通。

74 图6―6 用回溯法解图6―5迷宫问题的搜索过程

75 用回溯法解图6―5所示的迷宫问题的搜索过程如图6―6所示。
按照面向对象程序设计的思想，我们把迷宫问题设计成一个类。其数据成员有路口个数mazeSize、出口Exit和路口集合*intSec；其构造函数读入如前所示的数据文件构造描述一个具体问题的迷宫类的对象；其搜索函数TravMaze(intSecValue)的输入参数intSecValue为当前所处的路口，搜索函数用回溯法搜索迷宫的所有分支，搜索函数是一个递归函数。迷宫类设计如下：

76 ＃include<stdlib.h>
＃include<fstream.h> structInterSection //路口的结构体定义  {  intleft; //向左 intfo rward; //向前 intright; //向右 };

77 classMaze //迷宫类定义 { private: int mazeSize; //路口个数 intExit;//出口 Int erSection*intSec; //路口集合 public: Maze(char*filename); //构造函数 int TravMaze(intintSecValue); //搜索函数 };

78 Maze::Maze(char*filename)
{ ifstreamfin; fin.open(filename,ios::in||ios::nocreate); //打开文件 if(!fin) cerr<<"数据文件无法打开!"; exit(1); }

79 fin>>mazeSize;//读入路口个数
 intSec=newInterSection［mazeSize+1］; //建立mazeSize+1个元素的数组  for(inti=1;i<=mazeSize;i++)//读入全部路口的结构体数值 fin>>intSec［i］.left>>intSec［i］.forward>>intSec［i］.right; fin>>Exit;//读入出口  fin.close();//关闭文件 }

80 //用回溯法搜索迷宫的所有分支，输入参数intSecValue为当前所处的路口
intMaze::TravMaze(intintSecValue) { //intSecValue>0为有路径存在，可以继续探索发现一条路径 if(intSecValue>0) if(intSecValue==Exit)//到达出口 cout<<intSecValue<<"<=="

81 ;//输出路口号 return1;//返回1 } Else if(TravMaze(intSec［intSecValue］.left))//向左探索 { //只有探索成功，即返回值为1，才执行以下语句 cout<<intSecV alue<<"<=="; //输出路口号 return1; //返回1

82 } elseif(TravMaze(intSec［intSecValue］.forward)) //向前探索 { cout<<intS ecValue<<"<=="; return1; } Else if(TravMaze(intSec［intSecValue］.right))//向右探索 cout<<intSecValue<<"<==";

83 return1; } } //intSecValue =0为无路径存在，返回0 return0; 上述成员函数TravMaze(intSecValue)只有在探索到某个路口满足该路口编号等于出口编号，表明已探索到一条路径时，才从出口编号开始回退显示探索到的一条从入口到达出口的路径上的所有路口编号，所以显示的路径序列应该是从出口到入口。

84 求解图6―5的迷宫问题的主函数如下： Void main(void) { char file Name［20］={"Maze1.dat"}; Maze m(fileName); int start=1;   if(m.TravMaze(start)) cout<<endl<<"此迷宫的一条通路如上所示"<<endl; else cout<<"此迷宫无通路!"<<endl; }

85 程序的运行结果如下： 7<==6<==2<==1<== 此迷宫的一条通路如上所示 从上述求解图6―5的迷宫问题程序的运行结果，读者可通过实例再次分析迷宫类搜索成员函数的执行过程。我们的问题是：运行结果为什么首先显示出口“7<==”?搜索成员函数Trav Maze( )的执行过程是怎样的？

86 上述迷宫类中的搜索成员函数Trav Maze(intSec Value)算法假设了迷宫中的路径不构成环路。对于一个如图6―7所示的带环路的迷宫，Trav Maze(intSec Value)算法将由于重复不断的进栈操作而出错。有兴趣的读者可以重新编写一个不重复走已走过的路径的搜索算法。

87 图6―7 带环路的迷宫