数据结构05.ppt

《数据结构05.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、递归的概念递归过程与递归工作栈递归与回溯广义表第五章递归与广义表1递归的概念递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。以下三种情况常常用到递归方法。定义是递归的数据结构是递归的问题的解法是递归的2定义是递归的求解阶乘函数的递归算法longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);}例如，阶乘函数3求解阶乘n!的过程主程序ma

2、in:fact(4)参数4计算4*fact(3)返回24参数3计算3*fact(2)返回6参数2计算2*fact(1)返回2参数1计算1*fact(0)返回1参数0直接定值=1返回1参数传递结果返回递归调用回归求值4数据结构是递归的一个结点，它的指针域为NULL，是一个单链表;一个结点，它的指针域指向单链表，仍是一个单链表。例如，单链表结构ff5搜索链表最后一个结点并打印其数值templatevoidPrint(ListNode*f){if(f->link==NULL)

3、cout<data<link);}fffffa0a1a2a3a4递归找链尾6在链表中寻找等于给定值的结点并打印其数值templatevoidPrint(ListNode*f,TX&x){if(f!=NULL)if(f->data==x)cout<data<link,x);}ffff递归找含x值的结点x7问题的解法是递归的例如，汉诺塔(TowerofHanoi)问题的解法：如果

4、n=1，则将这一个盘子直接从A柱移到C柱上。否则，执行以下三步：①用C柱做过渡，将A柱上的(n-1)个盘子移到B柱上：②将A柱上最后一个盘子直接移到C柱上；③用A柱做过渡，将B柱上的(n-1)个盘子移到C柱上。89#include#include"strclass.h”voidHanoi(intn,StringA,StringB,StringC){//解决汉诺塔问题的算法if(n==1)cout<<"move"<

5、,A,C,B);cout<<"move"<#include#include

6、dlib.h>classMaze{private:intMazeSize;intEXIT;Intersection*intsec;public:Maze(char*filename);intTraverseMaze(intCurrentPos);};交通路口结构定义structIntersection{intleft;intforward;intright;}12Maze::Maze(char*filename){//从文件filename中读取各路口和出口的数据ifstreamfin;fin.op

7、en(filename,ios::in

8、ios::nocreate);if(!fin){cout<<“文件”<>MazeSize;//输入迷宫路口数intsec=newIntersection[MazeSize+1];//创建迷宫路口数组for(inti=1;i<=MazeSize;i++)fin>>intsec[i].left>>intsec[i].forward>>intsec[i].right;fin>>EXIT;//输

9、入迷宫出口fin.close();}13迷宫漫游与求解算法intMaze::TraverseMaze(intCurrentPos){if(CurrentPos>0){//路口从1开始if(CurrentPos==EXIT){//出口处理cout<