数据结构第05章(清华殷人昆版)学习教案.pptx

《数据结构第05章(清华殷人昆版)学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构第05章(清华殷人昆版)学习教案.pptx（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构数据结构(sh j ji u)第第05章章(清华清华 殷人昆版殷人昆版)第一页，共61页。递归的概念递归的概念(ginin)n n递归的定义递归的定义 若一个对象部分若一个对象部分地包含它自己地包含它自己(zj),或用或用它自己它自己(zj)给自己给自己(zj)定义定义,则称这个对象是递归则称这个对象是递归的；若一个过程直接地或间的；若一个过程直接地或间接地调用自己接地调用自己(zj),则称这则称这个过程是递归的过程。个过程是递归的过程。n n以下三种情况常常用到递归以下三种情况常常用到递归方法。方法。n n 定义是递归的定义是递归的n n 数据结构是递归的数据结构是递归的n

2、n 问题的解法是递归的问题的解法是递归的第1页/共61页第二页，共61页。定义定义(dngy)是递是递归的归的求解求解(qi ji)阶乘函数的递归算阶乘函数的递归算法法long Factorial(long n)if(n=0)return 1;else return n*Factorial(n-1);例如例如例如例如(lr)(lr)，阶乘函数，阶乘函数，阶乘函数，阶乘函数第2页/共61页第三页，共61页。求解阶乘求解阶乘(ji chn)n!的过程的过程主程序主程序主程序主程序 main:fact(4)参数参数 4 计算计算(j sun)4*fact(3)返回返回 24参数参数(cnsh)3 计

3、算计算 3*fact(2)返回返回 6参数参数 2 计算计算 2*fact(1)返回返回 2参数参数 1 计算计算 1*fact(0)返回返回 1参数参数 0 直接定值直接定值=1 返回返回 1参参参参数数数数传传传传递递递递结结结结果果果果返返返返回回回回递递递递归归归归调调调调用用用用回回回回归归归归求求求求值值值值第3页/共61页第四页，共61页。数据结构数据结构(sh j(sh j ji u)ji u)是递归的是递归的n n 一个一个一个一个(y)(y)(y)(y)结点，它的指针域为结点，它的指针域为结点，它的指针域为结点，它的指针域为NULLNULLNULLNULL，是一个，是一个，

4、是一个，是一个(y)(y)(y)(y)单链表单链表单链表单链表;n n 一个一个一个一个(y)(y)(y)(y)结点，它的指针域指向结点，它的指针域指向结点，它的指针域指向结点，它的指针域指向单链表，仍是一个单链表，仍是一个单链表，仍是一个单链表，仍是一个(y)(y)(y)(y)单链表。单链表。单链表。单链表。例如例如例如例如(lr)(lr)，单链表结构，单链表结构，单链表结构，单链表结构f f 第4页/共61页第五页，共61页。搜索链表最后搜索链表最后搜索链表最后搜索链表最后(zuhu)(zuhu)(zuhu)(zuhu)一个结点并打印一个结点并打印一个结点并打印一个结点并打印其数值其数值其

5、数值其数值template template template template void Print(ListNode*f)void Print(ListNode*f)void Print(ListNode*f)void Print(ListNode*f)if(f-link=NULL)if(f-link=NULL)if(f-link=NULL)if(f-link=NULL)cout data endl;cout data endl;cout data endl;cout data link);else Print(f-link);else Print(f-link);else Print(f

6、-link);f f f f f a0a1a2a3a4递归找链尾第5页/共61页第六页，共61页。在链表中寻找等于给定值的结点在链表中寻找等于给定值的结点在链表中寻找等于给定值的结点在链表中寻找等于给定值的结点(ji(ji didi n)n)并打印其数值并打印其数值并打印其数值并打印其数值template template void Print(ListNode*f,Type&x void Print(ListNode*f,Type&x)if(f!=NULL)if(f!=NULL)if(f-data=x)if(f-data=x)cout data endl;cout data link,x);

