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

第5章递归1.递归的概念1)定义是递归的

2)数据结构是递归的

3）问题的解法是递归的2.迷宫问题

3.递归过程的实现4.利用栈实现的迷宫问题的非递归解法5.广义表(GeneralList)1)广义表的概念(LS)2)广义表的性质3)广义表的操作4)广义表的存储结构5）广义表部分成员函数的实现算法6)广义表的递归算法求广义表的深度、判断两个广义表相等否、广义表的复制算法1/6/20231第5章递归12/1第5章递归1.递归的概念n!=1n=0n*(n-1)!n>0若一个对象部分地包含它自己或用它自己给自己定义，则称这个对象是递归的。若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。*测试终结递归的条件递归出口*n问题化为n-1问题（或着大问题化为小问题）1/6/20232第5章递归1.递归的概念n!=1n=0

三种常用到递归的方法

定义是递归的。数据结构是递归的。问题的解法是递归的。1)定义是递归的例1：如上面求n！的定义就是递归的。longfactorial(longn){if(n==0)return1;//递归终结条件elsereturnn*factorial(n-1);//n问题化为n-1问题}1/6/20233

三种常用到递归的方法

定义是递归的。12/11/下面看一下求factorial（3）F(3)f(2)f(1)f(0)

n=3n=2n=1n=06n*f(2)n*f(1)n*f(0)3*22*11*1n=3n=2n=11/6/20234下面看一下求factorial（3）F(3)例2斐波那契数列（Fibonacci)

0，1，1，2，3，5，8，……以fn表示数列中第n个数，fn的递归定义：n当n=0，1时Fib(n)=Fib(n-1)+Fib(n-2)当n>1时longFib(longn){if(n<=1)returnn;elsereturnFib(n-1)+Fib(n-2);}1/6/20235例2斐波那契数列（Fibonacci)12/11/2022）数据结构是递归的链表就是一种递归数据结构。

datalinkfirst是一个单链表first……是一个单链表

指向的也是一个单链表

^^1/6/202362）数据结构是递归的链表就是一种递归数据结构。^^12/数据结构是递归的，则写算法采用递归方法是最方便的。例1.查找非空单链表的最后一个结点并打印其数据域。template<classtype>voidfind(listnode<type>*f){if(flink==null)cout<<fdata<<endL;elsefind(flink);}例2.查找非空单链表中值为x的结点，并输出之。template<classtype>voidprint(listnode<type>*f){if(f!=null)if(fdata==x)cout<<fdata<<endL;elseprint(flink);}

1/6/20237数据结构是递归的，则写算法采用递归方法是最方便的。例1.查找3）问题的解法是递归的（Hanoi塔）

ABC从A柱移到C柱：每次移一片盘，而且不允许大盘在小盘上。分析：1.先将n-1个盘由AB(递归）2.将一个盘由AC3.将n-1个盘由BC(递归）n1/6/202383）问题的解法是递归的（Hanoi塔）n12/11/#include<iostream.h>#include“strclass.h”//字符串类的原型文件VoidHanoi(intn,stringA,stringB,stringC){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);//递归调用}}1/6/20239#include<iostream.h>12/11/2022.迷宫问题一个小型迷宫问题。

457

326

11/6/2023102.迷宫问题一个小型迷宫问题。12/11/2022103.递归过程的实现以上两个例子以及迷宫问题可以看到1)递归程序十分短,十分简练,但读起来不容易.2)有很多工作由编译程序做了,编译程序要开辟:参数栈,局部变量栈,返回地址栈函数名,引用参数,数值参数

