数据结构广义表

数据结构广义表第1页，共16页，2023年，2月20日，星期六1广义表的定义一、广义表定义

广义表可定义为：数据元素可以是表的线性表。记为：LS＝(d1,d2,…,dn)

LS为表名，di(i＝1,2,…,n)，可以是单元素(称为原子，用小写字母表示)，也可以是广义表(称为子表，用大写字母表示)；若广义表LS非空，则必有n大于0（即n>0）

n为表的长度，当长度为0时称为空表；称非空表的第一个元素d1为表头，其余元素组成的表(d2,…,dn)称为表尾。第2页，共16页，2023年，2月20日，星期六注意：表尾可以可以是空表，而表头可以是原子，也可以是一个表。广义表的抽象类型定义采用递归定义如教材P.107。

二、广义表的表达方式及例子1．A=()A是一个空表，其长度为0。2．B=(e)列表B只有一个原子e，其长度为1。3．C=(a,(b,c,d))列表C的长度为2，表头为原子，第二个元素是一个列表(b,c,d)。4.D=(A,B,C)列表D的长度为3，表头也是一个列表A，表尾是列表（A,B）,注意：这里引用了已有的列表A、B、C作为该广义表D的元素。第3页，共16页，2023年，2月20日，星期六5．

E=(a,E)这是一个递归列表，其元素中有自己。广义表也可以用图形表示，例如前述的广义表D和E可表示为：

beacdaDABC广义表DE广义表E第4页，共16页，2023年，2月20日，星期六2广义表的基本运算广义表的基本运算 ⑴取表头HEAD(LS)； ⑵取表尾TAIL(LS)。第5页，共16页，2023年，2月20日，星期六3广义表的存储结构

广义表中的数据元素可以是单元素，或是广义表，很难用顺序存储结构表示，常采用链式存储结构。

1.表头表尾链存储结构有两类结点：表结点和单元素结点。

┌───┬────┬───┐│tag=1│hp│tp│表结点

└───┴────┴───┘┌───┬────────┐│tag=0│data│单元素结点

└───┴────────┘tag标志域，0表示结点为单元素结点，1表示为表结点；hp：表头指针域；tp：表尾指针域；data：值域。第6页，共16页，2023年，2月20日，星期六3广义表的存储结构形式描述为：

typedefenum{ATOM,LIST}ElemTagtypedefstructGLNode{//定义广义表结点ElemTagetag;//公共部分，用以区分原子结点和表结点Union{//原子结点和表结点的联合部分

AtomTypeatom;//原子类型结点域，//AtomType由用户定义

Struct{structGLNode*hp,*tp;}ptr;};//表结点的指针域，

//ptr.hp

与ptr.tp分别指向广义表的表头和表尾。}*Glist;//广义表类型

第7页，共16页，2023年，2月20日，星期六3广义表的存储结构这种存储结构的特点是：最上层的表结点数即为广义表的长度；层次清楚；表结点数目多，与广义表中括号对的数目不匹配。

例:C=(a,(b,c,d))111110a0b0c0d＾＾((b,c,d))(b,c,d)(c,d)(d)C第8页，共16页，2023年，2月20日，星期六3广义表的存储结构2.同层结点链存储结构有两类结点：表结点和单元素结点。

┌────┬───┬───┐ │tag=1│hp│tp│表结点└────┴───┴───┘ ┌────┬───┬───┐ │tag=0│data│tp│单元素结点└────┴───┴───┘

结点结构是无论什么结点都有三个域：第一个域是结点类型标志tag；第二个域是指向一个列表的指针（当tag=1时）或一个原子（当tag=0时）；第三个域是指向下一个结点的指针tp。

第9页，共16页，2023年，2月20日，星期六3广义表的存储结构形式描述为：

typedefenum{ATOM,LIST}ElemTagtypedefstructGLNode{//定义广义表结点ElemTagetag;//公共部分，用以区分原子结点和表结点Unin{//原子结点和表结点的联合部分

AtomTypeatom;//原子类型结点域，//AtomType由用户定义structGLNode*hp,;//表结点的表头指针域

};structGLNode*tp;

//指向下一个结点的指针}*Glist;//广义表类型

第10页，共16页，2023年，2月20日，星期六3广义表的存储结构同层结点链结构的特点是：表结点的数目与广义表的括号对数目一致；写递归算法不方便。例:C=(a,(b,c,d))1C＾0a1＾0b0c0d＾(b,c,d)第11页，共16页，2023年，2月20日，星期六

应用：M元多项式的表示

对任何一个M元多项式P，先确定一个主变元，于是它可看成主变元的一元多项式，但它的系数可能是一个多项式，也可能是一个常数。于是P可表为一个线性表

P=((α1,expn1),(α2,expn2),…,(αn,expnn))其中每个αi可能是一个常数，也可能又是一个多项式；对于每一个多项式αj,又可以确定一个主变元（可称为原多项式的第二变元），从而，可表为下一级的一元多项式，其系数又可能性是常数，也可能是多项式；…；直到最后纯粹的一元多项式。所以M元多项式，最好用广义表来表示。其元素结点如下图：

表结点（多项式结点）

原子结点（常系数结点）tag=1exphptptag=0expcoeftp第12页，共16页，2023年，2月20日，星期六其形式定义如下：typedefstructMPNode{ElemTagtag;//区分原子结点和表结点intexpn;//指数域union{//原子结点和表结点共享一个域

floatcoef;//系数域structMPNode*hp;//表结点的表头指针}structMPNode*tp;//指向下一个元素结点}*MPList;//M元多项广义表类型M元多项式的表示第13页，共16页，2023年，2月20日，星期六例: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+Dy2C=x10+2x6D=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元多项式的表示第14页，共16页，2023年，2月20日，星期六存储表示(1)结点结构表结点单元素结点(2)用一维数组存储多项式的所有变元(3)每一层增设一个表头结点,并用exp域表明变元在数组中的下标(4)增设一个表头结点,表示整个表,用头指针p指示,并在exp域填上变元个数tag=1exphptptag=0expcoeftp第15页，共16页，2023年，2月20日，星期六前例:P(x,y,z)=z((A,2),(B,1),(15,0))A=y((c,3),(D,2))C=x((1,10),(2,6))P111