1、1 1 广义表广义表的定义的定义 一、广义表定义一、广义表定义 广义表可定义为：数据元素可以是表的线性表。广义表可定义为：数据元素可以是表的线性表。 记为：记为：LSLS(d(d1 1,d,d2 2, ,d,dn n) ) LS LS为表名，为表名， d di i (i (i1,2,1,2,n),n)，可以是，可以是单元素单元素( (称为称为原子原子，用小写，用小写字母表示字母表示) )，也可以是，也可以是广义表广义表( (称为称为子表子表，用大写字母表，用大写字母表示示) )； 若广义表若广义表LSLS非空，则必有非空，则必有n大于大于0（即（即 n 0n 0） n n为表的长度，当长度为为
2、表的长度，当长度为0 0时称为时称为空表空表； 称非空表的第一个元素称非空表的第一个元素d d1 1为为表头表头， 其余元素组成的其余元素组成的表表(d(d2 2, ,d,dn n) )称为称为表尾表尾。注意：注意：表尾可以可以是空表，而表头可以是原子，也可以表尾可以可以是空表，而表头可以是原子，也可以是一个表是一个表。广义表的抽象类型定义采用递归定义如教材广义表的抽象类型定义采用递归定义如教材P.107P.107。 二、二、 广义表的表达方式及例子广义表的表达方式及例子1 1A=( ) AA=( ) A是一个空表，其长度为是一个空表，其长度为0 0。2 2B=(e) B=(e) 列表列表B
3、B只有一个原子只有一个原子e e，其长度为，其长度为1 1。3 3C=(a,(b,c,d) C=(a,(b,c,d) 列表列表C C的长度为的长度为2 2，表头为原子，表头为原子， 第二个元素是一个列表第二个元素是一个列表( (b,c,d)b,c,d)。4. D=(A,B,C) 4. D=(A,B,C) 列表列表D D的长度为的长度为3 3， 表头也是一个列表表头也是一个列表A A，表尾是列表（，表尾是列表（A, BA, B）, ,注意：注意：这里引用了已有的列表这里引用了已有的列表A A、B B、C C作为该广义表作为该广义表D D的的元素。元素。 5 E=(a,E) 这是一个递归列表，其元
4、素中有自己。这是一个递归列表，其元素中有自己。广义表也可以用图形表示，例如前述的广义表广义表也可以用图形表示，例如前述的广义表D和和E可表示为：可表示为： beacdaDABC广义表广义表DE广义表广义表E2 2 广义表广义表的的基本运算基本运算广义表的基本运算广义表的基本运算 取表头取表头 HEAD(LS)HEAD(LS)； 取表尾取表尾 TAIL(LS)TAIL(LS)。3 3 广义表的广义表的存储结构存储结构 广义表中的数据元素可以是单元素，或是广义表，广义表中的数据元素可以是单元素，或是广义表， 很难用顺序存储结构表示，常采用链式存储结构。很难用顺序存储结构表示，常采用链式存储结构。
5、1.1.表头表尾链表头表尾链存储结构存储结构 有两类结点：表结点和单元素结点。有两类结点：表结点和单元素结点。 tag=1 hp tp 表结点表结点 tag=0 data 单元素结点单元素结点 tagtag标志域，标志域，0 0表示结点为单元素结点，表示结点为单元素结点，1 1表示为表结点；表示为表结点；hphp：表头指针域；：表头指针域； tptp：表尾指针域；：表尾指针域； datadata： 值域。值域。3 3 广义表的广义表的存储结构存储结构形式描述为：形式描述为： typedef enum ATOM, LIST ElemTagtypedef enum ATOM, LIST ElemT
6、agtypedef struct GLNode typedef struct GLNode /定义广义表结点ElemTage tag;ElemTage tag; /公共部分，用以区分 原子结点和表结点UnionUnion /原子结点和表结点的联合部分 AtomType atom;AtomType atom;/原子类型结点域， / AtomTypeAtomType由用户定义 Struct struct GLNode Struct struct GLNode * *hp, hp, * *tp; ptr; ;tp; ptr; ; /表结点的指针域， /ptr.hpptr.hp 与ptr.tpptr.
7、tp分别指向广义表的表头和表尾。 * *Glist;Glist; /广义表类型 3 3 广义表的广义表的存储结构存储结构这种存储结构的特点是：这种存储结构的特点是： 最上层的表结点数即为广义表的长度；最上层的表结点数即为广义表的长度； 层次清楚；层次清楚； 表结点数目多，与广义表中括号对的数目不匹配。表结点数目多，与广义表中括号对的数目不匹配。 3 3 广义表的广义表的存储结构存储结构2. 2. 同层结点链存储结构同层结点链存储结构 有两类结点：表结点和单元素结点。有两类结点：表结点和单元素结点。 tag=1 hp tp 表结点表结点 tag=0 data tp 单元素结点单元素结点 结点结构
8、结点结构是无论什么结点都有三个域：是无论什么结点都有三个域： 第一个域是结点类型标志第一个域是结点类型标志tagtag； 第二个域是指向一个列表的指针（当第二个域是指向一个列表的指针（当tag=1tag=1时）时） 或一个原子（当或一个原子（当tag=0tag=0时）；时）； 第三个域是指向下一个结点的指针第三个域是指向下一个结点的指针tp。 3 3 广义表的广义表的存储结构存储结构形式描述为：形式描述为： typedef enum ATOM, LIST ElemTagtypedef enum ATOM, LIST ElemTagtypedef struct GLNode typedef st
9、ruct GLNode /定义广义表结点ElemTage tag;ElemTage tag; /公共部分，用以区分 原子结点和表结点UninUnin /原子结点和表结点的联合部分 AtomType atom;AtomType atom;/原子类型结点域， / AtomTypeAtomType由用户定义 struct GLNode struct GLNode * *hp,;hp,; /表结点的表头指针域 ; struct GLNode struct GLNode * *tp;tp; /指向下一个结点的指针 * *Glist;Glist; /广义表类型 3 3 广义表的广义表的存储结构存储结构同层
10、结点链结构的特点是：同层结点链结构的特点是： 表结点的数目与广义表的括号对数目一致；表结点的数目与广义表的括号对数目一致； 写递归算法不方便。写递归算法不方便。 应用：应用：M元多项式的表示元多项式的表示 对任何一个对任何一个M M元多项式元多项式P P，先确定一个主变元，于是它可看成，先确定一个主变元，于是它可看成主变元的一元多项式，但它的系数可能是一个多项式，也可能是主变元的一元多项式，但它的系数可能是一个多项式，也可能是一个常数。于是一个常数。于是P P可表为一个线性表可表为一个线性表 P=(P=(1 1 , expn, expn1 1),(),(2 2 ,expn,expn2 2),)
11、,( ,( n n ,expn ,expnn n)其中每个其中每个i i可能是一个常数，也可能又是一个多项式；对于每一可能是一个常数，也可能又是一个多项式；对于每一个多项式个多项式j j , ,又可以确定一个主变元（可称为原多项式的第二变又可以确定一个主变元（可称为原多项式的第二变元），从而，可表为下一级的一元多项式，其系数又可能性是常元），从而，可表为下一级的一元多项式，其系数又可能性是常数，也可能是多项式；数，也可能是多项式；直到最后纯粹的一元多项式。；直到最后纯粹的一元多项式。所以所以M M元多项式，最好用广义表来表示。其元素结点如下图：元多项式，最好用广义表来表示。其元素结点如下图：
12、表结点（多项式结点）表结点（多项式结点） 原子结点（常系数结点）原子结点（常系数结点）其形式定义如下：其形式定义如下：typedef struct MPNodeElemTag tag; /区分原子结点和表结点区分原子结点和表结点int expn; /指数域指数域union /原子结点和表结点共享一个域原子结点和表结点共享一个域 float coef; /系数域系数域struct MPNode *hp; /表结点的表头指针表结点的表头指针 struct MPNode *tp; /指向下一个元素结点指向下一个元素结点*MPList; /M元多项广义表类型元多项广义表类型M元多项式的表示元多项式的表
13、示例例:P(x,y,z)=:P(x,y,z)=x x1010y y3 3z z2 2+2x+2x6 6y y3 3z z2 2+3x+3x5 5y y2 2z z2 2+x+x4 4y y4 4z+6xz+6x3 3y y4 4z+2yz+15z+2yz+15=(x=(x1010y y3 3+2x+2x6 6y y3 3+3x+3x5 5y y2 2)z)z2 2 +(x+(x4 4y y4 4+6x+6x3 3y y4 4+2y)z+15+2y)z+15=(x=(x1010+2x+2x6 6)y)y3 3+3x+3x5 5y y2 2)z)z2 2 +(x +(x4 4+6x+6x3 3)y
14、)y4 4+2y)z+15+2y)z+15=Az=Az2 2+Bz+15z+Bz+15z0 0其中其中: A=Cy: A=Cy3 3+Dy+Dy2 2 C=xC=x1010+2x+2x6 6 D=3xD=3x5 5可用广义表表示为可用广义表表示为: :P(x,y,z)=z(A,2),(B,1),(15,0)P(x,y,z)=z(A,2),(B,1),(15,0)A=y(C,3),(D,2) B=y(E,4),(2,1)A=y(C,3),(D,2) B=y(E,4),(2,1)C=x(1,10),(2,6) E=x(1,4),(6,3) C=x(1,10),(2,6) E=x(1,4),(6,3) D=x(3,5)D=x(3,5) M元多项式的表示元多项式的表示三类表结点三类表结点(tag=1):域为变元域为变元数，数，层头结点层头结点(每层一个每层一个), exp域为相应变元在数组中的域为相应变元在数组中的下标，下标， 一般表结点一般表结点, exp域为指数。域为指数。
