1 / 66
文档名称:

清华大学数据结构05recursiv.ppt

格式:ppt   大小:227KB   页数:66页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

清华大学数据结构05recursiv.ppt

上传人:相惜 2022/8/8 文件大小:227 KB

下载得到文件列表

清华大学数据结构05recursiv.ppt

文档介绍

文档介绍:递归(ss)的概念
迷宫(Maze)问题
递归过程与递归工作栈
广义表 (General Lists )
小结
第五章 递归与广义表
精选ppt
递归的概念
递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义aze ( char *filename );
int TraverseMaze ( int CurrentPos );
}
交通路口结构定义
struct Intersection {
int left;
int forward;
int right;
}
精选ppt
Maze :: Maze ( char *filename ) { //构造函数:从文件 filename 中读取各路口 //和出口的数据 ifstream fin; ( filename, ios::in | ios::nocreate ); //为输入打开文件,文件不存在则打开失败 if ( !fin ) { cout << “迷宫数据文件” << filename << “打不开” << endl; exit (1); } fin >> MazeSize; //输入迷宫路口数
精选ppt
intsec = new Intersection[MazeSize+1]; //创建迷宫路口数组
for ( int i = 1; i <= MazeSize; i++ ) fin >> intsec[i].left >> intsec[i].forward >> intsec[i].right; fin >> EXIT; //输入迷宫出口
( );
}
迷宫漫游与求解算法 int Maze::TraverseMaze ( int CurrentPos ) { if ( CurrentPos > 0 ) { //路口从 1 开始
精选ppt
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; }
精选ppt
递归过程与递归工作栈
递归过程在实现时,需要自己调用自己。
每一次递归调用时,需要为过程中使用的参数、局部变量等另外分配存储空间。
层层向下递归,退出时的次序正好相反:
递归次序
n! (n-1)! (n-2)! 1! 0!=1
返回次序
因此,每层递归调用需分配的空间形成递归工作记录,按后进先出的栈组织。
精选ppt
函数递归时的活动记录
精选ppt
long Factorial ( long n ) {
int temp;
if ( n == 0 ) return 1;
else temp = n * Factorial (n-1);
RetLoc2