清华大学-数据结构.ppt

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

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

2、定义求解斐波那契数列的递归算法longFib(longn){if(n<=1)returnn;elsereturnFib(n-1)+Fib(n-2);}数据结构是递归的搜索链表最后一个结点并打印其数值templatevoidFind(ListNode*f){if(f→link==NULL)cout<voidPrint(ListNode*f){if(f!=NULL)if(f

3、→data==x)cout<#include"strclass.h”voidHanoi(intn,StringA,StringB,StringC){//解决汉诺塔问题的算法if(n==1)cout<<"move"<

4、路口动作结果1(入口)正向走进到22左拐弯进到33右拐弯进到44(堵死)回溯退到33(堵死)回溯退到22正向走进到55(堵死)回溯退到22右拐弯进到66左拐弯进到7(出口)43521766左0直2右0行3行5行60040000007007小型迷宫的数据迷宫的类定义#include#include#includeclassMaze{private:intMazeSize;intEXIT;Intersection*intsec;public:Maze(char*filename);intTraverseMaze

5、(intCurrentPos);}交通路口结构定义structIntersection{intleft;intforward;intright;}Maze::Maze(char*filename){//构造函数：从文件filename中读取各路口//和出口的数据ifstreamfin;fin.open(filename,ios::in

6、ios::nocreate);//为输入打开文件,文件不存在则打开失败if(!fin){cout<<“迷宫数据文件”<>MazeSize;//输入迷宫路口数ints

7、ec=newIntersection[MazeSize+1];//创建迷宫路口数组for(inti=1;i<=MazeSize;i++)fin>>intsec[i].left>>intsec[i].forward>>intsec[i].right;fin>>EXIT;//输入迷宫出口fin.close();}迷宫漫游与求解算法intMaze::TraverseMaze(intCurrentPos){if(CurrentPos>0){//路口从1开始if(CurrentPos==EXIT){//出口处理cout<

8、递归向左搜寻可行if(TraverseMaze(intsec[CurrentPos].left)){cout<