第5章-递归数据结构课件.ppt

1、2023-2-1612023-2-162n!=1 n=0n*(n-1)!n0 若一个对象部分地包含它自己或用它自己给自己定义，则称这个对象是递归的。若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。*测试终结递归的条件 递归出口 *n问题化为n-1问题（或着大问题化为小问题）2023-2-1632023-2-1642023-2-1652023-2-1662023-2-167例2.查找非空单链表中值为x的结点，并输出之。templatevoid print(listnode*f)if(f!=null)if(f data=x)coutf dataendL;else print(f lin

2、k);2023-2-168n2023-2-1692023-2-16102023-2-16113.递归过程的实现 以上两个例子以及迷宫问题可以看到 1)递归程序十分短,十分简练,但读起来不容易.2)有很多工作由编译程序做了,编译程序要开辟:参数栈 ,局部变量栈,返回地址栈函数名,引用参数,数值参数 2023-2-16125.4 利用栈实现的迷宫问题的非递归解法数据结构:1.迷宫用二维数组表示 mazemp,但在迷宫外面加一个圈,为墙壁.Mazem+2p+2 即行数:0m+1;列数:0p+1 1 1 1 1 1 1 0 0 1 0 0 1 mazeij=0 表示该位置是通路 1 1 0 1 0 1

3、 mazeij=1 墙壁 1 0 1 0 1 1 入口:maze11 1 1 0 1 1 1 出口:mazemp 1 0 1 1 0 0 1 1 1 1 1 12023-2-16132.从ij位置,前进的方向有8个,可测探。i-1j-1 i-1j i-1j+1 ij-1 ij ij+1 i+1j-1 i+1j i+1j+1 8个方向用枚举类型来表示:enum directionsN,NE,E,SE,S,SW,W,NW3.向8个方向移动,其坐标位置要变化,具体实现放其偏移量,即:2023-2-1614Offset move8struct offsets int a,b;例如,若当前位置为ij,向

4、西南SW方向移动,则下一相邻位置gh为:g=i+moveSW.a;h=j+moveSW.b这里要指出的是,用枚举类型中的数组作为下标变量,这是一个技巧.实际上枚举类型在机内实现为整型数N-10NE-11E01SE11S10SW1-1ab.move2023-2-1615 4.为了防止重走老路,另外又建立了一个标志矩阵markm+2 p+2,初始化时都为0,一旦走到迷宫的某个位置ij,则得 markij置为1.表示下次这个位置不能再走了。mark与maze 矩阵大小一一对应.5.设立一个栈,存储在试探过程中所走过的路径,一旦要回溯,则从栈中取得刚才走过位置的坐标和前进方向.栈中需保存一个三元组 x

5、 y dir struct items 坐标 方向 int x,y,dir;2023-2-16166.具体实现算法 1.mark11=1;/11是入口 2.stackst(m*p);/开辟工作栈,大小为m*p 3.items tmp;/设一工作结构变量 tmp.x=1;tmp.y=1;tmp.dir=E;st.push(tmp);4.while(!st.IsEmpty()1）tmp=st.pop();2)int i=tmp.x;int j=tmp.y;int d=tmp.dir2023-2-1617 3)while(d=0)个表元素a0,a1,a2,an-1组成的有限序列。记作:LS=(a0,

6、a1,a2,an-1)其中每个表元素ai可以是原子,也可以是子表。原子:某种类型的对象,在结构上不可分。(用小写字母表示)子表:有结构的。(用大写字母表示)*广义表的长度:表中元素的个数2023-2-1619 *广义表的表头(head)、表尾(tail)head=a0;tail=(a1,a2,an-1)LS=（a,(b,a,b),(),c,(2)*广义表的深度:表中所含括号的最大层数 1)A=();2)B=(6,2)3)C=(a,(5,3,x)表头为a,表尾为(5,3,x)4)D=(B,C,A)5)E=(B,D)6)F=(4,F)递归的表2023-2-1620 2)广义表的性质 有序性 有长度

7、,有深度 可递归,如上面例6 可共享,如E中B为E,D所共享 各种广义表都可用一种示意图来表示,用 表示表元素,表示原子 A62Ba53xC2023-2-1621DBCA62a53xEBDCA62a53xF42023-2-16223)广义表的操作例子:list1=(5,12,s,47,a)head(list)/取第一个元素 tail(list)/tail(list1)=(12,s,47,a)first(list)/返回广义表第一个元素的指针 info(elem)/返回由elem指向的广义表节点的值 next(elem)/返回由elem指向的下一个节点的指针 nodetype(elem)/返回由

8、elem指向的广义表节点的类型 push(list,x)/将值为x的节点加入到广义表list的最前端 addon(list,x)/建立以x为头,list为尾的新表 setinfo(elem,x)/将表元素elem的值修改为x sethead(list,x)/将list的头元素重置为x2023-2-1623 4)广义表的存储结构 用数组存储显然不合适,因数组元素不同构 用拉链,但各元素类型不一致;用不等长节点不好.用等长节点来表示,每个表节点用三个域组成.标志域 值域 尾指针 utype value tlink2023-2-1624 utype=0:广义表专用的表头结点 1:整型原子结点 2:字

