广义表

1 广义表的作用

数组可以存储不可再分的数据元素（如元素1，字符‘a’），也可以存储数组。但在数组中，两种不同类型的存储元素不能出现在同一个数组中。

例如在数组中，可以存储{1,2,3}，也可以创建二维数组{1,{1,2,3}}，但数组不适合存储类似多维数组的元素，会极大的造成存储空间的浪费。

对于存储多维数组可以使用广义表结构来存储。

广义表，又称为列表，是一种线性存储结构。同数组类似，既可以存储不可再分的元素，也可以存储广义表，称作：，其中代表广义表的名称，表示广义表存储的数据，广义表中每个既可以代表单个元素，也可以代表另一个广义表，习惯上用大写字母表示广义表的名字，用小写字母表示原子。

在广义表中，存储的单个元素称为原子，存储的广义表称为子表。

2 广义表的结论

1. 广义表的元素可以使子表，而子表的元素还可以是子表。由此，广义表是一个多层次的结构，可以用图形抽象表示。如图所示，D是广义表，圆圈表示广义表，方块表示原子。

2. 广义表可为其他广义表所共享，如上图，广义表A、B和C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。
3. 广义表可以是一个递归的表，即广义表也可以是其本身的一个子表。

3 广义表的两个重要运算

1. 取表头GetHead(LS)：取出的表头为非空广义表中的第一个元素，它可以是一个单原子，也可以是一个子表。
2. 取表尾GetTail(LS)：**取出的表尾为除去表头之外，由其他元素构成的表。**即表尾一定是一个广义表。

例如：

GetHead(B)=e GetTail(B)=()

GetHead(D)=A GetTail(D)=(B,C)，

由于B,C是广义表，则可继续分解得到：

GetHead(B,C)=B GetTail(B,C)=C

广义表()和(())不同，前者为空表，长度n=0；后者长度n=1，可继续分解得到其表头，表尾均为空表()。