1/6/2023113.递归过程的实现12/11/2022115.4利用栈实现的迷宫问题的非递归解法数据结构:1.迷宫用二维数组表示maze[m][p],但在迷宫外面加一个圈,为墙壁.Maze[m+2][p+2]即行数:0~m+1;列数:0~p+1111111001001maze[i][j]=0表示该位置是通路110101maze[i][j]=1………………墙壁101011入口:maze[1][1]110111出口:maze[m][p]1011001111111/6/2023125.4利用栈实现的迷宫问题的非递归解法12/11/20222.从[i][j]位置,前进的方向有8个,可测探。[i-1][j-1][i-1][j][i-1][j+1][i][j-1][i][j][i][j+1][i+1][j-1][i+1][j][i+1][j+1]8个方向用枚举类型来表示:enumdirections{N,NE,E,SE,S,SW,W,NW}3.向8个方向移动,其坐标位置要变化,具体实现放其偏移量,即:1/6/20231312/11/202213Offsetmove[8]structoffsets{inta,b;};例如,若当前位置为[i][j],向西南SW方向移动,则下一相邻位置[g][h]为:g=i+move[SW].a;h=j+move[SW].b这里要指出的是,用枚举类型中的数组作为下标变量,这是一个技巧.实际上枚举类型在机内实现为整型数ab……..move1/6/202314Offsetmove[8]例如,若当前位置为[i][j],4.为了防止重走老路,另外又建立了一个标志矩阵mark[m+2][p+2],初始化时都为0,一旦走到迷宫的某个位置[i][j],则得mark[i][j]置为1.表示下次这个位置不能再走了。mark与maze矩阵大小一一对应.5.设立一个栈,存储在试探过程中所走过的路径,一旦要回溯,则从栈中取得刚才走过位置的坐标和前进方向.栈中需保存一个三元组xydirstructitems坐标方向{intx,y,dir;}1/6/2023154.为了防止重走老路,另外又建立了一个标志矩阵mark[m6.具体实现算法1.mark[1][1]=1;//[1][1]是入口2.stack<items>st(m*p);//开辟工作栈,大小为m*p3.itemstmp;//设一工作结构变量tmp.x=1;tmp.y=1;tmp.dir=E;st.push(tmp);4.while(!st.IsEmpty()){1）tmp=st.pop();2)inti=tmp.x;intj=tmp.y;intd=tmp.dir1/6/2023166.具体实现算法12/11/2022163)while(d<8){i)intg=i+move[d].a;inth=j+move[d].b;ii)if(g==m&&h==p)//判别是否出口{输出i,j,m,p;return;}iii)if(!maze[g][h]&&mark[g][h]){a.mark[g][h]=1;//表示向东走过该坐标b.将(i,j,d+1进栈)如果向东走下去,到某一步走不通,则有可能回退到i,j,则要换一个方向,即d+1(SE)东南c.从新的坐标点i=g,j=h,d=N开始一个个方向试探}elsed++;//遇到墙或该坐标已走过,则换一个方向试.}}1/6/2023173)while(d<8)12/11/202215.广义表(GeneralList)

1)广义表的概念(LS)*定义:n(n>=0)个表元素a0,a1,a2,……an-1组成的有限序列。记作:LS=(a0,a1,a2,……an-1)

其中每个表元素ai可以是原子,也可以是子表。原子:某种类型的对象,在结构上不可分。(用小写字母表示)子表:有结构的。(用大写字母表示)*广义表的长度:表中元素的个数1/6/2023185.广义表(GeneralList)12/11/202*广义表的表头(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)递归的表1/6/202319*广义表的表头(head)、表尾(tail)12/11

2)广义表的性质有序性有长度,有深度可递归,如上面例6可共享,如E中B为E,D所共享各种广义表都可用一种示意图来表示,用表示表元素,表示原子A62B‘a’53‘x’C1/6/2023202)广义表的性质A62B‘a’53‘x’C12/11/DBCA62‘a’53‘x’EBDCA62‘a’53‘x’F41/6/202321DBCA62‘a’53‘x’EBDCA62‘a’53‘x’F3)广义表的操作例子: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)//返回由elem指向的广义表节点的类型push(list,x)//将值为x的节点加入到广义表list的最前端addon(list,x)//建立以x为头,list为尾的新表setinfo(elem,x)//将表元素elem的值修改为xsethead(list,x)//将list的头元素重置为x1/6/2023223)广义表的操作12/11/202222

