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

1、广义表的定义第5章 数组和广义表数组的定义数组的顺序表示和实现矩阵的压缩存储广义表的存储结构定义5.4 广义表的类型定义广义表是线性表的推广，也称为列表(lists)记为： LS = ( a1 , a2 , , an ) 广义表名 第一个元素是表头，而其余元素组成的表称为表尾 ai 为原子或广义表，习惯上用小写字母表示原子类型，用大写字母表示列表n是表长在广义表中约定：表头(Head）表尾 (Tail)讨论：广义表与线性表的区别和联系？5.4 广义表的类型定义LS = ( a1, a2, . , ai , . , an )ai 为原子或广义表1.在线性表的定义中，ai 只限于是单个元素。而在广

2、义表的定义中，ai 可以是单个元素，也可是广义表，分别称为广义表 LS 的原子类型和子表。2.当每个元素都为原子且类型相同时，就是线性表3.广义表是递归定义的线性结构广义表的特点有次序性有长度有深度可递归可共享5.4 广义表的类型定义广义表的特点有次序性5.4 广义表的类型定义广义表中的数据元素有固定的相对次序一个直接前驱和一个直接后继广义表的特点有长度5.4 广义表的类型定义广义表的长度定义为最外层括弧中包含的数据元素个数如: H = (d, (e,( ) 长度为2表元素个数一定，不能无限，可以是空表广义表的特点有深度5.4 广义表的类型定义广义表的深度定义为广义表中括弧的最大重数注意：(1

3、)空表的深度为1； (2)原子不是广义表，所以没有深度可言， 但可以认为它的深度为0。如: H = (d, (e,( )深度为3广义表的特点可递归5.4 广义表的类型定义广义表可以是一个递归的表如: E = (a, E) = (a, (a, (a, . ,) 递归表的深度是无穷值，长度是有限值深度为无穷大,长度为2广义表的特点可共享5.4 广义表的类型定义A = ( a , B ) =( a , ( b , c , d ) ) 广义表的元素可以为其他广义表所共享例1：求下列广义表的长度5.4 广义表的类型定义E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E为递归表1）A =( )

4、2）B = ( e ) 3）C =( a ,( b , c , d ) ) 4）D=( A , B ,C )5）E=(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)，共享表试用图形表示下列广义表5.4 广义表的类型定义 设 代表原子， 代表子表） e D=(A, B, C)=( ( ), (e), ( a, (b, c, d ) ) )的长度为3，深度为3DABCeabcd试用图形表示下列广义表.5.4 广义表的类型定义 A=( a ,

5、 (b, A) )A的长度为2，深度为ab广义表的的类型定义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) /由串S创建广义表L。 CopyGList(&T, L) / 由广义表L复制得到广义表T。 GListLength(L); GListDepth(L); GListEmp

6、ty(L); GetHead(L); GetTail(L) InsertFirst_GL(&L, e); /插入元素e作为广义表L的第一元素。 DeleteFirst_GL(&L, &e) /删除广义表L的第一元素，并用e返回其值。ADT Glist广义表的的类型定义5.4 广义表的类型定义介绍两种特殊的基本操作：GetHead(L) 取表头 (可能是原子或列表);GetTail(L) 取表尾 (一定是列表) 。例：求下列广义表操作的结果5.4 广义表的类型定义1. GetTail (b, k, p, h) ; 2. GetHead ( (a, b), (c, d) ) ; 3. GetTai

7、l ( (a, b), (c, d) ) ; 4. GetTail GetHead(a, b),(c, d) ;(k, p, h)( b )(a, b)5. GetTail (e) ; 6. GetHead ( ( ) ) .7. GetTail ( ( ) ) .( )(a, b)( )( )(c, d)注意：( )和( ( ) )的区别5.4 广义表的类型定义前者为空表，长度=0，深度=1；后者长度=1，深度=2，表头、表尾均为( )广义表的存储结构5.5 广义表的存储结构 由于广义表( a1, a2, ., an )是一种递归的数据结构，且其中的数据元素可以具有不同的结构（或是原子，或是

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

9、点表结点结点结构5.5 广义表的存储结构Typedef 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分别指 /向表头和表尾 ;*Glist ; 例：A = ( ) B = (

10、 e ) C = ( a , ( b , c , d ) ) D = ( A , B , C ) E = ( a , E )BACDE1e0a01b0c0d0a011111111115.5 广义表的存储结构C = ( a , ( b , c , d ) ) a01b0c0d01111C如何设定结点的结构最上层的表结点数即为广义表的长度层次清楚结点众多，与广义表括号不匹配，不容易还原广义表5.5 广义表的存储结构如何设定结点的结构5.5 广义表的存储结构方式二：同层结点链 对于原子结点，应包含值域和指向其后继结点的指针域 对于表结点，应包含指向表中第一个结点的表头指针域和指向其后继结点的指针域

11、如何设定结点的结构5.5 广义表的存储结构 为了把原子结点和表结点区分开，还必须在每个结点中增设一个标志域，让标志域取两种不同的值，从而区分不同的结点tag=1headpLp原子结点表结点tag=0atomtp结点结构5.5 广义表的存储结构Typedef 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如何设定结点的结构结点数目与广义表括号对一致递归算法不方便5.5 广