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个变元