山大计算机数据结构ppt电子版资料DS05课件.ppt

递归(Recurve)的概念 迷宫(Maze)问题 递归过程与递归工作栈 广义表 (General Lists );递归的概念;定义是递归的;求解阶乘 n! 的过程;计算斐波那契数列的函数Fib(n)的定义;数据结构是递归的;在链表中寻找等于给定值的结点并打印其数值template class Type void Print ( ListNodeType *f ) { if ( f != NULL) if ( f →data == x ) cout f→data endl; else Print ( f→link );};问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题;;迷宫问题;迷宫的类定义 #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 ); };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+1]; //创建迷宫路口数组 for ( int i=1; i=MazeSize; i++ )  finintsec[i].left intsec[i].forward intsec[i].right; fin EXIT; //输入迷宫出口 fin.close ( ); } 迷宫漫游与求解算法int Maze::TraverseMaze ( int CurrentPos ) { if ( CurrentPos 0 ) { //路口从 1 开始; 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;};;函数递归时的活动记录; long Factorial ( long n ) { int temp; if ( n == 0 ) return 1; else temp = n * Factorial (n-1); RetLoc2 return temp; };计算Factorial时活动记录的内容;调用次数 NumCall(k) = 2*Fib(k+1) - 1。;打印数组A[n]的值 void recfunc ( int A[ ], int n ) {