迷宫的类完义 交通路口结构定义 #include <iostream. h> struct Intersection include <fstream. h> include <stdlib.h> int left; class Maze i int forward private int rig/ ght; int Mazesizes int EXIT Intersection Intece public: Maze( char filename ) int Traverselaze( int CurrentPos )3
迷宫的类定义 #include <iostream.h> #include <fstream.h> #include <stdlib.h> class Maze { private: int MazeSize; int EXIT; Intersection *intsec; public: Maze ( char *filename ); int TraverseMaze ( int CurrentPos ); } 交通路口结构定义 struct Intersection { int left; int forward; int right; }
Maze: Maze( char filename)& ∥构造函数:从文件 filename中读取各路口 /和出口的数据 ifstream fin fin. open(filename, ios: in ios: nocreate )3 /为输入打开丈件,件不存在则打开失败 if( fin)& cout≤<“迷宫数据文件"<< filename <<“打不开 <<en ndl; exit (1); fin > MazeSize, /入迷宫路口数
Maze::Maze ( char *filename ) { //构造函数：从文件 filename 中读取各路口 //和出口的数据 ifstream fin; fin.open ( filename, ios::in | ios::nocreate ); //为输入打开文件,文件不存在则打开失败 if ( !fin ) { cout << “迷宫数据文件” << filename << “打不开” << endl; exit (1); } fin >> MazeSize; //输入迷宫路口数
intsec- new Intersection MazeSize+1l 创建迷宫路口数组 for( int i=l; i<-MazeSize; i++) fin>>intseclil left > intseclil forward > intsecli] right; f>>EH/输入迷宫出口 fin. close (s 迷宫漫游与求解算法 int Maze: TraverseMaze( int CurrentPos)& if( Currents>0){∥路口从1开始
intsec = new Intersection[MazeSize+1]; //创建迷宫路口数组 for ( int i=1; i<=MazeSize; i++ ) fin>>intsec[i].left >> intsec[i].forward >> intsec[i].right; fin >> EXIT; //输入迷宫出口 fin.close ( ); } 迷宫漫游与求解算法 int Maze::TraverseMaze ( int CurrentPos ) { if ( CurrentPos > 0 ) { //路口从 1 开始
if( Currents==EHT){∥出口处理 cout < CurrentPos < return 1 eise 兔归向左拽寻可行 if (TraverseMaze(intec[ CurrentPos] left ) i cout < Currentpos <<"i return 1; 3 else 递归向前搜寻可行 if (TraverseMaze(intec[ CurrentPos ]. forward) i cout < CurrentPos <<" return 1; 3 ese∥)归向右搜寻可行 if (TraverseMaze(intsec[ CurrentPos) right 3 cout < CurrentPos <<"i return 1; return o
if ( CurrentPos == EXIT ) { //出口处理 cout << CurrentPos << " "; return 1; } else //递归向左搜寻可行 if (TraverseMaze(intsec[CurrentPos].left )) { cout << CurrentPos << “ ”; return 1; } else //递归向前搜寻可行 if (TraverseMaze(intsec[CurrentPos].forward)) { cout << CurrentPos << “ ”; return 1; } else //递归向右搜寻可行 if (TraverseMaze(intsec[CurrentPos].right)) { cout << CurrentPos << " "; return 1; } } return 0; }
递归过程与递归工作栈 递归过程在实现时,需要自己调用自己。 每一次递归调用时,需要为过程中使用 的参数、局部变量等另外分配存储空间。 层层向下递归,退出时的次序正好相反: 递归次序 n!=(n-1)!=(n-2)!曰m1!0!=1 返回次序 因此,每层递归调用需分配的空间形成 递归工作记录,按后进先出的栈组织
递归过程与递归工作栈 递归过程在实现时，需要自己调用自己。 每一次递归调用时，需要为过程中使用 的参数、局部变量等另外分配存储空间。 层层向下递归，退出时的次序正好相反： 递归次序 n! (n-1)! (n-2)! 1! 0!=1 返回次序 因此，每层递归调用需分配的空间形成 递归工作记录，按后进先出的栈组织