数据结构广义表.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,广义表,1广义表的定义,2广义表的基本运算,3广义表的存储结构,1,广义表,的定义,一、广义表定义,广义表可定义为：数据元素可以是表的线性表记为：,LS(d,1,d,2,d,n,),LS,为表名，,d,i,(i1,2,n)，,可以是,单元素,(称为,原子,，用小写字母表示)，也可以是,广义表,(称为,子表,，用大写字母表示)；,若广义表,LS,非空，则必有,n,大于0（即,n 0,）,n,为表的长度，当长度为0时称为,空表,；,称非空表的第一个元素,d,1,为,表头,，,其余元素组成的,表,(,d,2,d,n,),称为,表尾,注意：,表尾可以可以是空表，而表头可以是原子，也可以是一个表,广义表的抽象类型定义采用递归定义如教材,P.107二、广义表的表达方式及例子,1,A=()A,是一个空表，其长度为02,B=(e),列表,B,只有一个原子,e，,其长度为13,C=(a,(b,c,d),列表,C,的长度为2，表头为原子，,第二个元素是一个列表(,b,c,d)4.D=(A,B,C),列表,D,的长度为3，,表头也是一个列表,A，,表尾是列表（,A,B）,注意：,这里引用了已有的列表,A、B、C,作为该广义表,D,的元素。

5,E=(a,E),这是一个递归列表，其元素中有自己广义表也可以用图形表示，例如前述的广义表,D,和,E,可表示为：,b,e,a,c,d,a,D,A,B,C,广义表,D,E,广义表,E,2,广义表,的,基本运算,广义表的基本运算,取表头,HEAD(LS)；,取表尾,TAIL(LS)3 广义表的,存储结构,广义表中的数据元素可以是单元素，或是广义表，很难用顺序存储结构表示，常采用链式存储结构1.,表头表尾链,存储结构,有两类结点：表结点和单元素结点tag=1 hp tp ,表结点,tag=0 data ,单元素结点,tag,标志域，0表示结点为单元素结点，1表示为表结点；,hp：,表头指针域；,tp：,表尾指针域；,data：,值域3 广义表的,存储结构,形式描述为：,typedef enum ATOM,LIST ElemTag,typedef struct GLNode,/,定义广义表结点,ElemTage tag;,/,公共部分，用以区分,原子结点和表结点,Union,/,原子结点和表结点的联合部分,AtomType atom;,/,原子类型结点域，,/,AtomType,由用户定义,Struct struct GLNode *hp,*tp;ptr;,/,表结点的指针域，,/,ptr.hp,与,ptr.tp,分别指向广义表的表头和表尾。

Glist;,/,广义表类型,3 广义表的,存储结构,这种存储结构的特点是：,最上层的表结点数即为广义表的长度；,层次清楚；,表结点数目多，与广义表中括号对的数目不匹配例:,C=(a,(b,c,d),1,1,1,1,1,0,a,0,b,0,c,0,d,(,b,c,d,),(,b,c,d,),(,c,d,),(,d,),C,3 广义表的,存储结构,2.同层结点链存储结构,有两类结点：表结点和单元素结点tag=1 hp tp ,表结点,tag=0 data tp ,单元素结点,结点结构,是无论什么结点都有三个域：,第一个域是结点类型标志,tag,；,第二个域是指向一个列表的指针（当,tag=1,时）,或一个原子（当,tag=0,时）；,第三个域是指向下一个结点的指针,tp3 广义表的,存储结构,形式描述为：,typedef enum ATOM,LIST ElemTag,typedef struct GLNode,/,定义广义表结点,ElemTage tag;,/,公共部分，用以区分,原子结点和表结点,Unin,/,原子结点和表结点的联合部分,AtomType atom;,/,原子类型结点域，,/,AtomType,由用户定义,struct GLNode *hp,;,/,表结点的表头指针域,;,struct GLNode *tp;,/,指向下一个结点的指针,*,Glist;,/,广义表类型,3 广义表的,存储结构,同层结点链结构的特点是：,表结点的数目与广义表的括号对数目一致；,写递归算法不方便。

例:,C=(a,(b,c,d),1,C,0,a,1,0,b,0,c,0,d,(,b,c,d),应用：,M,元多项式的表示,对任何一个,M,元多项式,P，,先确定一个主变元，于是它可看成主变元的一元多项式，但它的系数可能是一个多项式，也可能是一个常数于是,P,可表为一个线性表,P=(,1,expn,1,),(,2,expn,2,),(,n,expn,n,),其中每个,i,可能是一个常数，也可能又是一个多项式；对于每一个多项式,j,又可以确定一个主变元（可称为原多项式的第二变元），从而，可表为下一级的一元多项式，其系数又可能性是常数，也可能是多项式；直到最后纯粹的一元多项式所以,M,元多项式，最好用广义表来表示其元素结点如下图：,表结点（多项式结点）,原子结点（常系数结点）,tag=1 exp hp tp,tag=0 exp coef tp,其形式定义如下：,typedef struct MPNode,ElemTag tag;/,区分原子结点和表结点,int expn;/,指数域,union /,原子结点和表结点共享一个域,float coef;/,系数域,struct MPNode *hp;/,表结点的表头指针,struct MPNode *tp;/,指向下一个元素结点,*,MPList;/M,元多项广义表类型,M,元多项式的表示,例:,P(x,y,z)=,x,10,y,3,z,2,+2,x,6,y,3,z,2,+3,x,5,y,2,z,2,+,x,4,y,4,z,+6,x,3,y,4,z,+2,yz,+15,=(,x,10,y,3,+2,x,6,y,3,+3,x,5,y,2,)z,2,+(x,4,y,4,+6,x,3,y,4,+2,y)z+15,=(x,10,+2,x,6,)y,3,+3,x,5,y,2,)z,2,+(x,4,+6,x,3,)y,4,+2,y)z+15,=Az,2,+Bz+15z,0,其中:,A=Cy,3,+D,y,2,C=x,10,+2,x,6,D=3x,5,可用广义表表示为:,P(x,y,z)=z(A,2),(B,1),(15,0),A=y(C,3),(D,2)B=y(E,4),(2,1),C=x(1,10),(2,6)E=x(1,4),(6,3),D=x(3,5),M,元多项式的表示,存储表示,(1)结点结构 表结点,单元素结点,(2)用一维数组存储多项式的所有变元,(3)每一层增设一个表头结点,并用,exp,域表明变元在数组中的下标,(4)增设一个表头结点,表示整个表,用头指针,p,指示,并在,exp,域填上变元个数,tag=1 exp hp tp,tag=0 exp coef tp,前例:,P(x,y,z)=z(A,2),(B,1),(15,0),A=y(c,3),(D,2)C=x(1,10),(2,6),P,1 1,1 3,1 2,1 1,0 0 15,1 2,1 3,1 2,0 10 1,0 6 2,1 3,D,z y x,B,A,C,三类表结点(,tag=1,):,整个表的头结点一个,exp,域为变元数，,层头结点(每层一个),exp,域为相应变元在数组中的下标，,一般表结点,exp,域为指数。