4)广义表的存储结构用数组存储显然不合适,因数组元素不同构用拉链,但各元素类型不一致;用不等长节点不好.用等长节点来表示,每个表节点用三个域组成.标志域值域尾指针utypevaluetlink1/6/20232312/11/202223

utype=0:广义表专用的表头结点1:整型原子结点2:字符型原子结点3:子表节点值域随着不同类型的节点,存放不同的内容,并用不同的名字来表示,实际上value部分可变的,用union实现.utype=0,ref:存放引用计数utype=1,intgrinfo:存放整数值utype=2,charinfo:存放字符型数据utype=3,hlink:指向子表表头的指针1/6/202324utype=0:广义表专用的表头结点12/1

tlink:当utype=0,tlink指向该表(表可以是子表)第一个元素的结点当utype!=0,tlink指向该值域同一层的下一个表结点例子:L=(3,(),(‘b’,‘c’),(((‘d’))))

utypereftlinkL0L13333^0^02b2c^

03^03^02‘d’^

1/6/202325tlink:当utype=0,tlink指向该广义表的类声明:#defineHEAD0#defineINTGR1#defineCH2#defineLIST31/6/202326广义表的类声明:12/11/202226classGenList;classGenListNode{friendclassGenList;private:intutype;//=1/2/3,表示HEAD/INTGR/CH/LSTGenListNode*tlink;union{//联合intref;intintgrinfo;charcharinfo;GenListNode*hlinkl}value;1/6/202327classGenList;12/11/202227Public:GenListNode&Info(GenListNode*elem);intnodetype(GenListNode*elem){returnelem-->utype;}voidsetInfo(GenListNode*elem,GenListNode&x);}广义表的类声明中:成员数据:first它指向广义表的表头结点成员函数:私有--copy，depth,equal,remove公有--Head,tail,First,Next,push,Addon等等

1/6/202328Public:12/11/2022285）广义表部分成员函数的实现算法广义表结点类的存取成员函数GenListNode&GenListNode::info(GenListNode*elem){//返回表元素elem的值GenListNode*pitem=newGenListNode;pitem-->utype=elem-->utype;pitem-->value=elem-->value;return*pitem;}广义表的一些成员函数

广义表类的构造函数

first01NULL1/6/2023295）广义表部分成员函数的实现算法first01NGenList::GenList(){GenListNode*first=newGenListNode;first-->utype=0;first-->value.ref=1;first-->tlink=NULL;}

Head()---返回广义表的第一个元素值,若为空表,则为非法操作.GenListNode&GenList::Head(){if(first-->tlink==NULL){cout<<“Illegalheadoperation.”<<endl;exit(1);}else{GenListNode*temp=newGenListNode;temp-->utype=first-->tlink-->utype;temp-->value=first-->tlink-->value;return*temp;}}1/6/202330GenList::GenList()12/11/20

取广义表的表尾---tail()(若是空表,则是非法操作)GenListGenList::Tail(){if(first-->tlink==NULL){cout<<“Illegaltailoperation.”<<endl;exit(1);}else{GenList*temp=newGenList;temp-->first-->tlink=first-->tlink-->tlink;return*temp;}}

1/6/202331取广义表的表尾---tail()(若是空表,则构造一个以x为第一个元素,list为尾的新表----AddonGenList&GenList::Addon(GenList&list,GenListNode&x){GenList*newList=newGenList;newList-->first=copy(list.first);x-->tlink=newList-->first-->tlink;newList-->first-->tlink=x;return*newlist;}重新定义广义表的尾----setTailvoidGenList::setTail(GenList&list){GenListNode*temp;1/6/202332构造一个以x为第一个元素,list为尾的新表----Addotemp=first-->tlink-->tlink;first-->tlink-->tlink=list.first-->tlink;deletelist.first;freelist(temp);}1/6/202333temp=first-->tlink-->tlin6)广义表的递归算法递归算法:*递归函数的外部调用-----公有函数界面*递归函数的内部调用-----私有函数真正实现部分求广义表的深度广义表的深度为广义表中最大括号的重数广义表LS==(a0,a1,a2,……an-1),其中ai(0<=i<=n-1)或者是原子或者是子表.0当LS为原子时递归结束条件Depth(LS)=1当LS为空表时1+max{depth(a0),depth(a1),………depth(an-1)}1/6/2023346)广义表的递归算法12/11/202234intGenList::depth()//公共函数{returndepth(first);}intGenList::depth(GenListNode*ls)//私有函数{if(ls-->tlink==NULL)return1;GenListNode*temp=ls-->tlink;intm=0;while(temp!=NULL){if(temp-->utype==LST){intn=depth(temp-->hlink);if(m<n)m=n;}temp=temp-->tlink;}returnm+1;}1/6/202335intGenList::depth()//公共函数