7、else Print(f-link,x);f f f f 递归找含x值的结点(ji din)x第6页/共61页第七页，共61页。问题的解法是递归的问题的解法是递归的 例如，汉诺塔例如，汉诺塔(Tower of Hanoi)问问题的解法：题的解法：如果如果 n=1，则将这一个盘子，则将这一个盘子(pn zi)直接从直接从 A 柱移到柱移到 C 柱上。柱上。否则，执行以下三步：否则，执行以下三步：用用 C 柱做过渡，将柱做过渡，将 A 柱上柱上的的(n-1)个盘子个盘子(pn zi)移到移到 B 柱柱上：上：将将 A 柱上最后一个盘子柱上最后一个盘子(pn zi)直接移到直接移到 C 柱上；柱上；

8、用用 A 柱做过渡，将柱做过渡，将 B 柱上柱上的的(n-1)个盘子个盘子(pn zi)移到移到 C 柱柱上。上。第7页/共61页第八页，共61页。第8页/共61页第九页，共61页。#include#include strclass.h”void Hanoi(int n,String A,String B,String C)/解决汉诺塔问题解决汉诺塔问题(wnt)的算法的算法 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页第十页，共61页。递归过

9、程递归过程(guchng)与递与递归工作栈归工作栈n n递归过程在实现时，需要自己递归过程在实现时，需要自己调用自己。调用自己。n n层层向下递归，退出时的次序层层向下递归，退出时的次序正好相反正好相反(xingfn)：n n 递归调用递归调用n n n!(n-1)!(n-2)!1!0!=1n n 返回次序返回次序n n主程序第一次调用递归过程为主程序第一次调用递归过程为外部调用；外部调用；n n递归过程每次递归调用自己为递归过程每次递归调用自己为内部调用。内部调用。n n它们返回调用它的过程的地址它们返回调用它的过程的地址不同。不同。第10页/共61页第十一页，共61页。递归工作栈递归工作栈

