《数据结构广义表》PPT课件.ppt

广义表,1 广义表的定义 2 广义表的基本运算 3 广义表的存储结构,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 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),(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 ElemTag typedef 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 MPNode ElemTag 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