9、符型原子结点 3:子表节点 值域随着不同类型的节点,存放不同的内容,并用不同的名字来表示,实际上value部分可变的,用union实现.utype=0,ref:存放引用计数 utype=1,intgrinfo:存放整数值 utype=2,charinfo:存放字符型数据 utype=3,hlink:指向子表表头的指针2023-2-1625 tlink:当utype=0,tlink指向该表(表可以是子表)第一个元素的结点 当utype!=0,tlink指向该值域同一层的下一个表结点 例子:L=(3,(),(b,c),(d)utype ref tlink L 0 L 1 3 3 3 3 0 0 2

10、 b 2 c 0 3 0 3 0 2 d 2023-2-1626广义表的类声明:#define HEAD 0#define INTGR 1#define CH 2#define LIST 32023-2-1627class GenList;class GenListNodefriend class GenList;private:int utype;/=1/2/3,表示HEAD/INTGR/CH/LST GenListNode*tlink;union /联合 int ref;int intgrinfo;char charinfo;GenListNode*hlinkl value;2023-2-

11、1628Public:GenListNode&Info(GenListNode*elem);int nodetype(GenListNode*elem)return elem-utype;void setInfo(GenListNode*elem,GenListNode&x);广义表的类声明中:成员数据:first 它指向广义表的表头结点 成员函数:私有-copy，depth,equal,remove 公有-Head,tail,First,Next,push,Addon等等 2023-2-16295）广义表部分成员函数的实现算法 广义表结点类的存取成员函数 GenListNode&GenLis

12、tNode:info(GenListNode*elem)/返回表元素elem的值 GenListNode*pitem=new GenListNode;pitem-utype=elem-utype;pitem-value=elem-value;return*pitem;广义表的一些成员函数 广义表类的构造函数 first0 1 NULL2023-2-1630 GenList:GenList()GenListNode*first=new GenListNode;first-utype=0;first-value.ref=1;first-tlink=NULL;Head()-返回广义表的第一个元素值,

13、若为空表,则为非法操作.GenListNode&GenList:Head()if(first-tlink=NULL)cout“Illegal head operation.”utype=first-tlink-utype;temp-value=first-tlink-value;return*temp;2023-2-1631 取广义表的表尾-tail()(若是空表,则是非法操作)GenList GenList:Tail()if(first-tlink=NULL)cout“Illegal tail operation.”first-tlink=first-tlink-tlink;return*t

14、emp;2023-2-1632构造一个以x为第一个元素,list为尾的新表-AddonGenList&GenList:Addon(GenList&list,GenListNode&x)GenList*newList=new GenList;newList-first=copy(list.first);x-tlink=newList-first-tlink;newList-first-tlink=x;return*newlist;重新定义广义表的尾-setTailvoid GenList:setTail(GenList&list)GenListNode*temp;2023-2-1633 temp

15、=first-tlink-tlink;first-tlink-tlink=list.first-tlink;delete list.first;freelist(temp);2023-2-16346)广义表的递归算法递归算法:*递归函数的外部调用-公有函数 界面 *递归函数的内部调用-私有函数 真正实现部分 求广义表的深度 广义表的深度为广义表中最大括号的重数 广义表 LS=(a0,a1,a2,an-1),其中ai(0=itlink=NULL)return 1;GenListNode*temp=ls-tlink;int m=0;while(temp!=NULL)if(temp-utype=LS

16、T)int n=depth(temp-hlink);if(mtlink;return m+1;2023-2-1636 判断两个广义表相等否 相等的条件:具有相同的结构 对应的数据元素具有相等的值 if(两个广义表都为空表)return相等 else if(都为原子值相等)递归比较同一层的后面的表元素 else return 不相等2023-2-1637 int operator=(const GenList&l,const GenList&m)return equal(l.first,m.first);int equal(GenListNode*s,GenListNode*t)int x;if

17、(s-tlink=NULL&t-tlink=NULL)return 1;if(s-tlink!=NULL&t-tlink!=NULL&s-tlink-utype=t-tlink-utype)if(s-tlink-utype=INTGR)if(s-tlink-value.intgrinfo=t-tlink-value.intgrinfo)x=1;else x=0;else if(s-tlink-utype=CH)if(s-tlink-value.charinfo=t-tlink-value.charinfo)x=1;else x=0;else x=equal(s-tlink-value.hlin

18、k,t-tlink-value.hlink);if(x)return equal(s-tlink,t-tlink);return 0;2023-2-1638 广义表的复制算法 分别复制表头,表尾,然后合成 前提是广义表不可以是共享表或递归表2023-2-1639void GenList:copy(const GenList&l)first=copy(l.first);GenListNode*GenList:copy(GenListNode*ls)GenListNode*q=NULL;if(ls!=NULL)q=new GenListNode;q-utype=ls-utype;Switch(ls

19、-utype)case HEAD:q-value.ref=ls-value.ref;break;/表头结点 case INTGR:q-value.intgrinfo=ls-value.intgrinfo;break;case CH:q-value.charinfo=ls-value.charinfo;break;case LST:q-value.hlink=copy(ls-value.hlink);break;q-tlink=copy(ls-tlink);return q;2023-2-1640 广义表的析构函数-GenList()GenList:GenList()remove(first);void GenList:remove(GenListNode*ls)ls-value.ref-;if(!ls-value.ref)GenListNode*y=ls;while(y-tlink!=NULL)y=y-tlink;if(y-utype=LST)remove(y-hlink);y-tlink=av;av=ls;/回收顶层节点到可利用空间表中 2023-2-16412023-2-16422023-2-1643tagtlinkhlink/data2023-2-1644