判断两个广义表相等否相等的条件:具有相同的结构对应的数据元素具有相等的值if(两个广义表都为空表)return相等elseif(都为原子^值相等)递归比较同一层的后面的表元素elsereturn不相等1/6/20233612/11/202236

intoperator==(constGenList&l,constGenList&m){returnequal(l.first,m.first);}intequal(GenListNode*s,GenListNode*t){intx;if(s-->tlink==NULL&&t-->tlink==NULL)return1;if((s-->tlink!=NULL&&t-->tlink!=NULL&&s-->tlink-->utype==t-->tlink-->utype){if(s-->tlink-->utype==INTGR)if(s-->tlink-->grinfo==t-->tlink-->grinfo)x=1;elsex=0;elseif(s-->tlink-->utype==CH)if(s-->tlink-->value.charinfo==t-->tlink-->value.charinfo)x=1;elsex=0;elsex=equal(s-->tlink-->value.hlink,t-->tlink-->value.hlink);if(x)returnequal(s-->tlink,t-->tlink);}return0;}1/6/202337intoperator==(constGenList

广义表的复制算法分别复制表头,表尾,然后合成前提是广义表不可以是共享表或递归表1/6/202338

voidGenList::copy(constGenList&l){first=copy(l.first);}GenListNode*GenList::copy(GenListNode*ls){GenListNode*q=NULL;if(ls!=NULL){q=newGenListNode;q-->utype=ls-->utype;Switch(ls-->utype){caseHEAD:q-->value.ref=ls-->value.ref;break;//表头结点caseINTGR:q-->grinfo=ls-->grinfo;break;caseCH:q-->value.charinfo=ls-->value.charinfo;break;caseLST:q-->value.hlink=copy(ls-->value.hlink);break;}q-->tlink=copy(ls-->tlink);}returnq;}

1/6/202339voidGenList::copy(constGenL

广义表的析构函数---------~GenList()GenList::~GenList(){remove(first);}voidGenList::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;//回收顶层节点到可利用空间表中}}1/6/202340广义表的析构函数---------~GenList(1/6/20234112/11/202241习题、考研题：1.5-12.5-53.5-64.5-75.2003四.26.2004四.17.递归算法1）求广义表的深度2）判别原子a是否属于广义表L=(b,(c,a),……)假设广义表用单链表方式存放。每个结点三个域：1/6/202342习题、考研题：12/11/202242

当tag=0时，data域为原子本身（假设为整型）tag=1时，hlink域指向子表的第一个元素ClassGenlistClassGenListNode;{friendclassGenList;private:inttag;GenListNode*tlink;Union{intdata;GenListNode*hlink;}value;public:…..}tagtlinkhlink/data1/6/202343

intmember(GenListNode*L;inta){intcheck=0;GenListNode*ptr=L;while((ptr!=NULL)&&(!check)){if(ptr->tag==1){check=member(ptr->value.hlink,a)if(check==0)ptr=ptr->tlink;}elseif(ptr->value.data==a)check=1;elseptr=ptr->tlink;}returncheck;}1/6/202344intmember(GenListNode*L;

第5章递归1.递归的概念1)定义是递归的

2)数据结构是递归的

3）问题的解法是递归的2.迷宫问题

3.递归过程的实现4.利用栈实现的迷宫问题的非递归解法5.广义表(GeneralList)1)广义表的概念(LS)2)广义表的性质3)广义表的操作4)广义表的存储结构5）广义表部分成员函数的实现算法6)广义表的递归算法求广义表的深度、判断两个广义表相等否、广义表的复制算法1/6/202345第5章递归12/1第5章递归1.递归的概念n!=1n=0n*(n-1)!n>0若一个对象部分地包含它自己或用它自己给自己定义，则称这个对象是递归的。若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。*测试终结递归的条件递归出口*n问题化为n-1问题（或着大问题化为小问题）1/6/202346第5章递归1.递归的概念n!=1n=0

