《数据结构第05章 (清华 殷人昆版).pptx》由会员分享，可在线阅读，更多相关《数据结构第05章 (清华 殷人昆版).pptx（61页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、递归的概念递归的概念n n递归的定义递归的定义递归的定义递归的定义 若一个对象部分地包含它自己若一个对象部分地包含它自己若一个对象部分地包含它自己若一个对象部分地包含它自己,或用它自己给自己定义或用它自己给自己定义或用它自己给自己定义或用它自己给自己定义,则则则则称这个对象是递归的；若一个过程称这个对象是递归的；若一个过程称这个对象是递归的；若一个过程称这个对象是递归的；若一个过程直接地或间接地调用自己直接地或间接地调用自己直接地或间接地调用自己直接地或间接地调用自己,则称这个过则称这个过则称这个过则称这个过程是递归的过程。程是递归的过程。程是递归的过程。程是递归的过程。n n以下三种情况常常
2、用到递归方法。以下三种情况常常用到递归方法。以下三种情况常常用到递归方法。以下三种情况常常用到递归方法。n n 定义是递归的定义是递归的n n 数据结构是递归的数据结构是递归的n n 问题的解法是递归的问题的解法是递归的第1页/共61页定义是递归定义是递归的的求解阶乘函数的递归算法求解阶乘函数的递归算法long Factorial(long n)if(n=0)return 1;else return n*Factorial(n-1);例如，阶乘函数例如，阶乘函数第2页/共61页求解阶乘求解阶乘 n!的过程的过程主程序主程序主程序主程序 main:fact(4)参数参数 4 计算计算 4*fac
3、t(3)返回返回 24参数参数 3 计算计算 3*fact(2)返回返回 6参数参数 2 计算计算 2*fact(1)返回返回 2参数参数 1 计算计算 1*fact(0)返回返回 1参数参数 0 直接定值直接定值=1 返回返回 1参参参参数数数数传传传传递递递递结结结结果果果果返返返返回回回回递递递递归归归归调调调调用用用用回回回回归归归归求求求求值值值值第3页/共61页数据结构是递归的数据结构是递归的n n 一个结点，它的指针域为一个结点，它的指针域为NULL，是，是一个单链表一个单链表;n n 一个结点，它的指针域指向单链表，一个结点，它的指针域指向单链表，仍是一个单链表。仍是一个单链表
4、。例如，单链表结构例如，单链表结构f f 第4页/共61页搜索链表最后一个结点并打印其数值搜索链表最后一个结点并打印其数值template void Print(ListNode*f)if(f-link=NULL)cout data link);f f f f f a0a1a2a3a4递归找链尾第5页/共61页在链表中寻找等于给定值的结点并打在链表中寻找等于给定值的结点并打印其数值印其数值template void Print(ListNode*f,Type&x)if(f!=NULL)if(f-data=x)cout -data-link,x);f f f f 递归找含x值的结点x第6页/共6
5、1页 问题的解法是递归的问题的解法是递归的 例如，汉诺塔例如，汉诺塔(Tower of Hanoi)问题的解问题的解法：法：如如果果 n=1，则则将将这这一一个个盘盘子子直直接接从从 A 柱移到柱移到 C 柱上。否则，执行以下三步：柱上。否则，执行以下三步：用用 C 柱柱做做过过渡渡，将将 A 柱柱上上的的(n-1)个盘子移到个盘子移到 B 柱上：柱上：将将 A 柱柱上上最最后后一一个个盘盘子子直直接接移移到到 C 柱上；柱上；用用 A 柱做过渡，将柱做过渡，将 B 柱上的柱上的(n-1)个盘子移到个盘子移到 C 柱上。柱上。第7页/共61页第8页/共61页#include#include s
6、trclass.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);第9页/共61页递归过程与递归工作栈递归过程与递归工作栈n n递归过程在实现时，需要自己调用自己。递归过程在实现时，需要自己调用自己。递归过程在实现时，需要自己调用自己。递归过程在实现时，需要自己调用自己。n n层层向下递归，退出时的次序正好相反：层层向下递归，退出时的次序正好相反：层层
7、向下递归，退出时的次序正好相反：层层向下递归，退出时的次序正好相反：递归调用递归调用递归调用递归调用 n n!(!(n n-1)!(-1)!(n n-2)!1!0!=1-2)!1!0!=1 返回次序返回次序返回次序返回次序n n主程序第一次调用递归过程为主程序第一次调用递归过程为主程序第一次调用递归过程为主程序第一次调用递归过程为外部调用外部调用外部调用外部调用；n n递归过程每次递归调用自己为递归过程每次递归调用自己为递归过程每次递归调用自己为递归过程每次递归调用自己为内部调用内部调用内部调用内部调用。n n它们它们它们它们返回返回返回返回调用它的过程的调用它的过程的调用它的过程的调用它的过
8、程的地址地址地址地址不同。不同。不同。不同。第10页/共61页递归工作栈递归工作栈n n每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。间。间。间。n n每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。每层递归调用需分配的空间形成递归工作记录
9、，按后进先出的栈组织。局部变量局部变量返回地址返回地址参参 数数活动活动记录记录框架框架递归递归工作记录工作记录第11页/共61页函数递归时的活动记录函数递归时的活动记录.Function().调用块函数块返回地址(下一条指令)局部变量 参数第12页/共61页 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 第13页/共61页计算计算Fact时活动记录的内容时活动记录的内容递递
10、归归调调用用序序列列0 RetLoc21 RetLoc22 RetLoc23 RetLoc24 RetLoc1参数参数参数参数 返回地址返回地址返回地址返回地址 返回时的指令返回时的指令返回时的指令返回时的指令RetLoc1 return 4*6 /返回返回返回返回2424 RetLoc2 return 3*2 /返回返回返回返回6 6 RetLoc2 return 1 /返回返回返回返回1 1 RetLoc2 return 1*1 /返回返回返回返回1 1 RetLoc2 return 2*1 /返回返回返回返回2 2 第14页/共61页递归过程改为非递归过程递归过程改为非递归过程n n递归
11、过程简洁、易编、易懂递归过程简洁、易编、易懂n n递归过程递归过程效率低效率低，重复计算多，重复计算多n n改为非递归过程的目的是改为非递归过程的目的是提高效提高效率率n n单向递归单向递归和和尾递归尾递归可直接用可直接用迭代迭代实现其非递归过程实现其非递归过程n n其他情形必须借助其他情形必须借助栈栈实现非递归实现非递归过程过程第15页/共61页计算斐波那契数列的函数计算斐波那契数列的函数Fib(n)的定义的定义求解斐波那契数列的递归算法求解斐波那契数列的递归算法 long Fib(long n)if(n=1)return n;else return Fib(n-1)+Fib(n-2);如如
12、 F0=0,F1=1,F2=1,F3=2,F4=3,F5=5 第16页/共61页调用次数调用次数 NumCall(k)=2*Fib(k+1)-1。斐波那契数列的递归调用树斐波那契数列的递归调用树Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)第17页/共61页Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)栈结点栈结点n tagtag=1,向左递归；向左递归；tag=2,向右递归向右递归第18页/共61页
13、Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)2 13 14 1 n=1sum=0+12 23 14 1n=2-23 14 1 n=0sum=1+03 24 1n=3-24 1 n=1sum=1+14 2n=4-2第19页/共61页Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)2 14 2 n=1sum=2+12 24 2n=2-24 2 n=0sum=3+0第20页/共61页long Fibnacci(long n)Stack S;Node*w;long sum=0;/
14、反复执行直到所有终端结点数据累加完 do while(n 1)w-n=n;w-tag=1;S.push(w);n-;/向左递归到底,边走边进栈 sum=sum+n;/执行求和 第21页/共61页 while(!S.IsEmpty()w=S.getTop();S.Pop();if(w-tag=1)/改为向右递归 w-tag=2;S.push(w);n=w-n 2;/F(n)右侧为F(n-2)break;while(!S.IsEmpty();return sum;第22页/共61页单向递归用迭代法实单向递归用迭代法实现现long FibIter(long n)if(n=1)return n;lon
15、g twoback=0,oneback=1,Current;for(int i=2;i=0)cout An=0)cout value An endl;n-;第25页/共61页递归与回溯递归与回溯 常用于搜索过程常用于搜索过程n皇后问题皇后问题 在在 n 行行 n 列的列的国际象棋棋盘国际象棋棋盘上，若上，若两个皇后两个皇后位于位于同一行同一行、同一同一列列、同一对角线同一对角线上，则称为它们为上，则称为它们为互相攻击互相攻击。n皇后问题是指皇后问题是指找到这找到这 n 个皇后的互不攻击的布局个皇后的互不攻击的布局。第26页/共61页1#主对角线主对角线3#主对角线主对角线5#主对角线主对角线0
16、#次对角线次对角线2#次对角线次对角线4#次对角线次对角线6#次对角线次对角线1#次对角线次对角线3#次对角线次对角线5#次对角线次对角线0#主对角线主对角线2#主对角线主对角线4#主对角线主对角线6#主对角线主对角线0 1 2 3 0123k=i+jk=n+i-j-1第27页/共61页解题思路解题思路n n安放安放安放安放第第第第 i i 行行行行皇后时，需要在列的方向从皇后时，需要在列的方向从皇后时，需要在列的方向从皇后时，需要在列的方向从 0 0 到到到到 n-1 n-1 试探试探试探试探 (j=0,n-1(j=0,n-1)n n在在在在第第第第 j j 列列列列安放一个皇后：安放一个皇
17、后：安放一个皇后：安放一个皇后：uu如果在如果在列列、主对角线主对角线、次对角线次对角线方方向有其它皇后，则出现攻击，撤消向有其它皇后，则出现攻击，撤消在在第第 j 列列安放的皇后。安放的皇后。uu如果没有出现攻击，在如果没有出现攻击，在第第 j 列列安放安放的皇后不动，递归安放第的皇后不动，递归安放第 i+1行皇行皇后。后。第28页/共61页n n设置设置 4 个数组个数组u col n：coli 标识第标识第 i 列是列是否安放了皇后否安放了皇后u md2n-1:mdk 标识第标识第 k 条主对角线是否安放了皇后条主对角线是否安放了皇后u sd2n-1:sdk 标识第标识第 k 条条次对角
18、线是否安放了皇后次对角线是否安放了皇后u qn:qi 记录第记录第 i 行皇后在行皇后在第几列第几列第29页/共61页void Queen(int i)for(int j=0;j n;j+)if(第第第第 i i 行第行第行第行第 j j 列没有攻击列没有攻击列没有攻击列没有攻击)在在在在第第第第 i i 行第行第行第行第 j j 列安放皇后列安放皇后列安放皇后列安放皇后；if(i=n-1)输出一个布局输出一个布局输出一个布局输出一个布局；else Queen(i+1);撤消撤消撤消撤消第第第第 i i 行第行第行第行第 j j 列的皇后列的皇后列的皇后列的皇后；第30页/共61页算法求精算法
19、求精void Queen(int i)for(int j=0;j n;j+)if(!col j&!mdn+i-j-1&!sdi+j)/*第第 i 行第行第 j 列没有攻击列没有攻击*/col j=mdn+i-j-1=sdi+j=1;qi=j;/*在在第第 i 行第行第 j 列安放皇后列安放皇后*/第31页/共61页 if(i=n-1)/*输出一个布局输出一个布局*/for(j=0;j n;j+)cout qj ,;cout 0时，时，表的表的第一个表元素第一个表元素称为广义表称为广义表 的的表头表头(head)，除此之外，除此之外，其它表元素其它表元素组组 成的表成的表称为广义表的称为广义表的
20、表尾表尾(tail)。第33页/共61页广义表的特性广义表的特性n n有次序性有次序性n n有长度有长度A=()B=(6,2)C=(a,(5,3,x)D=(B,C,A)E=(B,D)F=(4,F)n n有深度有深度n n可共享可共享n n可递归可递归第34页/共61页第35页/共61页广义表的表示广义表的表示只包括整数和字符型数据的广义表链表表示只包括整数和字符型数据的广义表链表表示 表中套表情形下的广义表链表表示表中套表情形下的广义表链表表示5232436103914 list25list1 1247as第36页/共61页广义表结点定义广义表结点定义n n结点类型结点类型结点类型结点类型 u
21、type utype =0,=0,表头；表头；表头；表头；=1,=1,整型原子；整型原子；整型原子；整型原子；=2,=2,字符型原子；字符型原子；字符型原子；字符型原子；=3,=3,子表子表子表子表n n值值值值 valuevalue utype=0utype=0时时时时,存存存存 放放放放 引引引引 用用用用 计计计计 数数数数(ref)(ref)；utype=1utype=1时时时时,存存存存 放放放放 整整整整 数数数数 值值值值(intinfo)(intinfo)；utype=2utype=2时时时时,存存存存放放放放字字字字符符符符型型型型数数数数据据据据(charinfo)(cha
22、rinfo)；utype=3utype=3时时时时,存存存存放放放放指指指指向子表表头的指针向子表表头的指针向子表表头的指针向子表表头的指针(hlink)(hlink)n n尾指针尾指针尾指针尾指针tlinktlink utype=0utype=0时时时时,指向该表第一个结点；指向该表第一个结点；指向该表第一个结点；指向该表第一个结点；utypeutype 0 0时时时时,指向同一层指向同一层指向同一层指向同一层下一个结点下一个结点下一个结点下一个结点 utype value tlink 第37页/共61页广义表的存储表示广义表的存储表示E EBF F0 11 430 133D 0 11 51
23、 32 x 0 12 a3 C C 0 13330 11 6D DB BBCA1 2 0 1A A 第38页/共61页广义表的类定义广义表的类定义class GenList;/GenList类的前视声明class GenListNode /广义表结点类的前视声明struct Items /仅有结点信息的项friend class GenlistNode;friend class Genlist;int utype;/0/1/2/3 union /联合 第39页/共61页 int ref;/utype=0,存放引用计数 int intinfo;/utype=1,存放整数值 char charin
24、fo;/utype=2,存放字符 GenListNode*hlink;/utype=3,存放指向子表的指针 class GenListNode /广义表结点类定义friend class Genlist;private:int utype;/0/1/2/3第40页/共61页 GenListNode*tlink;/下一结点指针 union/联合 int ref;/utype=0,存放引用计数 int intinfo;/utype=1,存放整数值 char charinfo;/utype=2,存放字符 GenListNode*hlink;/utype=3,存放指向子表的指针 value;publi
25、c:GenListNode():utype(0),tlink(NULL),ref(0)/构造函数,建表头结点第41页/共61页 GenListNode(int t,GenListNode*next=NULL)/构造函数：建表结点 Items&Info(GenListNode*elem);/返回表元素elem的值 int nodetype(GenListNode*elem)return elem-utype;/返回表元素elem的数据类型 GenListNode&setInfo(Items&x);/将表元素elem中的值修改为x;第42页/共61页class GenList /广义表类定义 pr
26、ivate:GenListNode*first;/广义表头指针 GenListNode*Copy(GenListNode*ls);/复制一个 ls 指示的无共享非递归表 int depth(GenListNode*ls);/计算由 ls 指示的非递归表的深度 int equal(GenListNode*s,GenListNode*t);/比较以s和t为表头的两个表是否相等 void Remove(GenListNode*ls);/释放以 ls 为表头结点的广义表第43页/共61页public:Genlist();/构造函数 GenList();/析构函数 GenListNode&Head();
27、/返回表头元素 GenList&Tail();/返回表尾 GenListNode*First();/返回第一个元素 GenListNode*Next(GenListNode*elem);/返回表元素elem的直接后继元素 void setNext(GenListNode*elem1,GenListNode*elem2);/将elem2插到表中元素elem1后 第44页/共61页 void Copy(const GenList&l);/广义表的复制 int depth();/计算一个非递归表的深度 int Createlist(GenListNode*ls,char*s);/从广义表的字符串描述
28、 s 出发,/建立一个带表头结点的广义表结构 第45页/共61页广义表的访问算法广义表的访问算法 广义表结点类的存取成员函数广义表结点类的存取成员函数Items&GenListNode:Info(GenListNode*elem)/返回表元素elem的值 Items*pitem=new Items;pitem-utype=elem-utype;pitem-value=elem-value;return*pitem;第46页/共61页GenListNode&GenListNode:setInfo(Items&x)/修改表元素的值为 x utype=x-utype;value=x-value;广义
29、表类的构造和访问成员函数广义表类的构造和访问成员函数Genlist:GenList()/构造函数 GenListNode*first=new GenListNode();first-utype=0;first-ref=1;first-tlink=NULL;第47页/共61页Items&GenList:Head()/若广义表非空，则返回其第一个元素的值，/否则函数没有定义。if(first-tlink=NULL)return NULL;else /非空表 Items*temp=new Items;temp-utype=frist-tlink-utype;temp-value=frist-tlin
30、k-value;return*temp;/返回类型及值 第48页/共61页GenList&GenList:Tail()/若广义表非空，则返回广义表除第一个元/素外其它元素组成的表,否则函数没有定义 if(frist-tlink=NULL)return NULL;else/非空表 GenList*temp;temp-first=Copy(first);return*temp;第49页/共61页GenListNode*GenList:First()if(first-tlink=NULL)return NULL;else return first-tlink;GenListNode*GenList:
31、Next(GenListNode*elem)if(elem-tlink=NULL)return NULL;else return elem-tlink;第50页/共61页广义表的递归算法广义表的递归算法 广义表的复制算法广义表的复制算法 void GenList:Copy(const GenList&ls)first=Copy(ls.first);/共有函数GenListNode*GenList:Copy(GenListNode*lst)/私有函数 GenListNode*q=NULL;if(lst!=NULL)q=new GenListNode(lst-utype,NULL);第51页/共6
32、1页 switch(ls-utype)case 0:q-value.ref=ls-value.ref;break;case 1:q-value.intgrinfo=ls-value.intgrinfo;break;case 2:q-value.charinfo=ls-value.charinfo;break;case 3:q-value.hlink=Copy(ls-value.hlink);第52页/共61页 q-tlink=Copy(ls-tlink);return q;第53页/共61页求广义表的深度求广义表的深度例如，对于广义表例如，对于广义表 E(B(a,b),D(B(a,b),C(u
33、,(x,y,z),A()1111234第54页/共61页int GenList:depth(GenListNode*lst)if(lst-tlink=NULL)return 1;/空表 GenListNode*temp=lst-tlink;int m=0;while(temp!=NULL)/在表顶层横扫 if(temp-utype=3)/结点为表结点 int n=depth(temp-value.hlink);if(m tlink;return m+1;第55页/共61页int GenList:depth()return depth(first);广义表的删除算法广义表的删除算法0 11 53
34、31 2 0 12 x 0 10 12 yls32 x n n 扫描子链表扫描子链表uu 若结点数据为若结点数据为x,删除。可能做循环连续删。删除。可能做循环连续删。uu 若结点数据不为若结点数据不为x，不执行删除。，不执行删除。uu 若结点为子表，递归在子表执行删除。若结点为子表，递归在子表执行删除。第56页/共61页n n 扫描子链表扫描子链表uu 若结点数据为若结点数据为x,删除。可能做循删除。可能做循环连环连 续删。续删。uu 若结点数据不为若结点数据不为x，不执行删除。，不执行删除。uu 若结点为子表，递归在子表执行删除。若结点为子表，递归在子表执行删除。void delvalue(
35、GenListNode*ls,const value x)/在广义表中删除所有含 x 的结点 if(ls-tlink!=NULL)/非空表 GenListNode*p=ls-tlink;第57页/共61页 while(p!=NULL&/横扫链表 (p-utype=1&p-value.intinfo=x)|(p-utype=2&p-value.charinfo=x)ls-tlink=p-tlink;delete p;/删除 p=ls-tlink;/指向同一层后继结点 if(p!=NULL)if(p-utype=3)/在子表中删除 delvalue(p-value.hlink,x);第58页/共6
36、1页 delvalue(p,x);/在后续链表中删除 GenList:GenList()/析构函数 Remove(first);void GenList:Remove(GenListNode*ls)/私有函数：释放以 ls 为表头指针的广义表 ls-value.ref-;/引用计数减1第59页/共61页 if(ls-value.ref=0)/如果减到0 GenListNode*p=ls,*q;/横扫表顶层 while(p-tlink!=NULL)q=p-tlink;/到第一个结点 if(q-utype=3)/递归删除子表 Remove(q-value.hlink);p-link=q-link;delete q;第60页/共61页感谢您的观看！第61页/共61页