71广义表的概念 广义表是n(n>0)个数据元素组成的序列,其中每个数 据元素或是单个数据元素(简称原子),或仍然是一个 广义表。 广义表可以看作是线性表的推广,但如果从原子数据元 素的角度看,一个数据元素有多个后继原子数据元素 就属于下一章要讨论的树型结构。所以,广义表本质上 是非线性结构
2 广义表是n（n≥0）个数据元素组成的序列，其中每个数 据元素或是单个数据元素（简称原子），或仍然是一个 广义表 。 广义表可以看作是线性表的推广，但如果从原子数据元 素的角度看，一个数据元素有多个后继原子数据元素， 就属于下一章要讨论的树型结构。所以，广义表本质上 是非线性结构。 7.1 广义表的概念
个广义表通常用一对圆括号括起来,这样当这个广义 表中的某个数据元素又是一个广义表时,就可以再用一对括 号括起来。广义表中的原子数据元素通常用小写字母表示 而广义表通常用大写字母表示。从结构上看一个广义表对应 了一棵树。例如,设有如下广义表: A=0 B=(a, b, c) (B,C)=(a,b,c),(d) E=(D,e)=((a,b,c),(d),el)
3 一个广义表通常用一对圆括号括起来，这样当这个广义 表中的某个数据元素又是一个广义表时，就可以再用一对括 号括起来。广义表中的原子数据元素通常用小写字母表示， 而广义表通常用大写字母表示。从结构上看一个广义表对应 了一棵树。例如，设有如下广义表： A = () B = (a, b, c) C = (d) D = (B, C) = ((a, b, c), (d)) E = (D, e) = (((a, b, c), (d)), e)
广义表E的图形表示
4 广义表E的图形表示 E B C D e a b c d
广义表的长度指广义表中数据元素(原子元素或广义表) 的个数。如广义表A的长度为0,广义表B的长度为3,广义 表C的长度为1,广义表D的长度为2(注意D中只有两个数 据元素B和C),广义表E的长度为2。 广义表的原子元素个数指广义表中原子数据元素的个数。 如广义表A的原子元素个数为0,广义表B的原子元素个数 为3,广义表C的原子元素个数为1,广义表D的原子元素个 数为4,广义表E的原子元素个数为5。 广义表的深度指广义表中所有原子数据元素到达根结点 的最大值。一个广义表对应了一棵树,广义表的深度即是 指广义表所对应的树的深度。如广义表A,B和C的深度均 为1,广义表D的深度为2,广义表E的深度为3
5 广义表的长度指广义表中数据元素（原子元素或广义表） 的个数。如广义表A的长度为0，广义表B的长度为3，广义 表C的长度为1，广义表D的长度为2（注意D中只有两个数 据元素B和C），广义表E的长度为2。 广义表的原子元素个数指广义表中原子数据元素的个数。 如广义表A的原子元素个数为0，广义表B的原子元素个数 为3，广义表C的原子元素个数为1，广义表D的原子元素个 数为4，广义表E的原子元素个数为5。 广义表的深度指广义表中所有原子数据元素到达根结点 的最大值。一个广义表对应了一棵树，广义表的深度即是 指广义表所对应的树的深度。如广义表A，B和C的深度均 为1，广义表D的深度为2，广义表E的深度为3
个广义表无论简单或复杂,都可以分做表头和表尾两 部分。任何一个非空广义表的表头既可能是原子也可能是 广义表,但非空广义表的表尾一定是一个广义表。 例如广义表(a,b),其表头为原子a,其表尾为广义表(b); 又例如广义表(b),其表头为原子b,其表尾为空广义表0; 又例如广义表(a,bc),(d),e),其表头为广义表 (a,b,c),(d)),其表尾为广义表(e) 对任何一个广义表的处理都可以由对表头的处理部分和 对表尾的处理部分两部分组成。 广义表有许多应用,其中最典型的,是在表处理语言 LSP中,把广义表作为基本的数据结构,就连程序也表示 为一系列的广义表。另外,广义表还可以用来表示m元多 项式。所谓m元多项式就是其每一项最多允许有m个变元
6 一个广义表无论简单或复杂，都可以分做表头和表尾两 部分。任何一个非空广义表的表头既可能是原子也可能是 广义表，但非空广义表的表尾一定是一个广义表。 例如广义表(a,b)，其表头为原子a，其表尾为广义表(b)； 又例如广义表(b)，其表头为原子b，其表尾为空广义表()； 又 例 如 广 义 表 (((a,b,c),(d)),e) ， 其 表 头 为 广 义 表 ((a,b,c),(d))，其表尾为广义表(e)。 对任何一个广义表的处理都可以由对表头的处理部分和 对表尾的处理部分两部分组成。 广义表有许多应用，其中最典型的，是在表处理语言 LISP中，把广义表作为基本的数据结构，就连程序也表示 为一系列的广义表。另外，广义表还可以用来表示m元多 项式。所谓m元多项式就是其每一项最多允许有m个变元
广义表抽象数据类型 数据集合: 广义表的数据集合可以表示为a,a1,a2,…,an1,每个 数据元素或是原子元素,或是一个广义表。 操作集合: (1)创建广义表 Creatglist(S) (2)求长度 GListLength(L) (3)求原子元素个数 GListAtomnum(L) (4)求深度 GListDepth(L)
7 数据集合： 广义表的数据集合可以表示为a0 , a1 , a2 , ..., an-1，每个 数据元素或是原子元素，或是一个广义表。 操作集合： （1）创建广义表CreatGList(S) （2）求长度GListLength(L) （3）求原子元素个数GListAtomNum(L) （4）求深度GListDepth(L) 广义表抽象数据类型
(5)判非空否 GListNotempty(L) (6)取表头 Gethead(L) (7)取表尾Geai(L) (8)插入 GListInsert(L,e) (9)删除 GListDeleter(L,e) (10)查找原子元素 GListSearch(L,e) (11)撒消 Destroy Liste(L)
8 （5）判非空否GListNotEmpty(L) （6）取表头GetHead(L) （7）取表尾GetTail(L) （8）插入GListInsert(L, e) （9）删除GListDelete(L, e) （10）查找原子元素GListSearch(L, e) （11）撤消DestroyGList(L)
72广义表的存储结构 头链和尾链存储结构 一个广义表可以由表头和表尾两部分组成,所以可以 用一个头指针和一个尾指针表示一个广义表。这样, 头链和尾链结构中一个结点的结构由一个标志域tag 决定:当tag值为1时,该结点除标志域外还有一个头 指针域和一个尾指针域;当tag值为0时,该结点除标 志城外还有一个原子元素域
9 7.2 广义表的存储结构 头链和尾链存储结构 一个广义表可以由表头和表尾两部分组成，所以可以 用一个头指针和一个尾指针表示一个广义表。这样， 头链和尾链结构中一个结点的结构由一个标志域tag 决定：当tag值为1时，该结点除标志域外还有一个头 指针域和一个尾指针域；当tag值为0时，该结点除标 志域外还有一个原子元素域
E-++A ∧ ∧ ∧ ∧0d
10 1 1 ∧ 1 1 ∧ 1 0 a 0 b E 1 1 ∧ 0 c 0 d 0 e 1 ∧ 1 ∧
原子和子表存储结构 观察上图中的结点可以发现,头链和尾链存储结构中 当结点为原子元素时,需要由头指针所指的结点存储 该原子元素。若此时在该结点中直接存储该原子元素, 则构成了原子和子表结构。其中标志tag含义同上 即tag值为1时,该结点除标志域外还有一个头指针域 和一个尾指针域;当tag值为0时,该结点除标志城外 还有一个原子元素城
11 原子和子表存储结构 观察上图中的结点可以发现，头链和尾链存储结构中 当结点为原子元素时，需要由头指针所指的结点存储 该原子元素。若此时在该结点中直接存储该原子元素， 则构成了原子和子表结构。其中标志tag含义同上， 即tag值为1时，该结点除标志域外还有一个头指针域 和一个尾指针域；当tag值为0时，该结点除标志域外 还有一个原子元素域
