5.4 广义表—广义表的定义和基本运算
顾名思义，广义表是线性表的推广。也有人称其为列表（Lists，用复数形式以示与统称的表List 的区别）。
我们知道，线性表是由n 个数据元素组成的有限序列。其中每个组成元素被限定为单元素，有时这种限制需要拓宽。例如，中国举办的某体育项目国际邀请赛，参赛队清单可采用如下的表示形式：
在这个拓宽了的线性表中，韩国队应排在美国队的后面，但由于某种原因未参加，成为空表。国家队、河北队、四川队均作为东道主的参赛队参加，构成一个小的线性表，成为原线性表的一个数据项。这种拓宽了的线性表就是广义表。
广义表（Generalized Lists）是n（n≥0）个数据元素a1，a2，…，ai，…，an 的有序序列，一般记作：
其中：ls 是广义表的名称，n 是它的长度。每个ai（1≤i≤n）是ls 的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表ls 的单元素和子表。当广义表ls 非空时，称第一个元素a1 为ls 的表头（head），称其余元素组成的表（a2，…，ai，…，an）为ls 的表尾（tail）。显然，广义表的定义是递归的。
为书写清楚起见，通常用大写字母表示广义表，用小写字母表示单个数据元素，广义表用括号括起来，括号内的数据元素用逗号分隔开。下面是一些广义表的例子：
A ＝（）
B ＝（e）
C ＝（a，（b，c，d））
D ＝（A，B，C）
E ＝（a，E）
F ＝（（））
从上述广义表的定义和例子可以得到广义表的下列重要性质：
⑴广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，…。
⑵广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表E 就是一个递归的表。
⑶广义表可以为其他表所共享。例如，表A、表B、表C 是表D 的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。
广义表的上述特性对于它的使用价值和应用效果起到了很大的作用。
广义表可以看成是线性表的推广，线性表是广义表的特例。广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。当二维数组的每行（或每列）作为子表处理时，二维数组即为一个广义表。另外，树和有向图也可以用广义表来表示。由于广义表不仅集中了线性表、数组、树和有向图等常见数据结构的特点，而且可有效地利用存储空间，因此在计算机的许多应用领域都有成功使用广义表的实例。
广义表有两个重要的基本操作，即取头操作（Head）和取尾操作（Tail）。根据广义表的表头、表尾的定义可知，对于任意一个非空的列表，其表头可能是单元素也可能是列表，而表尾必为列表。例如：
Head（B）＝ e Tail（B）＝（）
Head（C）＝ a Tail（C）＝（（b，c，d））
Head（D）＝ A Tail（D）＝（B，C）
Head（E）＝ a Tail（E）＝（E）
Head（F）＝（） Tail（F）＝（）
此外，在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。
CreateLists(ls)：根据广义表的书写形式创建一个广义表ls。
IsEmpty(ls)：若广义表ls 空，则返回True；否则返回False。
Length(ls)：求广义表ls 的长度。
Depth(ls)：求广义表ls 的深度。
Locate(ls，x)：在广义表ls 中查找数据元素x。
Merge(ls1，ls2)：以ls1 为头、ls2 为尾建立广义表。
CopyGList(ls1，ls2)：复制广义表，即按ls1 建立广义表ls2。
Head(ls)：返回广义表ls 的头部。
Tail(ls)：返回广义表的尾部。
……
⒈广义表的定义和性质
我们知道，线性表是由n 个数据元素组成的有限序列。其中每个组成元素被限定为单元素，有时这种限制需要拓宽。例如，中国举办的某体育项目国际邀请赛，参赛队清单可采用如下的表示形式：
（俄罗斯，巴西，（国家，河北，四川），古巴，美国，（），日本）
在这个拓宽了的线性表中，韩国队应排在美国队的后面，但由于某种原因未参加，成为空表。国家队、河北队、四川队均作为东道主的参赛队参加，构成一个小的线性表，成为原线性表的一个数据项。这种拓宽了的线性表就是广义表。
广义表（Generalized Lists）是n（n≥0）个数据元素a1，a2，…，ai，…，an 的有序序列，一般记作：
ls＝（a1，a2，…，ai，…，an）
其中：ls 是广义表的名称，n 是它的长度。每个ai（1≤i≤n）是ls 的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表ls 的单元素和子表。当广义表ls 非空时，称第一个元素a1 为ls 的表头（head），称其余元素组成的表（a2，…，ai，…，an）为ls 的表尾（tail）。显然，广义表的定义是递归的。
为书写清楚起见，通常用大写字母表示广义表，用小写字母表示单个数据元素，广义表用括号括起来，括号内的数据元素用逗号分隔开。下面是一些广义表的例子：
A ＝（）
B ＝（e）
C ＝（a，（b，c，d））
D ＝（A，B，C）
E ＝（a，E）
F ＝（（））
⒉广义表的性质
从上述广义表的定义和例子可以得到广义表的下列重要性质：
⑴广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，…。
⑵广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表E 就是一个递归的表。
⑶广义表可以为其他表所共享。例如，表A、表B、表C 是表D 的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。
广义表的上述特性对于它的使用价值和应用效果起到了很大的作用。
广义表可以看成是线性表的推广，线性表是广义表的特例。广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。当二维数组的每行（或每列）作为子表处理时，二维数组即为一个广义表。另外，树和有向图也可以用广义表来表示。由于广义表不仅集中了线性表、数组、树和有向图等常见数据结构的特点，而且可有效地利用存储空间，因此在计算机的许多应用领域都有成功使用广义表的实例。
⒊广义表基本运算
广义表有两个重要的基本操作，即取头操作（Head）和取尾操作（Tail）。根据广义表的表头、表尾的定义可知，对于任意一个非空的列表，其表头可能是单元素也可能是列表，而表尾必为列表。例如：
Head（B）＝ e Tail（B）＝（）
Head（C）＝ a Tail（C）＝（（b，c，d））
Head（D）＝ A Tail（D）＝（B，C）
Head（E）＝ a Tail（E）＝（E）
Head（F）＝（） Tail（F）＝（）
此外，在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。
CreateLists(ls)：根据广义表的书写形式创建一个广义表ls。
IsEmpty(ls)：若广义表ls 空，则返回True；否则返回False。
Length(ls)：求广义表ls 的长度。
Depth(ls)：求广义表ls 的深度。
Locate(ls，x)：在广义表ls 中查找数据元素x。
Merge(ls1，ls2)：以ls1 为头、ls2 为尾建立广义表。
CopyGList(ls1，ls2)：复制广义表，即按ls1 建立广义表ls2。
Head(ls)：返回广义表ls 的头部。
Tail(ls)：返回广义表的尾部。
……
