广 义 表

广义表一般记作：

​ LS=(a1,a2,.....an)，其中LS是广义表(a1,a2,.....an)的名称，n是其长度。在广义表的定义中，ai可以是单个元素，也可以是广义表，分别称为广义表LS的原子和字表。习惯上，用大写字母表示广义表的名称，用小写字母表示原子(广义表中的数据元素通常采用链式存储结构)。

1.下面列举一些广义表的例子：

(1) A=( ) A是一个空表，其长度为零。

(2) B=(e) B只有一个原子e，其长度为1.

(3) C=(a,(b,c,d)) C的长度为2，两个元素分别为原子a和子表(b,c,d)。

(4) D=(A,B,C) D的长度为3,3个元素都是广义表。显然，将子表的值代入后，则有D=(( ).(e),(a,(b,c,d)))

(5) E=(a,E) 这是一个递归的表，其长度为2,。E相当于一个无限的广义表 E=(a,(a(a,.......)))。

(6) L=(a,(b,c,d)) L的表头是a, 表尾是 ((b.c.d))。

2.广义表中最重要的两个运算如下。

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

复杂点的例子

广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）. Head(Tail(Head(Tail(Tail(A)))))

第一步： Tail(A)：(b,(c,d),(e,(f,g)))

第二步：Tail(Tail(A)) ： ((c,d),(e,(f,g)))

第三步： Head(……) ： (c,d)

第四步： Tail(……) ： (d)

第五步： Head(……) ： d