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