三种常用到递归的方法

定义是递归的。数据结构是递归的。问题的解法是递归的。1)定义是递归的例1：如上面求n！的定义就是递归的。longfactorial(longn){if(n==0)return1;//递归终结条件elsereturnn*factorial(n-1);//n问题化为n-1问题}1/6/202347

三种常用到递归的方法

定义是递归的。12/11/下面看一下求factorial（3）F(3)f(2)f(1)f(0)

n=3n=2n=1n=06n*f(2)n*f(1)n*f(0)3*22*11*1n=3n=2n=11/6/202348下面看一下求factorial（3）F(3)例2斐波那契数列（Fibonacci)

0，1，1，2，3，5，8，……以fn表示数列中第n个数，fn的递归定义：n当n=0，1时Fib(n)=Fib(n-1)+Fib(n-2)当n>1时longFib(longn){if(n<=1)returnn;elsereturnFib(n-1)+Fib(n-2);}1/6/202349例2斐波那契数列（Fibonacci)12/11/2022）数据结构是递归的链表就是一种递归数据结构。

datalinkfirst是一个单链表first……是一个单链表

指向的也是一个单链表

^^1/6/2023502）数据结构是递归的链表就是一种递归数据结构。^^12/数据结构是递归的，则写算法采用递归方法是最方便的。例1.查找非空单链表的最后一个结点并打印其数据域。template<classtype>voidfind(listnode<type>*f){if(flink==null)cout<<fdata<<endL;elsefind(flink);}例2.查找非空单链表中值为x的结点，并输出之。template<classtype>voidprint(listnode<type>*f){if(f!=null)if(fdata==x)cout<<fdata<<endL;elseprint(flink);}

1/6/202351数据结构是递归的，则写算法采用递归方法是最方便的。例1.查找3）问题的解法是递归的（Hanoi塔）

ABC从A柱移到C柱：每次移一片盘，而且不允许大盘在小盘上。分析：1.先将n-1个盘由AB(递归）2.将一个盘由AC3.将n-1个盘由BC(递归）n1/6/2023523）问题的解法是递归的（Hanoi塔）n12/11/#include<iostream.h>#include“strclass.h”//字符串类的原型文件VoidHanoi(intn,stringA,stringB,stringC){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);//递归调用}}1/6/202353#include<iostream.h>12/11/2022.迷宫问题一个小型迷宫问题。

457

326

11/6/2023542.迷宫问题一个小型迷宫问题。12/11/2022103.递归过程的实现以上两个例子以及迷宫问题可以看到1)递归程序十分短,十分简练,但读起来不容易.2)有很多工作由编译程序做了,编译程序要开辟:参数栈,局部变量栈,返回地址栈函数名,引用参数,数值参数

