数据结构第5章数组和广义表2广义表ppt课件

1、武汉科技大学Wuhan University of Science and Technology张 凯计算机学院 软件工程系2019年3月12日:广义表的定义第第5 5章章 数组和广义表数组和广义表数组的定义数组的顺序表示和实现矩阵的紧缩存储广义表的存储构造:v定义定义5.4 广义表的类型定义广义表的类型定义广义表是线性表的推行，也称为列表(lists)记为： LS = ( a1 , a2 , , an ) 广义表名 第一个元素是表头，而其他元素组成的表称为表尾 ai 为原子或广义表，习惯上用小写字母表示原子类型，用大写字母表示列表n是表长在广义表中商定：表头(Head表尾 (Tail):v讨

2、论：广义表与线性表的区别和联络？讨论：广义表与线性表的区别和联络？5.4 广义表的类型定义广义表的类型定义LS = ( a1, a2, . , ai , . , an )ai 为原子或广义表1.在线性表的定义中，ai 只限于是单个元素。而在广义表的定义中，ai 可以是单个元素，也可是广义表，分别称为广义表 LS 的原子类型和子表。2.当每个元素都为原子且类型一样时，就是线性表3.广义表是递归定义的线性构造:v广义表的特点广义表的特点v有次序性有次序性v有长度有长度v有深度有深度v可递归可递归v可共享可共享5.4 广义表的类型定义广义表的类型定义:v广义表的特点广义表的特点v有次序性有次序性5.

3、4 广义表的类型定义广义表的类型定义广义表中的数据元素有固定的相对次序一个直接前驱和一个直接后继:v广义表的特点广义表的特点v有长度有长度5.4 广义表的类型定义广义表的类型定义广义表的长度定义为最外层括弧中包含的数据元素个数如: H = (d, (e,( ) 长度为2表元素个数一定，不能无限，可以是空表:v广义表的特点广义表的特点v有深度有深度5.4 广义表的类型定义广义表的类型定义广义表的深度定义为广义表中括弧的最大重数留意：(1)空表的深度为1； (2)原子不是广义表，所以没有深度可言， 但可以以为它的深度为0。如: H = (d, (e,( )深度为3:v广义表的特点广义表的特点v可递

4、归可递归5.4 广义表的类型定义广义表的类型定义广义表可以是一个递归的表如: E = (a, E) = (a, (a, (a, . ,) 递归表的深度是无穷值，长度是有限值深度为无穷大,长度为2:v广义表的特点广义表的特点v可共享可共享5.4 广义表的类型定义广义表的类型定义A = ( a , B ) =( a , ( b , c , d ) ) 广义表的元素可以为其他广义表所共享:v例例1：求以下广义表的长度：求以下广义表的长度5.4 广义表的类型定义广义表的类型定义E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E为递归表1A =( )2B = ( e ) 3C =( a ,(

5、 b , c , d ) ) 4D=( A , B ,C )5E=(a, E)n=0，由于A是空表n=1，表中元素e是原子n=2，a 为原子，(b, c, d)为子表n=3，3个元素都是子表n=2，a 为原子，E为子表D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表:v试用图形表示以下广义表试用图形表示以下广义表5.4 广义表的类型定义广义表的类型定义 设 代表原子， 代表子表 e D=(A, B, C)=( ( ), (e), ( a, (b, c, d ) ) )的长度为3，深度为3DABCeabcd:v试用图形表示以下广义表试用图形表示以下广义表.5.4 广义表的类型定义

6、广义表的类型定义 A=( a , (b, A) )A的长度为2，深度为ab:v广义表的的类型定义广义表的的类型定义5.4 广义表的类型定义广义表的类型定义ADT Glist 数据对象：数据对象：Dei | i=1,2,.,n; n0; ei AtomSet或或ei Glist AtomSet为某个数据对为某个数据对象象 数据关系：数据关系：LR| ei-1 ,ei D, 2in 根本操作：根本操作： InitGList(&L); /创建空的广义表创建空的广义表L。 DestroyGList(&L) /销毁广义表销毁广义表L。 CreateGList(&L, S) /由串

7、由串S创建广义表创建广义表L。 CopyGList(&T, L) / 由广义表由广义表L复制得到广义表复制得到广义表T。 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L) InsertFirst_GL(&L, e); /插入元素插入元素e作为广义表作为广义表L的第一元素。的第一元素。 DeleteFirst_GL(&L, &e) /删除广义表删除广义表L的第一元素，并用的第一元素，并用e前往其值。前往其值。ADT Glist:v广义表的的类型定义广义表的的类型定义5.4 广义

8、表的类型定义广义表的类型定义引见两种特殊的根本操作：GetHead(L) 取表头 (能够是原子或列表);GetTail(L) 取表尾 (一定是列表) 。:v例：求以下广义表操作的结果例：求以下广义表操作的结果5.4 广义表的类型定义广义表的类型定义1. GetTail (b, k, p, h) ; 2. GetHead ( (a, b), (c, d) ) ; 3. GetTail ( (a, b), (c, d) ) ; 4. GetTail GetHead(a, b),(c, d) ;(k, p, h)( b )(a, b)5. GetTail (e) ; 6. GetHead ( ( )

9、 ) .7. GetTail ( ( ) ) .( )(a, b)( )( )(c, d):v留意：留意：( )和和( ( ) )的区别的区别5.4 广义表的类型定义广义表的类型定义前者为空表，长度=0，深度=1；后者长度=1，深度=2，表头、表尾均为( ):v广义表的存储构造广义表的存储构造5.5 广义表的存储构造广义表的存储构造 由于广义表( a1, a2, ., an )是一种递归的数据构造，且其中的数据元素可以具有不同的构造或是原子，或是列表，因此难以用顺序存储构造表示，通常采用链式存储构造，每个数据元素可用一个结点表示。:v如何设定结点的构造？如何设定结点的构造？5.5 广义表的存储

10、构造广义表的存储构造方式一：表头表尾链 在一个广义表中，其数据元素有原子和列表之分，所以在对应的存储构造中，其存储结点也有相应划分。 对于原子结点，应包含值域； 对于表结点，应包含指示表头的表头指针域(指向表中的第一个元素)和指示表尾的表尾指针域(指向除去原表头元素后的广义表)。:v如何设定结点的构造？如何设定结点的构造？5.5 广义表的存储构造广义表的存储构造 为了把原子结点和表结点区分开，还必需在每个结点中增设一个标志域，让标志域取两种不同的值，从而区分不同的结点。tag=0atomtag=1headptailp原子结点表结点:v结点构造结点构造5.5 广义表的存储构造广义表的存储构造Ty

11、pedef enum ATOM, LIST Elemtag; /ATOM = = 0 ：原子：原子 LIST = = 1 ：子表：子表Typedef struct GLNode Elemtag tag; /标志域标志域 ；公共部分；公共部分,区分原子和表结点区分原子和表结点 union /原子结点和表结点的结合部分原子结点和表结点的结合部分 AtomType atom; /atom是原子结点的值域，是原子结点的值域，AtomType由用户定由用户定义义 struct struct GLNode *hp,*tp; ptr; /ptr是表结点的指针域，是表结点的指针域，ptr.hp、ptr.tp分

12、别指分别指 /向表头和表尾向表头和表尾 ;*Glist ; :例：A = ( ) B = ( e ) C = ( a , ( b , c , d ) ) D = ( A , B , C ) E = ( a , E )BACDE1e0a01b0c0d0a01111111111:5.5 广义表的存储构造广义表的存储构造C = ( a , ( b , c , d ) ) a01b0c0d01111C:v如何设定结点的构造如何设定结点的构造v最上层的表结点数即为广义表的长度最上层的表结点数即为广义表的长度v层次清楚层次清楚v结点众多，与广义表括号不匹配，不容结点众多，与广义表括号不匹配，不容易复原广义

13、表易复原广义表5.5 广义表的存储构造广义表的存储构造:v如何设定结点的构造如何设定结点的构造5.5 广义表的存储构造广义表的存储构造方式二：同层结点链 对于原子结点，应包含值域和指向其后继结点的指针域 对于表结点，应包含指向表中第一个结点的表头指针域和指向其后继结点的指针域 :v如何设定结点的构造如何设定结点的构造5.5 广义表的存储构造广义表的存储构造 为了把原子结点和表结点区分开，还必需在每个结点中增设一个标志域，让标志域取两种不同的值，从而区分不同的结点tag=1headpLp原子结点表结点tag=0atomtp:v结点构造结点构造5.5 广义表的存储构造广义表的存储构造Typedef

14、 enum ATOM,LIST Elemtag; /ATOM = = 0 ; 原子原子 LIST = = 1 ; 子表子表Typedef struct GLNode Elemtag tag; /标志域标志域 ；公共部分；公共部分,区分原子和表结点区分原子和表结点 union /原子结点和表结点的结合部分原子结点和表结点的结合部分 AtomType atom; /atom是原子结点的值域，是原子结点的值域，AtomType由用户定义由用户定义 struct GLNode *hp /表结点的表头指针表结点的表头指针 ； struct GLNode *tp /相当于线性链表的相当于线性链表的next，指向下一个元素结点，指向下一个元素结点;*Glist;:BDE1a0b0111c0d0Ae0C11111a01表头指针域:指向表中第一个结点例：A = ( ) B = ( e ) C = ( a , ( b , c , d ) ) D = ( A , B , C ) E = ( a , E ):5.5 广义表的存储构造广义表的存储构造C = ( a , ( b , c , d ) ) a0b01c0d0C1:v如何设定结点的构造如何设定结点的构造v结点数目与广义表括号对一致结点数目与广义表括号对一致v递归算法不方便递归算法不方便5.5 广义表的存储构造广义