数据结构广义表课件.ppt

1 广义表的定义,一、广义表定义 广义表可定义为：数据元素可以是表的线性表。记为：LS(d1,d2,dn)LS为表名，di(i1,2,n)，可以是单元素(称为原子，用小写字母表示)，也可以是广义表(称为子表，用大写字母表示)；若广义表LS非空，则必有n大于0（即 n 0）n为表的长度，当长度为0时称为空表；称非空表的第一个元素d1为表头，其余元素组成的表(d2,dn)称为表尾。,注意：表尾可以可以是空表，而表头可以是原子，也可以是一个表。广义表的抽象类型定义采用递归定义如教材P.107。,二、广义表的表达方式及例子1A=()A是一个空表，其长度为0。2B=(e)列表B只有一个原子e，其长度为1。3C=(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可表示为：,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 ElemTagtypedef 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),(b,c,d),(b,c,d),(c,d),(d),3 广义表的存储结构,2.同层结点链存储结构 有两类结点：表结点和单元素结点。tag=1 hp tp 表结点 tag=0 data tp 单元素结点 结点结构是无论什么结点都有三个域：第一个域是结点类型标志tag；第二个域是指向一个列表的指针（当tag=1时）或一个原子（当tag=0时）；第三个域是指向下一个结点的指针tp。,3 广义表的存储结构,形式描述为：typedef enum ATOM,LIST ElemTagtypedef struct GLNode/定义广义表结点ElemTage tag;/公共部分，用以区分 原子结点和表结点Unin/原子结点和表结点的联合部分 AtomType atom;/原子类型结点域，/AtomType由用户定义 struct GLNode*hp,;/表结点的表头指针域;struct GLNode*tp;/指向下一个结点的指针*Glist;/广义表类型,3 广义表的存储结构,同层结点链结构的特点是：表结点的数目与广义表的括号对数目一致；写递归算法不方便。,例:C=(a,(b,c,d),(b,c,d),应用：M元多项式的表示,对任何一个M元多项式P，先确定一个主变元，于是它可看成主变元的一元多项式，但它的系数可能是一个多项式，也可能是一个常数。于是P可表为一个线性表 P=(1,expn1),(2,expn2),(n,expnn)其中每个i可能是一个常数，也可能又是一个多项式；对于每一个多项式j,又可以确定一个主变元（可称为原多项式的第二变元），从而，可表为下一级的一元多项式，其系数又可能性是常数，也可能是多项式；直到最后纯粹的一元多项式。所以M元多项式，最好用广义表来表示。其元素结点如下图：,表结点（多项式结点）原子结点（常系数结点）,其形式定义如下：typedef struct MPNodeElemTag tag;/区分原子结点和表结点int expn;/指数域union/原子结点和表结点共享一个域 float coef;/系数域struct MPNode*hp;/表结点的表头指针 struct MPNode*tp;/指向下一个元素结点*MPList;/M元多项广义表类型,M元多项式的表示,例:P(x,y,z)=x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15=(x10y3+2x6y3+3x5y2)z2+(x4y4+6x3y4+2y)z+15=(x10+2x6)y3+3x5y2)z2+(x4+6x3)y4+2y)z+15=Az2+Bz+15z0其中:A=Cy3+Dy2 C=x10+2x6 D=3x5可用广义表表示为: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域填上变元个数,前例:P(x,y,z)=z(A,2),(B,1),(15,0)A=y(c,3),(D,2)C=x(1,10),(2,6),P,D,B,A,C,三类表结点(tag=1):整个表的头结点一个,exp域为变元数，层头结点(每层一个),exp域为相应变元在数组中的下标，一般表结点,exp域为指数。,