1/6/2023553.递归过程的实现12/11/2022115.4利用栈实现的迷宫问题的非递归解法数据结构:1.迷宫用二维数组表示maze[m][p],但在迷宫外面加一个圈,为墙壁.Maze[m+2][p+2]即行数:0~m+1;列数:0~p+1111111001001maze[i][j]=0表示该位置是通路110101maze[i][j]=1………………墙壁101011入口:maze[1][1]110111出口:maze[m][p]1011001111111/6/2023565.4利用栈实现的迷宫问题的非递归解法12/11/20222.从[i][j]位置,前进的方向有8个,可测探。[i-1][j-1][i-1][j][i-1][j+1][i][j-1][i][j][i][j+1][i+1][j-1][i+1][j][i+1][j+1]8个方向用枚举类型来表示:enumdirections{N,NE,E,SE,S,SW,W,NW}3.向8个方向移动,其坐标位置要变化,具体实现放其偏移量,即:1/6/20235712/11/202213Offsetmove[8]structoffsets{inta,b;};例如,若当前位置为[i][j],向西南SW方向移动,则下一相邻位置[g][h]为:g=i+move[SW].a;h=j+move[SW].b这里要指出的是,用枚举类型中的数组作为下标变量,这是一个技巧.实际上枚举类型在机内实现为整型数ab……..move1/6/202358Offsetmove[8]例如,若当前位置为[i][j],4.为了防止重走老路,另外又建立了一个标志矩阵mark[m+2][p+2],初始化时都为0,一旦走到迷宫的某个位置[i][j],则得mark[i][j]置为1.表示下次这个位置不能再走了。mark与maze矩阵大小一一对应.5.设立一个栈,存储在试探过程中所走过的路径,一旦要回溯,则从栈中取得刚才走过位置的坐标和前进方向.栈中需保存一个三元组xydirstructitems坐标方向{intx,y,dir;}1/6/2023594.为了防止重走老路,另外又建立了一个标志矩阵mark[m6.具体实现算法1.mark[1][1]=1;//[1][1]是入口2.stack<items>st(m*p);//开辟工作栈,大小为m*p3.itemstmp;//设一工作结构变量tmp.x=1;tmp.y=1;tmp.dir=E;st.push(tmp);4.while(!st.IsEmpty()){1）tmp=st.pop();2)inti=tmp.x;intj=tmp.y;intd=tmp.dir1/6/2023606.具体实现算法12/11/2022163)while(d<8){i)intg=i+move[d].a;inth=j+move[d].b;ii)if(g==m&&h==p)//判别是否出口{输出i,j,m,p;return;}iii)if(!maze[g][h]&&mark[g][h]){a.mark[g][h]=1;//表示向东走过该坐标b.将(i,j,d+1进栈)如果向东走下去,到某一步走不通,则有可能回退到i,j,则要换一个方向,即d+1(SE)东南c.从新的坐标点i=g,j=h,d=N开始一个个方向试探}elsed++;//遇到墙或该坐标已走过,则换一个方向试.}}1/6/2023613)while(d<8)12/11/202215.广义表(GeneralList)

1)广义表的概念(LS)*定义:n(n>=0)个表元素a0,a1,a2,……an-1组成的有限序列。记作:LS=(a0,a1,a2,……an-1)

其中每个表元素ai可以是原子,也可以是子表。原子:某种类型的对象,在结构上不可分。(用小写字母表示)子表:有结构的。(用大写字母表示)*广义表的长度:表中元素的个数1/6/2023625.广义表(GeneralList)12/11/202*广义表的表头(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)递归的表1/6/202363*广义表的表头(head)、表尾(tail)12/11