10、n n每一次递归调用时，需要为过每一次递归调用时，需要为过程中使用的参数、局部变量等程中使用的参数、局部变量等另外分配存储空间另外分配存储空间(kngjin)。n n每层递归调用需分配的空间每层递归调用需分配的空间(kngjin)形成递归工作记录，形成递归工作记录，按后进先出的栈组织。按后进先出的栈组织。局部变量局部变量局部变量局部变量返回返回返回返回(fnhu)(fnhu)地址地址地址地址参参参参 数数数数活动活动活动活动记录记录记录记录(jl(jl)框框框框架架架架递归递归工作记录工作记录第11页/共61页第十二页，共61页。函数函数函数函数(hnsh)(hnsh)递归时的活动记递归时的活

11、动记递归时的活动记递归时的活动记录录录录.Function().调用(dioyng)块函数块返回地址返回地址(下一条指令下一条指令)局部变量局部变量 参数参数第12页/共61页第十三页，共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页第十四页，共61页。计算计算计算计算FactFact时活动记录时活动记录时活动记录时活动记录(jl)(jl)的的的的内

12、容内容内容内容递递递递归归归归调调调调用用用用(d diio oy y n ng g)序序序序列列列列0 RetLoc21 RetLoc22 RetLoc23 RetLoc24 RetLoc1参数参数参数参数(cnsh)(cnsh)(cnsh)(cnsh)返回地址返回地址返回地址返回地址 返回时的指令返回时的指令返回时的指令返回时的指令RetLoc1 return 4*6 /返回返回返回返回2424 RetLoc2 return 3*2 /返回返回返回返回6 6 RetLoc2 return 1 /返回返回返回返回1 1 RetLoc2 return 1*1 /返回返回返回返回1 1 RetL

13、oc2 return 2*1 /返回返回返回返回2 2 第14页/共61页第十五页，共61页。递归过程递归过程(guchng)改为非递归改为非递归过程过程(guchng)n n递归过程简洁、易编、易懂递归过程简洁、易编、易懂递归过程简洁、易编、易懂递归过程简洁、易编、易懂n n递归过程效率低，重复计算多递归过程效率低，重复计算多递归过程效率低，重复计算多递归过程效率低，重复计算多n n改为非递归过程的目的是提高效率改为非递归过程的目的是提高效率改为非递归过程的目的是提高效率改为非递归过程的目的是提高效率n n单向递归和尾递归可直接单向递归和尾递归可直接单向递归和尾递归可直接单向递归和尾递归可直

14、接(zhji)(zhji)用迭代实现其非递归过程用迭代实现其非递归过程用迭代实现其非递归过程用迭代实现其非递归过程n n其他情形必须借助栈实现非递归过其他情形必须借助栈实现非递归过其他情形必须借助栈实现非递归过其他情形必须借助栈实现非递归过程程程程第15页/共61页第十六页，共61页。计算斐波那契数列的函数计算斐波那契数列的函数计算斐波那契数列的函数计算斐波那契数列的函数(hnsh)Fib(n)(hnsh)Fib(n)的定义的定义的定义的定义求解求解求解求解(qi ji)(qi ji)(qi ji)(qi ji)斐波那契数列的递归算法斐波那契数列的递归算法斐波那契数列的递归算法斐波那契数列的递

15、归算法 long Fib(long n)long Fib(long n)long Fib(long n)long Fib(long n)if(n=1)return n;if(n=1)return n;if(n=1)return n;if(n=1)return n;else return Fib(n-1)+Fib(n-2);else return Fib(n-1)+Fib(n-2);else return Fib(n-1)+Fib(n-2);else return Fib(n-1)+Fib(n-2);如如如如 F F0 0=0,F=0,F1 1=1,F=1,F2 2=1,F=1,F3 3=2,F

16、=2,F4 4=3,F=3,F5 5=5 =5 第16页/共61页第十七页，共61页。调用调用调用调用(dioyng)(dioyng)次数次数次数次数 NumCall(k)=NumCall(k)=2*Fib(k+1)-12*Fib(k+1)-1。斐波那契数列斐波那契数列(shli)(shli)的递归调用树的递归调用树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页第十八页，共61页。Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fi

17、b(2)Fib(1)Fib(3)Fib(4)栈结点栈结点栈结点栈结点(ji din)(ji din)n tagtag=1,向左递归；向左递归；tag=2,向右递归向右递归第18页/共61页第十九页，共61页。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页第二十页，共61页。Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib

18、(1)Fib(3)Fib(4)2 14 2 n=1sum=2+12 24 2n=2-24 2 n=0sum=3+0第20页/共61页第二十一页，共61页。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-;/向向左左递递归归到到底底(do d),边边走边进栈走边进栈 sum=sum+n;/执执行行求求和和 第21页/共61页第二十二页，共61页。while(!S.IsEmpty()w=S.getTop(

19、);S.Pop();if(w-tag=1)/改为(i wi)向右递归 w-tag=2;S.push(w);n=w-n 2;/F(n)右侧为F(n-2)break;while(!S.IsEmpty();return sum;第22页/共61页第二十三页，共61页。单向单向(dn xin)递归用递归用迭代法实现迭代法实现long FibIter(long n)if(n=1)return n;long twoback=0,oneback=1,Current;for(int i=2;i=0)cout An=0)cout value An endl;n-;第25页/共61页第二十六页，共61页。递归与回

20、溯递归与回溯(hu s)(hu s)常用于搜索常用于搜索过程过程n皇后问题皇后问题 在在 n 行行 n 列的国际象棋棋盘上，列的国际象棋棋盘上，若两个若两个(lin)皇后位于同一行、皇后位于同一行、同一列、同一对角线上，则称为它同一列、同一对角线上，则称为它们为互相攻击。们为互相攻击。n皇后问题是指找皇后问题是指找到这到这 n 个皇后的互不攻击的布局。个皇后的互不攻击的布局。第26页/共61页第二十七页，共61页。1#主对角线主对角线3#主对角线主对角线5#主对角线主对角线0#次对角线次对角线2#次对角线次对角线4#次对角线次对角线6#次对角线次对角线1#次对角线次对角线3#次对角线次对角线5

21、#次对角线次对角线0#主对角线主对角线2#主对角线主对角线4#主对角线主对角线6#主对角线主对角线0 1 2 3 0123k=i+jk=n+i-j-1第27页/共61页第二十八页，共61页。解题解题(ji t)思路思路n n安放第安放第 i 行皇后时，需要在列行皇后时，需要在列的方向从的方向从 0 到到 n-1 试探试探(j=0,n-1)n n在第在第 j 列安放一个皇后：列安放一个皇后：n n如果在列、主对角线、次对角如果在列、主对角线、次对角线方向有其它皇后，则出现攻线方向有其它皇后，则出现攻击，撤消击，撤消(chxio)在第在第 j 列列安放的皇后。安放的皇后。n n如果没有出现攻击，在

22、第如果没有出现攻击，在第 j 列列安放的皇后不动，递归安放第安放的皇后不动，递归安放第 i+1行皇后。行皇后。第28页/共61页第二十九页，共61页。n n设置设置设置设置 4 4 个数组个数组个数组个数组n n col n col n：coli coli 标识第标识第标识第标识第 i i 列是否安放列是否安放列是否安放列是否安放了皇后了皇后了皇后了皇后(hunghu)(hunghu)n n md2n-1:mdk md2n-1:mdk 标识第标识第标识第标识第 k k 条主对角条主对角条主对角条主对角线是否安放了皇后线是否安放了皇后线是否安放了皇后线是否安放了皇后(hunghu)(hunghu

23、)n n sd2n-1:sdk sd2n-1:sdk 标识第标识第标识第标识第 k k 条次对角线条次对角线条次对角线条次对角线是否安放了皇后是否安放了皇后是否安放了皇后是否安放了皇后(hunghu)(hunghu)n n qn:qi qn:qi 记录第记录第记录第记录第 i i 行皇后行皇后行皇后行皇后(hunghu)(hunghu)在第几列在第几列在第几列在第几列第29页/共61页第三十页，共61页。void Queen(int i)for(int j=0;j n;j+)if(第第 i 行第行第 j 列没有攻击列没有攻击)在第在第 i 行第行第 j 列安放皇后；列安放皇后；if(i=n-1

24、)输出一个布输出一个布局局(bj)；else Queen(i+1);撤消第撤消第 i 行第行第 j 列的皇后；列的皇后；第30页/共61页第三十一页，共61页。算法求精算法求精算法求精算法求精void Queen(int i)void Queen(int i)for(int j=0;j n;j+)for(int j=0;j n;j+)if(!colj&!mdn+i-j-1&!sdi+j)if(!colj&!mdn+i-j-1&!sdi+j)/*/*第第第第 i i 行第行第行第行第 j j 列没有攻击列没有攻击列没有攻击列没有攻击*/*/colj=mdn+i-j-1=sdi+j=1;colj=

25、mdn+i-j-1=sdi+j=1;qi=j;qi=j;/*/*在第在第在第在第 i i 行第行第行第行第 j j 列安放列安放列安放列安放(nfng)(nfng)皇后皇后皇后皇后*/*/第31页/共61页第三十二页，共61页。if(i=n-1)/*输出一个布局输出一个布局*/for(j=0;j n;j+)cout qj ,;cout 0 n 0时，表的第一个表元素称为广义时，表的第一个表元素称为广义时，表的第一个表元素称为广义时，表的第一个表元素称为广义(gungy)(gungy)表表表表nn 的表头的表头的表头的表头(head)(head)，除此之外，其它表元素组，除此之外，其它表元素组，

26、除此之外，其它表元素组，除此之外，其它表元素组nn 成的表称为广义成的表称为广义成的表称为广义成的表称为广义(gungy)(gungy)表的表尾表的表尾表的表尾表的表尾(tail)(tail)。第33页/共61页第三十四页，共61页。广义广义(gungy)表的特性表的特性n n有次序有次序有次序有次序(cx)(cx)性性性性n n有长度有长度有长度有长度A=()B=(6,2)C=(a,(5,3,x)D=(B,C,A)E=(B,D)F=(4,F)n n有深度有深度有深度有深度(shnd)(shnd)n n可共享可共享可共享可共享n n可递归可递归可递归可递归第34页/共61页第三十五页，共61页

27、。第35页/共61页第三十六页，共61页。广义广义(gungy)(gungy)表的表示表的表示只包括只包括只包括只包括(boku)(boku)(boku)(boku)整数和字符型数据的广义表链表整数和字符型数据的广义表链表整数和字符型数据的广义表链表整数和字符型数据的广义表链表表示表示表示表示 表中套表情表中套表情表中套表情表中套表情(bioqng)(bioqng)(bioqng)(bioqng)形下的广义形下的广义形下的广义形下的广义表链表表示表链表表示表链表表示表链表表示5232436103914 list25list1 1247as第36页/共61页第三十七页，共61页。广义广义广义广义

28、(gu(gu ngy)ngy)表结表结表结表结点定义点定义点定义点定义n n结结点点类类型型 utype =0,表表头头；=1,整整型型原原子子；=2,字字符符型型原原子子；=3,子表子表n n值值value utype=0时时,存存放放引引用用计计数数(ref)；utype=1时时,存存放放整整数数(zhngsh)值值(intinfo)；utype=2时时,存存放放字字符符型型数数据据(charinfo)；utype=3时时,存存放放指向子表表头的指针指向子表表头的指针(hlink)n n尾尾指指针针tlink utype=0时时,指指向向该该表表第第一一个个结结点点；utype 0时时,指

29、向同一层下一个结点指向同一层下一个结点 utype value tlinkutype value tlink 第37页/共61页第三十八页，共61页。广义广义广义广义(gungy)(gungy)(gungy)(gungy)表的表的表的表的存储表示存储表示存储表示存储表示E EBF F0 11 430 133D 0 11 51 32 x 0 12 a3 C C 0 13330 11 6D DB BBCA1 2 0 1A A 第38页/共61页第三十九页，共61页。广义广义广义广义(gungy)(gungy)表的表的表的表的类定义类定义类定义类定义class GenList;/GenList类类的

30、的前前视视声声明明class GenListNode /广义广义(gungy)表结点类的前视声明表结点类的前视声明struct Items /仅有结点信息的项仅有结点信息的项friend class GenlistNode;friend class Genlist;int utype;/0/1/2/3 union /联合联合 第39页/共61页第四十页，共61页。int ref;/utype=0,存放引用计数存放引用计数 int intinfo;/utype=1,存存放放整整数数(zhngsh)值值 char charinfo;/utype=2,存放字符存放字符 GenListNode*hli

31、nk;/utype=3,存放指向子表的指针存放指向子表的指针 class GenListNode /广义表结点类定义广义表结点类定义friend class Genlist;private:int utype;/0/1/2/3第40页/共61页第四十一页，共61页。GenListNode*tlink;/下一结点指针 union/联合 int ref;/utype=0,存放引用计数 int intinfo;/utype=1,存放整数值 char charinfo;/utype=2,存放字符(z f)GenListNode*hlink;/utype=3,存放指向子表的指针 value;public

32、:GenListNode():utype(0),tlink(NULL),ref(0)/构造函数,建表头结点第41页/共61页第四十二页，共61页。GenListNode(int t,GenListNode*next=NULL)/构造函数：建表结点 Items&Info(GenListNode*elem);/返回表元素(yun s)elem的值 int nodetype(GenListNode*elem)return elem-utype;/返回表元素(yun s)elem的数据类型 GenListNode&setInfo(Items&x);/将表元素(yun s)elem中的值修改为x;第42

33、页/共61页第四十三页，共61页。class GenList /广广义义表表类类定定义义 private:GenListNode*first;/广义表头指针广义表头指针 GenListNode*Copy(GenListNode*ls);/复复制制一一个个 ls 指指示示的的无无共共享享非递归表非递归表 int depth(GenListNode*ls);/计算由计算由 ls 指示的非递归表的深度指示的非递归表的深度 int equal(GenListNode*s,GenListNode*t);/比比较较以以s和和t为为表表头头的的两个表是否相等两个表是否相等(xingdng)void Remo

34、ve(GenListNode*ls);/释释放放以以 ls 为为表表头头结结点点的的广广义表义表第43页/共61页第四十四页，共61页。public:Genlist();/构造函数构造函数(hnsh)GenList();/析构函数析构函数(hnsh)GenListNode&Head();/返回表头元素返回表头元素 GenList&Tail();/返回表尾返回表尾 GenListNode*First();/返回第一个元素返回第一个元素 GenListNode*Next(GenListNode*elem);/返回表元素返回表元素elem的直接后继元素的直接后继元素 void setNext(Gen

35、ListNode*elem1,GenListNode*elem2);/将将elem2插到表中元素插到表中元素elem1后后 第44页/共61页第四十五页，共61页。void Copy(const GenList&l);/广义表的复制广义表的复制 int depth();/计计算算一一个个非非递递归归表表的的深深度度 int Createlist(GenListNode*ls,char*s);/从广义表的字符串描述从广义表的字符串描述 s 出发出发,/建建立立一一个个带带表表头头(bio tu)结结点点的的广广义义表表结构结构 第45页/共61页第四十六页，共61页。广义表的访问广义表的访问(f

36、ngwn)(fngwn)算法算法 广义广义广义广义(gungy)(gungy)(gungy)(gungy)表结点类的存取成员函表结点类的存取成员函表结点类的存取成员函表结点类的存取成员函数数数数Items&GenListNode:Items&GenListNode:Items&GenListNode:Items&GenListNode:Info(GenListNode*elem)Info(GenListNode*elem)Info(GenListNode*elem)Info(GenListNode*elem)/返回表元素返回表元素返回表元素返回表元素elemelemelemelem的值的值的值

37、的值 Items*pitem=new Items;Items*pitem=new Items;Items*pitem=new Items;Items*pitem=new Items;pitem-utype=elem-utype;pitem-utype=elem-utype;pitem-utype=elem-utype;pitem-utype=elem-utype;pitem-value=elem-value;pitem-value=elem-value;pitem-value=elem-value;pitem-value=elem-value;return*pitem;return*pitem

38、;return*pitem;return*pitem;第46页/共61页第四十七页，共61页。GenListNode&GenListNode:setInfo(Items&x)/修改(xigi)表元素的值为 x utype=x-utype;value=x-value;广义表类的构造和访问成员函数Genlist:GenList()/构造函数 GenListNode*first=new GenListNode();first-utype=0;first-ref=1;first-tlink=NULL;第47页/共61页第四十八页，共61页。Items&GenList:Head()/若广义表非空，则返回

39、(fnhu)其第一个元素的值，/否则函数没有定义。if(first-tlink=NULL)return NULL;else /非空表 Items*temp=new Items;temp-utype=frist-tlink-utype;temp-value=frist-tlink-value;return*temp;/返回(fnhu)类型及值 第48页/共61页第四十九页，共61页。GenList&GenList:Tail()/若广义表非空，则返回广义表除第一个元/素外其它元素组成的表,否则(fuz)函数没有定义 if(frist-tlink=NULL)return NULL;else/非空表

40、GenList*temp;temp-first=Copy(first);return*temp;第49页/共61页第五十页，共61页。GenListNode*GenList:First()if(first-tlink=NULL)return NULL;else return first-tlink;GenListNode*GenList:Next(GenListNode*elem)if(elem-tlink=NULL)return NULL;else return elem-tlink;第50页/共61页第五十一页，共61页。广义广义广义广义(gungy)(gungy)(gungy)(gung

41、y)表的递表的递表的递表的递归算法归算法归算法归算法 广义表的复制算法广义表的复制算法 void GenList:Copy(const GenList&ls)first=Copy(ls.first);/共有共有(n yu)函数函数GenListNode*GenList:Copy(GenListNode*lst)/私有函数私有函数 GenListNode*q=NULL;if(lst!=NULL)q=new GenListNode(lst-utype,NULL);第51页/共61页第五十二页，共61页。switch(ls-utype)case 0:q-value.ref=ls-value.ref;

42、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页第五十三页，共61页。q-tlink=Copy(ls-tlink);return q;第53页/共61页第五十四页，共61页。求广义求广义(gungy)(gungy)表的深度表的深度例如例如例如例如(lr)(lr)，对于广义表，对于广义表，对于广义表，对于广义表 E(B(a,b),D(B(

43、a,b),C(u,(x,y,z),A()E(B(a,b),D(B(a,b),C(u,(x,y,z),A()1111234第54页/共61页第五十五页，共61页。int GenList:depth(GenListNode*lst)if(lst-tlink=NULL)return 1;/空空表表 GenListNode*temp=lst-tlink;int m=0;while(temp!=NULL)/在在表表顶顶层层横横扫扫(hngso)if(temp-utype=3)/结点为表结点结点为表结点 int n=depth(temp-value.hlink);if(m tlink;return m+1

44、;第55页/共61页第五十六页，共61页。int GenList:depth()return depth(first);广义广义广义广义(gungy)(gungy)(gungy)(gungy)表的删除算法表的删除算法表的删除算法表的删除算法0 11 5331 2 0 12 x 0 10 12 ylsls32 x n n 扫描子链表扫描子链表扫描子链表扫描子链表n n 若结点数据为若结点数据为若结点数据为若结点数据为x,x,删除。可能做循环连续删除。可能做循环连续删除。可能做循环连续删除。可能做循环连续(linx)(linx)删。删。删。删。n n 若结点数据不为若结点数据不为若结点数据不为若结

45、点数据不为xx，不执行删除。，不执行删除。，不执行删除。，不执行删除。n n 若结点为子表，递归在子表执行删除。若结点为子表，递归在子表执行删除。若结点为子表，递归在子表执行删除。若结点为子表，递归在子表执行删除。第56页/共61页第五十七页，共61页。n n 扫描子链表扫描子链表扫描子链表扫描子链表n n 若结点若结点若结点若结点(ji din)(ji din)数据为数据为数据为数据为x,x,删除。可能做循删除。可能做循删除。可能做循删除。可能做循环连环连环连环连n n 续删。续删。续删。续删。n n 若结点若结点若结点若结点(ji din)(ji din)数据不为数据不为数据不为数据不为x

46、x，不执行删除。，不执行删除。，不执行删除。，不执行删除。n n 若结点若结点若结点若结点(ji din)(ji din)为子表，递归在子表执行删为子表，递归在子表执行删为子表，递归在子表执行删为子表，递归在子表执行删除。除。除。除。void delvalue(GenListNode*ls,const value x)/在广义在广义(gungy)表中删除所有含表中删除所有含 x 的结点的结点 if(ls-tlink!=NULL)/非空表非空表 GenListNode*p=ls-tlink;第57页/共61页第五十八页，共61页。while(p!=NULL&/横扫(hngso)链表 (p-uty

47、pe=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页/共61页第五十九页，共61页。delvalue(p,x);/在后续链表中删除 GenList:GenList()/析构函数 Remove(first);void GenList:Remove(GenListNode*ls)/私有函数：释放以 ls 为表头(bio tu)指针的广义表 ls-value.ref-;/引用计数减1第59页/共61页第六十页，共61页。if(ls-value.ref=0)/如果减到如果减到0 GenListNode*p=ls,*q;/横横扫扫表表顶顶层层(dn cn)while(p-tlink!=NULL)q=p-tlink;/到第一个结点到第一个结点 if(q-utype=3)/递归删除子表递归删除子表 Remove(q-value.hlink);p-link=q-link;delete q;第60页/共61页第六十一页，共61页。