辽宁石油化工大学数据结构课件-递归与广义表

递归的概念递归过程与递归工作栈递归与回溯广义表递归的概念递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。以下三种情况常常用到递归方法。定义是递归的数据结构是递归的问题的解法是递归的定义是递归的求解阶乘函数的递归算法longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);}例如，阶乘函数时当时当1,)!1(0,1!nnnnn求解阶乘n!的过程主程序main: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参数传递结果返回递归调用回归求值数据结构是递归的一个结点，它的指针域为NULL，是一个单链表;一个结点，它的指针域指向单链表，仍是一个单链表。例如，单链表结构ff搜索链表最后一个结点并打印其数值templateclassTypevoidPrint(ListNodeType*f){if(f-link==NULL)coutf-dataendl;elsePrint(f-link);}fffffa0a1a2a3a4递归找链尾在链表中寻找等于给定值的结点并打印其数值templateclassTypevoidPrint(ListNodeType*f,Type&x){if(f!=NULL)if(f-data==x)coutf-dataendl;elsePrint(f-link,x);}ffff递归找含x值的结点x问题的解法是递归的例如，汉诺塔(TowerofHanoi)问题的解法：如果n=1，则将这一个盘子直接从A柱移到C柱上。否则，执行以下三步：①用C柱做过渡，将A柱上的(n-1)个盘子移到B柱上：②将A柱上最后一个盘子直接移到C柱上；③用A柱做过渡，将B柱上的(n-1)个盘子移到C柱上。#includeiostream.h#includestrclass.h”voidHanoi(intn,StringA,StringB,StringC){//解决汉诺塔问题的算法if(n==1)coutmoveAtoCendl;else{Hanoi(n-1,A,C,B);coutmoveAtoCendl;Hanoi(n-1,B,A,C);}}递归过程与递归工作栈递归过程在实现时，需要自己调用自己。层层向下递归，退出时的次序正好相反：递归调用n!(n-1)!(n-2)!1!0!=1返回次序主程序第一次调用递归过程为外部调用；递归过程每次递归调用自己为内部调用。它们返回调用它的过程的地址不同。递归工作栈每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。局部变量返回地址参数活动记录框架递归工作记录函数递归时的活动记录……………….下一条指令Function(参数表)……………….return调用块函数块返回地址(下一条指令)局部变量参数longFactorial(longn){inttemp;if(n==0)return1;elsetemp=n*Factorial(n-1);RetLoc2returntemp;}voidmain(){intn;n=Factorial(4);RetLoc1}计算Fact时活动记录的内容递归调用序列0RetLoc21RetLoc22RetLoc23RetLoc24RetLoc1参数返回地址返回时的指令RetLoc1return4*6//返回24RetLoc2return3*2//返回6RetLoc2return1//返回1RetLoc2return1*1//返回1RetLoc2return2*1//返回2递归过程改为非递归过程递归过程简洁、易编、易懂递归过程效率低，重复计算多改为非递归过程的目的是提高效率单向递归和尾递归可直接用迭代实现其非递归过程其他情形必须借助栈实现非递归过程计算斐波那契数列的函数Fib(n)的定义求解斐波那契数列的递归算法longFib(longn){if(n=1)returnn;elsereturnFib(n-1)+Fib(n-2);}1n2),Fib(n1)Fib(n0,1nn,)Fib(n如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)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)栈结点ntagtag=1,向左递归；tag=2,向右递归Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)213141n=1sum=0+1223141n=2-23141n=0sum=1+03241n=3-241n=1sum=1+142n=4-2Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)2142n=1sum=2+12242n=2-242n=0sum=3+0longFibnacci(longn){StackNodeS;Node*w;longsum=0;//反复执行直到所有终端结点数据累加完do{while(n1){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;}}}while(!S.IsEmpty());returnsum;}单向递归用迭代法实现longFibIter(longn){if(n=1)returnn;longtwoback=0,oneback=1,Current;for(inti=2;i=n;i++){Current=twoback+oneback;twoback=oneback;oneback=Current;}returnCurrent;}voidrecfunc(intA[],intn){if(n=0){coutA[n]“”;n--;recfunc(A,n);}}2536721899495463尾递归用迭代法实现voidsterfunc(intA[],intn){//消除了尾递归的非递归函数while(n=0){coutvalueA[n]endl;n--;}}递归与回溯常用于搜索过程n皇后问题在n行n列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称为它们为互相攻击。n皇后问题是指找到这n个皇后的互不攻击的布局。1#主对角线3#主对角线5#主对角线0#次对角线2#次对角线4#次对角线6#次对角线1#次对角线3#次对角线5#次对角线0#主对角线2#主对角线4#主对角线6#主对角线01230123k=i+jk=n+i-j-1解题思路安放第i行皇后时，需要在列的方向从0到n-1试探(j=0,…,n-1)在第j列安放一个皇后：如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第j列安放的皇后。如果没有出现攻击，在第j列安放的皇后不动，递归安放第i+1行皇后。设置4个数组col[n]：col[i]标识第i列是否安放了皇后md[2n-1]:md[k]标识第k条主对角线是否安放了皇后sd[2n-1]:sd[k]标识第k条次对角线是否安放了皇后q[n]:q[i]记录第i行皇后在第几列voidQueen(inti){for(intj=0;jn;j++){if(第i行第j列没有攻击){在第i行第j列安放皇后；if(i==n-1)输出一个布局；elseQueen(i+1);}撤消第i行第j列的皇后；}}算法求精voidQueen(inti){for(intj=0;jn;j++){if(!col[j]&&!md[n+i-j-1]&&!sd[i+j]){/*第i行第j列没有攻击*/col[j]=md[n+i-j-1]=sd[i+j]=1;q[i]=j;/*在第i行第j列安放皇后*/if(i==n-1){/*输出一个布局*/for(j=0;jn;j++)coutq[j]‘,’;coutendl;}elseQueen(i+1);}col[j]=md[n+i-j-1]=sd[i+j]=0;q[i]=0;/*撤消第i行第j列的皇后*/}}广义表(GeneralLists)广义表的概念n(0)个表元素组成的有限序列，记作LS=(a0,a1,a2,…,an-1)LS是表名，ai是表元素，它可以是表(称为子表)，可以是数据元素(称为原子)。n为表的长度。n=0的广义表为空表。n0时，表的第一个表元素称为广义表的表头(head)，除此之外，其它表元素组成的表称为广义表的表尾(tail)。广义表的特性有次序性有长度A=()B=(6,2)C=(‘a’,(5,3,‘x’))D=(B,C,A)E=(B,D)F=(4,F)有深度可共享可递归广义表的表示只包括整数和字符型数据的广义表链表表示表中套表情形下的广义表链表表示5232436103914list25list11247‘a’‘s’广义表结点定义结点类型utype=0,表头；=1,整型原子；=2,字符型原子；=3,子表值valueutype=0时,存放引用计数(ref)；utype=1时,存放整数值(intinfo)；utype=2时,存放字符型数据(charinfo)；utype=3时,存放指向子表表头的指针(hlink)尾指针tlinkutype=0时,指向该表第一个结点；utype0时,指向同一层下一个结点utypevaluetlink广义表的存储表示EBF011430133D0115132‘x’012‘a’3C013330116DBBCA1201A广义表的类定义classGenList;//GenList类的前视声明classGenListNode{//广义表结点类的前视声明structItems{//仅有结点信息的项friendclassGenlistNode;friendclassGenlist;intutype;//＝0/1/2/3union{//联合intref;//utype=0,存放引用计数intintinfo;//utype=1,存放整数值charcharinfo;//utype=2,存放字符GenListNode*hlink;//utype=3,存放指向子表的指针}}classGenListNode{//广义表结点类定义friendclassGenlist;private:intutype;//＝0/1/2/3GenListNode*tlink;//下一结点指针union{//联合intref;//utype=0,存放引用计数intintinfo;//utype=1,存放整数值charcharinfo;//utype=2,存放字符GenListNode*hlink;//utype=3,存放指向子表的指针}valu