《2019年清华大学数据结构课件》由会员分享，可在线阅读，更多相关《2019年清华大学数据结构课件（66页珍藏版）》请在金锄头文库上搜索。
1、递归(ss)的概念 迷宫(Maze)问题 递归过程与递归工作栈 广义表 (General Lists ) 小结,第五章 递归与广义表,递归的概念,递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 以下三种情况常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的,定义是递归的,求解阶乘函数的递归算法 long Factorial ( long n ) if ( n = 0 ) return 1; else return n*Factorial (n-1); ,例如，阶乘函数,求
2、解阶乘 n! 的过程,计算斐波那契数列的函数Fib(n)的定义,求解斐波那契数列的递归算法 long Fib ( long n ) if ( n = 1 ) return n; else return Fib (n-1) + Fib (n-2); ,数据结构是递归的,搜索链表最后一个结点并打印其数值 template void Find ( ListNode *f ) if ( f link = NULL ) cout f data endl; else Find ( f link ); ,例如，单链表结构,在链表中寻找等于给定值的结点并打印其数值template void Print ( L
3、istNode *f, Type,问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题,#include #include strclass.h” void Hanoi (int n, String A, String B, String C ) /解决汉诺塔问题的算法 if ( n = 1 ) cout move A to ” C endl; else Hanoi ( n-1, A, C, B ); cout move A to C endl; Hanoi ( n-1, B, A, C ); ,迷宫问题,小型迷宫,路口 动作 结果 1 (入口) 正向走 进到 2 2 左拐弯
4、进到 3 3 右拐弯 进到 4 4 (堵死) 回溯 退到 3 3 (堵死) 回溯 退到 2 2 正向走 进到 5 5 (堵死) 回溯 退到 2 2 右拐弯 进到 6 6 左拐弯 进到 7 (出口),4 3,5 2 1,7 6,6 左 0 直 2 右 0 行 3 行 5 行 6 0 0 4 0 0 0 0 0 0 7 0 0 7,小型迷宫的数据,迷宫的类定义 #include #include #include class Maze private: int MazeSize; int EXIT; Intersection *intsec; public: Maze ( char *filena
5、me ); 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 ); /为输入打开文件,文件不存在则打开失败 if ( !fin ) cout MazeSize; /输入迷宫路口数,intsec = new
6、 IntersectionMazeSize+1; /创建迷宫路口数组 for ( int i = 1; i intseci.left intseci.forward intseci.right; fin EXIT; /输入迷宫出口 fin.close ( ); 迷宫漫游与求解算法int Maze:TraverseMaze ( int CurrentPos ) if ( CurrentPos 0 ) /路口从 1 开始,if ( CurrentPos = EXIT ) /出口处理 cout CurrentPos ; return 1; else /递归向左搜寻可行 if (TraverseMaz
7、e(intsecCurrentPos.left ) cout CurrentPos “ ”; return 1; else /递归向前搜寻可行 if (TraverseMaze(intsecCurrentPos.forward) cout CurrentPos “ ”; return 1; else /递归向右搜寻可行 if (TraverseMaze(intsecCurrentPos.right) cout CurrentPos ; return 1; return 0;,递归过程与递归工作栈,递归过程在实现时，需要自己调用自己。 每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配
8、存储空间。 层层向下递归，退出时的次序正好相反： 递归次序 n! (n-1)! (n-2)! 1! 0!=1 返回次序 因此，每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。,函数递归时的活动记录,long Factorial ( long n ) int temp; if ( n = 0 ) return 1; else temp = n * Factorial (n-1); RetLoc2 return temp; ,void main ( ) int n; n = Factorial (4); RetLoc1 ,计算Factorial时活动记录的内容,调用次数 NumCal
9、l(k) = 2*Fib(k+1) - 1。,斐波那契数列的递归调用树,打印数组An的值 void recfunc ( int A , int n ) if ( n = 0 ) cout An ; n-; recfunc ( A, n ); ,25 36 72 18 99 49 54 63 81,void iterfunc ( int A , int n ) /消除了尾递归的非递归函数 while ( n = 0 ) cout value An endl; n-; ,广义表 (General Lists ),广义表的概念 n ( 0 )个表元素组成的有 限序列，记作 LS = (a0, a1,
10、 a2, , an-1) LS是表名，ai是表元素，它可以是表(称为 子表)，可以是数据元素(称为原子)。 n为表的长度。n = 0 的广义表为空表。 n 0时，表的第一个表元素称为广义表 的表头(head)，除此之外，其它表元素组 成的表称为广义表的表尾(tail)。,广义表的特性,有次序性 有长度 有深度,可递归 可共享,A = ( ) B = ( 6, 2 ) C = ( a, ( 5, 3, x ) ) D = ( B, C, A ) E = ( B, D ) F = ( 4, F ),各种广义表的示意图,广义表的表示,只包括整数和字符型数据的广义表链表表示,表中套表情形下的广义表链表
11、表示,广义表结点定义,标志域 utype, 表明结点类型。0为表头结点，1 为整型原子结点，2为字符型原子结点，3为子表结点。 值域 value。当 utype = 0 时为表引用计数，= 1时为整数值，= 2 时为字符值， = 3 时为指向子表的表头结点的指针。 尾指针域 tlink。当 utype = 0 时为指向该表表头元素的指针；当 utype 0 时为指向同一层下一个表结点的指针。,utype = 0/1/2/3,value = ref /intgrinfo /charinfo / hlink,tlink,广义表的带表头结点的存储表示,广义表的类定义,#define HEAD 0 #
12、define INTGR 1 #define CH 2 #define LST 3 class GenList; class GenListNode /广义表结点类 friend class Genlist; private: int utype; GenListNode * tlink;,union int ref;/utype = 0, 表头结点 int intgrinfo;/utype = 1, 整型 char charinfo; /utype = 2, 字符型 GenListNode *hlink; /utype = 3, 子表结点 value; public: GenListNode
13、 ,class GenList /广义表类 private: GenListNode* first; /广义表表头指针 GenListNode* Copy ( GenListNode* ls ); int depth ( GenListNode *ls ); int equal ( GenListNode *s, GenListNode *t ); void Remove (GenListNode *ls ); public: Genlist ( ); GenList ( ); GenListNode,GenListNode *First ( ); GenListNode *Next ( Ge
14、nListNode *elem ); void Push ( GenListNode ,广义表的访问算法,广义表结点类的存取成员函数 GenListNode ,void GenListNode : setInfo(GenListNode* elem, GenListNode /仅建立表头结点 ,GenListNode ,GenListNode ,void GenList : Push ( GenListNode ,GenList ,广义表的递归算法,广义表的复制算法 void GenList:Copy ( const GenList /复制 utype,switch ( lsutype ) c
15、ase HEAD : qvalue.ref = lsvalue.ref; break; case INTGR : qvalue.intgrinfo = lsvalue.intgrinfo; break; case CH : qvalue.charinfo = lsvalue.charinfo; break; case LST : qvalue.hlink = Copy ( lsvalue.hlink ); break; ,qtlink = Copy ( lstlink ); return q; ,求广义表的深度,例如，对于广义表 E ( B (a, b), D ( B (a, b), C (u, (x, y, z), A ( ) ) ) 按递归算法分析： De
