《数据结构课件c语言描述第5章.ppt》由会员分享，可在线阅读，更多相关《数据结构课件c语言描述第5章.ppt（79页珍藏版）》请在三一办公上搜索。
1、递归的概念递归过程与递归工作栈递归与回溯广义表,第五章 递归与广义表,递归的概念,递归的定义 若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。以下三种情况常常用到递归方法。定义是递归的 数据结构是递归的 问题的解法是递归的,定义是递归的,求解阶乘函数的递归算法long Factorial(long n)if(n=0)return 1;else return n*Factorial(n-1);,例如，阶乘函数,求解阶乘 n!的过程,主程序 main:fact(4),参数 4 计算 4*fact(3)返回 24,参
2、数 3 计算 3*fact(2)返回 6,参数 2 计算 2*fact(1)返回 2,参数 1 计算 1*fact(0)返回 1,参数 0 直接定值=1 返回 1,参数传递,结果返回,递归调用,回归求值,数据结构是递归的,一个结点，它的指针域为NULL，是一个单链表;一个结点，它的指针域指向单链表，仍是一个单链表。,例如，单链表结构,f,f,搜索链表最后一个结点并打印其数值template void Print(ListNode*f)if(f-link=NULL)cout data link);,f,f,f,f,f,a0,a1,a2,a3,a4,递归找链尾,在链表中寻找等于给定值的结点并打印其
3、数值template void Print(ListNode*f,Type,f,f,f,f,递归找含x值的结点,x,问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题的解法：如果 n=1，则将这一个盘子直接从 A 柱移到 C 柱上。否则，执行以下三步：用 C 柱做过渡，将 A 柱上的(n-1)个盘子移到 B 柱上；将 A 柱上最后一个盘子直接移到 C 柱上；用 A 柱做过渡，将 B 柱上的(n-1)个盘子移到 C 柱上。,#include#include strclass.h”void Hanoi(int n,String A,String B,String C)/解决汉诺塔
4、问题的算法 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);,(3,A,B,C),(2,A,C,B),A-C,A,B,C,(1,A,C,B),A,B,C,A-C,A-C,(1,B,A,C),A,B,C,A-C,A-B,A-BA-C,B-CC-B,A-C,(2,B,A,C),A,B,C,(1,A,C,B),A,B,C,A-C,A-C,(1,B,A,C),A,B,C,A-C,B-C,A-BB-A,B-CA-C,自顶向下、逐步分解的策略,子问题应与原问题做同样的事情，且
5、更为简单；解决递归问题的策略是把一个规模比较大的问题分解为一个或若干规模比较小的问题，分别对这些比较小的问题求解，再综合它们的结果，从而得到原问题的解。分而治之策略（分治法）这些比较小的问题的求解方法与原来问题的求解方法一样。,构成递归的条件,不能无限制地调用本身，必须有一个出口，化简为非递归状况直接处理。Procedure()if()return(initial value);else return(parameter exchange);,递归过程与递归工作栈,递归过程在实现时，需要自己调用自己。层层向下递归，退出时的次序正好相反：递归调用 n!(n-1)!(n-2)!1!0!=1 返回次
6、序主程序第一次调用递归过程为外部调用；递归过程每次递归调用自己为内部调用。它们返回调用它的过程的地址不同。,递归工作栈,每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。,局部变量返回地址参 数,活动记录框架,递归工作记录,函数递归时的活动记录,.,Function().,调用块,函数块,返回地址(下一条指令)局部变量 参数,long Factorial(long n)int temp;if(n=0)return 1;else temp=n*Factorial(n-1);RetLoc2 return temp;,
7、void main()int n;n=Factorial(4);RetLoc1,计算Fact时活动记录的内容,递归调用序列,0 1 RetLoc2,1 1 RetLoc2,2 2 RetLoc2,3 6 RetLoc2,4 24 RetLoc1,参数 返回值 返回地址 返回时的指令,return 4*6/返回 24,return 3*2/返回 6,return 1/返回 1,return 1*1/返回 1,return 2*1/返回 2,递归过程改为非递归过程,递归过程简洁、易编、易懂；递归过程效率低，重复计算多；改为非递归过程的目的是提高效率；单向递归和尾递归可直接用迭代实现其非递归过程；其
8、他情形必须借助栈实现非递归过程。,计算斐波那契数列的函数Fib(n)的定义,求解斐波那契数列的递归算法 long Fib(long n)if(n=1)return n;else return Fib(n-1)+Fib(n-2);,如 F0=0,F1=1,F2=1,F3=2,F4=3,F5=5,调用次数 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),Fib(1
9、),Fib(0),Fib(2),Fib(1),Fib(0),Fib(2),Fib(1),Fib(3),Fib(4),栈结点,n tag,tag=1,向左递归；tag=2,向右递归。,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+1,2 23 14 1,n=2-2,3 14 1,n=0sum=1+0,3 24 1,n=3-2,4 1,n=1sum=1+1,4 2,n=4-2,Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(2),Fib(1),Fib(
10、3),Fib(4),2 14 2,n=1sum=2+1,2 24 2,n=2-2,4 2,n=0sum=3+0,long Fibnacci(long n)Stack S;Node w;long sum=0;/反复执行直到所有终端结点数据累加完 do while(n 1)w.n=n;w.tag=1;S.push(w);n-;/向左递归到底,边走边进栈 sum=sum+n;/执行求和,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;whil
11、e(!S.IsEmpty();return sum;,单向递归用迭代法实现,long FibIter(long n)if(n=1)return n;long twoback=0,oneback=1,Current;for(int i=2;i=n;i+)Current=twoback+oneback;twoback=oneback;oneback=Current;return Current;,void recfunc(int A,int n)if(n=0)cout An“”;n-;recfunc(A,n);,25 36 72 18 99 49 54 63,尾递归用迭代法实现,void ster
12、func(int A,int n)/消除了尾递归的非递归函数 while(n=0)cout value An endl;n-;,递归与回溯 常用于搜索过程,对一个包含有许多结点，且每个结点有多个分支的问题，可以先选择一个分支进行搜索。当搜索到某一结点，发现无法再继续搜索下去时，可以沿搜索路径回退到前一结点，沿另一分支继续搜索。如果回退之后没有其他选择，再沿搜索路径回退到更前结点，。依次执行，直到搜索到问题的解，或搜索完全部可搜索的分支没有解存在为止。回溯法与分治法本质相同，可用递归算法求解。,n皇后问题 在 n 行 n 列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称为它们
13、为互相攻击。n皇后问题是指找到这 n 个皇后的互不攻击的布局。,1#主对角线3#主对角线5#主对角线,0#次对角线2#次对角线4#次对角线6#次对角线,1#次对角线3#次对角线5#次对角线,0#主对角线2#主对角线4#主对角线6#主对角线,0 1 2 3,0123,k=i+j,k=n+i-j-1,解题思路,安放第 i 行皇后时，需要在列的方向从 0 到 n-1 试探(j=0,n-1)。在第 j 列安放一个皇后：如果在列、主对角线、次对角线方向有其他皇后，则出现攻击，撤消在第 j 列安放的皇后。如果没有出现攻击，在第 j 列安放的皇后不动，递归安放第 i+1行皇后。,设置 4 个数组 col n
14、：coli 标识第 i 列是否安放了皇后；md2n-1:mdk 标识第 k 条主对角线是否安放了皇后；sd2n-1:sdk 标识第 k 条次对角线是否安放了皇后；qn:qi 记录第 i 行皇后在第几列。,void Queen(int i)for(int j=0;j n;j+)if(第 i 行第 j 列没有攻击)在第 i 行第 j 列安放皇后；if(i=n-1)输出一个布局；else Queen(i+1);撤消第 i 行第 j 列的皇后；,算法求精void Queen(int i)for(int j=0;j n;j+)if(!colj/*在第 i 行第 j 列安放皇后*/,if(i=n-1)/*
15、输出一个布局*/for(k=0;k n;k+)cout qk,;cout endl;else Queen(i+1);colj=mdn+i-j-1=sdi+j=0;qi=0;/*撤消第 i 行第 j 列的皇后*/,迷宫问题,小型迷宫,路口 动作 结果 1(入口)正向走 进到 2 2 左拐弯 进到 3 3 右拐弯 进到 4 4(堵死)回溯 退到 3 3(堵死)回溯 退到 2 2 正向走 进到 5 5(堵死)回溯 退到 2 2 右拐弯 进到 6 6 左拐弯 进到 7(出口),43,521,76,6 左 0 直 2 右 0 行 3 行 5 行 6 0 0 4 0 0 0 0 0 0 7 0 0 7,小
16、型迷宫的数据,迷宫的类定义#include#include#include class Maze private:int MazeSize;int EXIT;Intersection*intsec;public:Maze(char*filename);int TraverseMaze(int CurrentPos);,交通路口结构定义struct Intersection int left;int forward;int right;,Maze:Maze(char*filename)/构造函数：从文件 filename 中读取各路口/和出口的数据 ifstream fin;fin.open(f
17、ilename,ios:in|ios:nocreate);/为输入打开文件,文件不存在则打开失败 if(!fin)cerr MazeSize;/输入迷宫路口数,intsec=new 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
18、)/出口处理 cout CurrentPos;return 1;else/递归向左搜寻可行 if(TraverseMaze(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;,广义表(General Lists),
19、广义表的概念 n(0)个表元素组成的有 限序列，记作：LS(a0,a1,a2,an-1)LS是表名，ai是表元素，它可以是表(称 为子表)，可以是数据元素(称为原子)。n为表的长度。n=0 的广义表为空表。n 0时，表的第一个表元素称为广义表 的表头(head)，除此之外，其他表元素组 成的表称为广义表的表尾(tail)。,广义表的特性,有次序性有长度,有深度可共享,可递归,A()B(6,2)head(B)=6,tail(B)=(2)C(a,(5,3,x)D(B,C,A)head(C)=aE(B,D)tail(C)=(5,3,x)F(4,F)head(5,3,x)=(5,3,x)tail(5,
20、3,x)=(),广义表的表示,只包括整数和字符型数据的广义表链表表示,表中套表情形下的广义表链表表示,5,2,3,2,4,3,6,10,3,9,14,list2,5,list1,12,47,a,s,广义表结点定义,结点类型 utype=0,表头；=1,整型原子；=2,字符型原子；=3,子表。值value utype=0时,存放引用计数(ref)；utype=1时,存放整数值(intinfo)；utype=2时,存放字符型数据(charinfo)；utype=3时,存放指向子表表头的指针(hlink)。尾指针tlink utype=0时,指向该表第一个结点；utype0时,指向同一层下一个结点。
21、,utype value tlink,广义表的存储表示,E,B,F,0 1,1 4,3,0 0,3,3,D,0 1,1 5,1 3,2 x,0 1,2 a,3,C,0 1,3,3,3,0 2,1 6,D,B,B,C,A,1 2,0 1,A,广义表的类定义,class GenList;/GenList类的前视声明class GenListNode;/广义表结点类的前视声明struct Items/仅有结点信息的项friend class GenlistNode;friend class Genlist;int utype;/0/1/2/3 union/联合,int ref;/utype=0,存放
22、引用计数 int intinfo;/utype=1,存放整数值 char charinfo;/utype=2,存放字符 GenListNode*hlink;/utype=3,存放指向子表的指针 value;class GenListNode/广义表结点类定义friend class Genlist;private:int utype;/0/1/2/3,GenListNode*tlink;/下一结点指针 union/联合 int ref;/utype=0,存放引用计数 int intinfo;/utype=1,存放整数值 char charinfo;/utype=2,存放字符 GenListNo
23、de*hlink;/utype=3,存放指向子表的指针 value;public:GenListNode():utype(0),tlink(NULL),ref(0)/构造函数,建表头结点,GenListNode(int t,GenListNode*next=NULL)/构造函数：建表结点 Items Info();/返回当前表元素的值 int nodetype()return utype;/返回当前表元素的数据类型 void setInfo(Items,class GenList/广义表类定义 private:GenListNode*first;/广义表头指针 GenListNode*Copy
24、(GenListNode*ls);/复制一个 ls 指示的无共享非递归表 int depth(GenListNode*ls);/计算由 ls 指示的非递归表的深度 int equal(GenListNode*s,GenListNode*t);/比较以s和t为表头的两个表是否相等 void Remove(GenListNode*ls);/释放以 ls 为表头结点的广义表,public:Genlist();/构造函数 GenList();/析构函数 Items Head();/返回表头元素 GenList Tail();/返回表尾 GenListNode*First();/返回第一个元素 GenL
25、istNode*Next(GenListNode*elem);/返回表元素elem的直接后继元素 GenList Addon(GenList/将表结点 x 加到表的最前端,void setNext(GenListNode*elem1,GenListNode*elem2);/将elem2插到表中元素elem1后 void Copy(const GenList/从广义表的字符串描述 s 出发,/建立一个带表头结点的广义表结构,广义表的访问算法,广义表结点类的存取成员函数Items GenListNode:Info()/返回表元素的值 Items pitem;pitem.utype=utype;pi
26、tem.value=value;return pitem;,void GenListNode:setInfo(Items,Items GenList:Head()/若广义表非空，则返回其第一个元素的值，/否则函数没有定义。if(first-tlink=NULL)return NULL;else/非空表 Items temp;temp.utype=frist-tlink-utype;temp.value=frist-tlink-value;return temp;/返回类型及值,GenList GenList:Tail()/若广义表非空，则返回广义表除第一个元/素外其它元素组成的表,否则函数没有
27、定义 if(frist-tlink=NULL)return NULL;GenList temp;temp.first=new GenListNode;temp.first-utype=0;temp.first-value.ref=0;temp.first-tlink=Copy(first-tlink-tlink);return temp;,GenListNode*GenList:First()if(first-tlink=NULL)return NULL;else return first-tlink;GenListNode*GenList:Next(GenListNode*elem)if(e
28、lem-tlink=NULL)return NULL;else return elem-tlink;,GenList,void GenList:Push(GenListNode,广义表的递归算法,广义表的复制算法void GenList:Copy(const GenList,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-v
29、alue.hlink=Copy(ls-value.hlink);,q-tlink=Copy(ls-tlink);return q;,求广义表的深度,例如，对于广义表 E(B(a,b),D(B(a,b),C(u,(x,y,z),A(),1,1,1,1,2,3,4,int GenList:depth(GenListNode*ls)if(ls-tlink=NULL)return 1;/空表 GenListNode*temp=ls-tlink;int m=0;while(temp!=NULL)/在表顶层横扫 if(temp-utype=3)/结点为表结点 int n=depth(temp-value.
30、hlink);if(m tlink;return m+1;,int GenList:depth()return depth(first);,广义表的删除算法,0 1,1 5,3,3,1 2,0 1,2 x,0 1,0 1,2 y,ls,3,2 x,扫描子链表 若结点数据为x,删除。可能做循环连续删。若结点数据不为x，不执行删除。若结点为子表，递归在子表执行删除。,扫描子链表 若结点数据为x,删除。可能做循环连续删。若结点数据不为x，不执行删除。若结点为子表，递归在子表执行删除。,void delvalue(GenListNode*ls,const value x)/在广义表中删除所有含 x 的
31、结点 if(ls-tlink!=NULL)/非空表 GenListNode*p=ls-tlink;,while(p!=NULL,delvalue(p,x);/在后续链表中删除 GenList:GenList()/析构函数 Remove(first);delete(first);void GenList:Remove(GenListNode*ls)/私有函数：释放以 ls 为表头指针的广义表 ls-value.ref-;/引用计数减1,if(ls-value.ref tlink!=NULL)q=ls-tlink;/到第一个结点 if(q-utype=3)/递归删除子表 Remove(q-valu
32、e.hlink);if(q-value.hlink-value.ref value.hlink;ls-tlink=q-tlink;delete q;,从字符串s 建立广义表的链表表示 lsint Genlist:CreateList(GenListNode*ls,char*s)char*sub,*hsub;int tag;ls=new GenListNode();/建立表头结点 ls-utype=HEAD;ls-value.ref=1;if(strlen(s)=0|!strcmp(s,()ls-tlink=NULL;/空表 else strncpy(sub,s+1,strlen(s)-2);/
33、脱去广义表外面的引号,GenListNode*p=ls;while(strlen(sub)!=0)/建立表结点 p=p-tlink=new GenListNode();/创建新结点,向表尾链接 if(sever(sub,hsub)/以逗号为界,分离第一个表元素hsub if(hsub0!=(else,if(hsub0!=(/字符串表达式有错/循环完成,p-tlink=NULL;/封闭最后一个结点 return 1;int Genlist:sever(char*str1,char*hstr1)/对不含外分界符的字符串分离第一个元素 char ch=str10;int n=strlen(str1);int i=0,k=0;/检测str1,扫描完或遇到,且括号配对则停,while(i n,else if(k!=0)return 0;/括号不配对出错 else/括号配对 strcpy(hstr1,str1);str1=0;/str1全部传送给hstr1 return 1;,设 str=(2,(b,7),(),(d),得到的广义表链表结构,