2)广义表的性质有序性有长度,有深度可递归,如上面例6可共享,如E中B为E,D所共享各种广义表都可用一种示意图来表示,用表示表元素,表示原子A62B‘a’53‘x’C1/6/2023642)广义表的性质A62B‘a’53‘x’C12/11/DBCA62‘a’53‘x’EBDCA62‘a’53‘x’F41/6/202365DBCA62‘a’53‘x’EBDCA62‘a’53‘x’F3)广义表的操作例子: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)//返回由elem指向的广义表节点的类型push(list,x)//将值为x的节点加入到广义表list的最前端addon(list,x)//建立以x为头,list为尾的新表setinfo(elem,x)//将表元素elem的值修改为xsethead(list,x)//将list的头元素重置为x1/6/2023663)广义表的操作12/11/202222

4)广义表的存储结构用数组存储显然不合适,因数组元素不同构用拉链,但各元素类型不一致;用不等长节点不好.用等长节点来表示,每个表节点用三个域组成.标志域值域尾指针utypevaluetlink1/6/20236712/11/202223

utype=0:广义表专用的表头结点1:整型原子结点2:字符型原子结点3:子表节点值域随着不同类型的节点,存放不同的内容,并用不同的名字来表示,实际上value部分可变的,用union实现.utype=0,ref:存放引用计数utype=1,intgrinfo:存放整数值utype=2,charinfo:存放字符型数据utype=3,hlink:指向子表表头的指针1/6/202368utype=0:广义表专用的表头结点12/1

tlink:当utype=0,tlink指向该表(表可以是子表)第一个元素的结点当utype!=0,tlink指向该值域同一层的下一个表结点例子:L=(3,(),(‘b’,‘c’),(((‘d’))))

utypereftlinkL0L13333^0^02b2c^

03^03^02‘d’^

1/6/202369tlink:当utype=0,tlink指向该广义表的类声明:#defineHEAD0#defineINTGR1#defineCH2#defineLIST31/6/202370广义表的类声明:12/11/202226classGenList;classGenListNode{friendclassGenList;private:intutype;//=1/2/3,表示HEAD/INTGR/CH/LSTGenListNode*tlink;union{//联合intref;intintgrinfo;charcharinfo;GenListNode*hlinkl}value;1/6/202371classGenList;12/11/202227Public:GenListNode&Info(GenListNode*elem);intnodetype(GenListNode*elem){returnelem-->utype;}voidsetInfo(GenListNode*elem,GenListNode&x);}广义表的类声明中:成员数据:first它指向广义表的表头结点成员函数:私有--copy，depth,equal,remove公有--Head,tail,First,Next,push,Addon等等

1/6/202372Public:12/11/2022285）广义表部分成员函数的实现算法广义表结点类的存取成员函数GenListNode&GenListNode::info(GenListNode*elem){//返回表元素elem的值GenListNode*pitem=newGenListNode;pitem-->utype=elem-->utype;pitem-->value=elem-->value;return*pitem;}广义表的一些成员函数

广义表类的构造函数

first01NULL1/6/2023735）广义表部分成员函数的实现算法first01NGenList::GenList(){GenListNode*first=newGenListNode;first-->utype=0;first-->value.ref=1;first-->tlink=NULL;}

Head()---返回广义表的第一个元素值,若为空表,则为非法操作.GenListNode&GenList::Head(){if(first-->tlink==NULL){cout<<“Illegalheadoperation.”<<endl;exit(1);}else{GenListNode*temp=newGenListNode;temp-->utype=first-->tlink-->utype;temp-->value=first-->tlink-->value;return*temp;}}1/6/202374GenList::GenList()12/11/20

取广义表的表尾---tail()(若是空表,则是非法操作)GenListGenList::Tail(){if(first-->tlink==NULL){cout<<“Illegaltailoperation.”<<endl;exit(1);}else{GenList*temp=newGenList;temp-->first-->tlink=first-->tlink-->tlink;return*temp;}}

1/6/202375取广义表的表尾---tail()(若是空表,则构造一个以x为第一个元素,list为尾的新表----AddonGenList&GenList::Addon(GenList&list,GenListNode&x){GenList*newList=newGenList;newList-->first=copy(list.first);x-->tlink=newList-->first-->tlink;newList-->f