数据结构广义表精品文稿.ppt

上传人:石*** 文档编号:71827579 上传时间:2023-02-06 格式:PPT 页数:16 大小:1.20MB
返回 下载 相关 举报
数据结构广义表精品文稿.ppt_第1页
第1页 / 共16页
数据结构广义表精品文稿.ppt_第2页
第2页 / 共16页
点击查看更多>>
资源描述

《数据结构广义表精品文稿.ppt》由会员分享,可在线阅读,更多相关《数据结构广义表精品文稿.ppt(16页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构广义表第1页,本讲稿共16页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为表的长度,当长度为为表的长

2、度,当长度为0 0时称为时称为空表空表;称非空表的第一个元素称非空表的第一个元素d d1 1为为表头表头,其余元素组成的其余元素组成的表表(d d2 2,d,dn n)称为称为表尾表尾。第2页,本讲稿共16页注意:注意:表尾可以可以是空表,而表头可以是原子,也可以是一个表表尾可以可以是空表,而表头可以是原子,也可以是一个表。广义表的抽象类型定义采用递归定义如教材广义表的抽象类型定义采用递归定义如教材P.107P.107。二、二、广义表的表达方式及例子广义表的表达方式及例子1 1A=()AA=()A是一个空表,其长度为是一个空表,其长度为0 0。2 2B=(e)B=(e)列表列表B B只有一个原

3、子只有一个原子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页5 E=(a,E)这是一个递归列表,其元素中有自己。这是一个递归列

4、表,其元素中有自己。广义表也可以用图形表示,例如前述的广义表广义表也可以用图形表示,例如前述的广义表D和和E可表示为:可表示为:beacdaDABC广义表广义表DE广义表广义表E第4页,本讲稿共16页2 2 广义表广义表的的基本运算基本运算广义表的基本运算广义表的基本运算 取表头取表头 HEAD(LS)HEAD(LS);取表尾取表尾 TAIL(LS)TAIL(LS)。第5页,本讲稿共16页3 3 广义表的广义表的存储结构存储结构 广义表中的数据元素可以是单元素,或是广义表,广义表中的数据元素可以是单元素,或是广义表,很很难用顺序存储结构表示,常采用链式存储结构。难用顺序存储结构表示,常采用链式

5、存储结构。1.1.表头表尾链表头表尾链存储结构存储结构 有两类结点:表结点和单元素结点。有两类结点:表结点和单元素结点。tag=1 hp tp 表结点表结点 tag=0 data 单元素结点单元素结点 tagtag标志域,标志域,0 0表示结点为单元素结点,表示结点为单元素结点,1 1表示为表结点;表示为表结点;hphp:表头指针域;表头指针域;tptp:表尾指针域;表尾指针域;datadata:值域。值域。第6页,本讲稿共16页3 3 广义表的广义表的存储结构存储结构形式描述为:形式描述为:typedef enum ATOM,LIST ElemTagtypedef enum ATOM,LIS

6、T 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分别指向广义

7、表的表头和表尾。*Glist;Glist;/广义表类型 第7页,本讲稿共16页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页3 3 广

8、义表的广义表的存储结构存储结构2.2.同层结点链存储结构同层结点链存储结构 有两类结点:表结点和单元素结点。有两类结点:表结点和单元素结点。tag=1 hp tp 表结点表结点 tag=0 data tp 单元素结点单元素结点 结点结构结点结构是无论什么结点都有三个域:是无论什么结点都有三个域:第一个域是结点类型标志第一个域是结点类型标志tagtag;第二个域是指向一个列表的指针(当第二个域是指向一个列表的指针(当tag=1tag=1时)时)或一个原子(当或一个原子(当tag=0tag=0时);时);第三个域是指向下一个结点的指针第三个域是指向下一个结点的指针tp。第9页,本讲稿共16页3 3

9、 广义表的广义表的存储结构存储结构形式描述为:形式描述为: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 GLNo

10、de *hp,;/表结点的表头指针域 ;struct GLNode *tp;struct GLNode *tp;/指向下一个结点的指针*Glist;Glist;/广义表类型 第10页,本讲稿共16页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页 应用:应用:M元多

11、项式的表示元多项式的表示 对任何一个对任何一个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,又可以

12、确定一个主变元(可称为原多项式的第二变元),从而,可表又可以确定一个主变元(可称为原多项式的第二变元),从而,可表为下一级的一元多项式,其系数又可能性是常数,也可能是多项式;为下一级的一元多项式,其系数又可能性是常数,也可能是多项式;直到最后纯粹的一元多项式。;直到最后纯粹的一元多项式。所以所以M M元多项式,最好用广义表来表示。其元素结点如下图:元多项式,最好用广义表来表示。其元素结点如下图:表结点(多项式结点)表结点(多项式结点)原子结点(常系数结点)原子结点(常系数结点)tag=1 exp hp tptag=1 exp hp tptag=0 exp coef tptag=0 exp co

13、ef tp第12页,本讲稿共16页其形式定义如下:其形式定义如下:typedef struct MPNodeElemTag tag;/区分原子结点和表结点区分原子结点和表结点int expn;/指数域指数域union /原子结点和表结点共享一个域原子结点和表结点共享一个域 float coef;/系数域系数域struct MPNode *hp;/表结点的表头指针表结点的表头指针 struct MPNode *tp;/指向下一个元素结点指向下一个元素结点*MPList;/M元多项广义表类型元多项广义表类型M元多项式的表示元多项式的表示第13页,本讲稿共16页例例:P(x,y,z)=P(x,y,z

14、)=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

15、+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元多

16、项式的表示元多项式的表示第14页,本讲稿共16页存储表示存储表示存储表示存储表示(1)(1)结点结构结点结构结点结构结点结构 表结点表结点表结点表结点 单元素结点单元素结点单元素结点单元素结点(2)(2)用一维数组存储多项式的所有变元用一维数组存储多项式的所有变元用一维数组存储多项式的所有变元用一维数组存储多项式的所有变元(3)(3)每一层增设一个表头结点每一层增设一个表头结点每一层增设一个表头结点每一层增设一个表头结点,并用并用并用并用expexp域表明变元在数组域表明变元在数组域表明变元在数组域表明变元在数组中的下标中的下标中的下标中的下标(4)(4)增设一个表头结点增设一个表头结点增设一

17、个表头结点增设一个表头结点,表示整个表表示整个表表示整个表表示整个表,用头指针用头指针用头指针用头指针p p指示指示指示指示,并在并在并在并在expexp域填上变元个数域填上变元个数域填上变元个数域填上变元个数tag=1 exp hp tptag=1 exp hp tptag=0 exp coef tptag=0 exp coef tp第15页,本讲稿共16页前例前例前例前例: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,

18、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)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页

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 大学资料

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