广义表是啥？
广义表(Lists，又称列表)是一种非线性的数据结构，是线性表的一种推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。它被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中，广义表是一种最基本的数据结构，就连LISP 语言的程序也表示为一系列的广义表。（又见LISP，自从看了《黑客与画家》总感觉这LISP出现频率高了不少……）
广义表表示
（1）广义表常用表示
① E=() : E是一个空表，其长度为0。
② L=(a，b) : L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表
③ A=(x，L)=(x，(a，b)) : A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。
④ B=(A，y)=((x，(a，b))，y) : B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。
⑤ C=(A，B)=((x，(a，b))，((x，(a，b))，y)) : C的长度为2，两个元素都是子表。
⑥ D=(a，D)=(a，(a，(a，(…)))) : D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。
（2）广义表的深度
一个表的”深度”是指表展开后所含括号的层数。
【例】表L、A、B、C的深度为分别为1、2、3、4，表D的深度为∞。
（3）带名字的广义表表示
如果规定任何表都是有名字的，为了既表明每个表的名字，又说明它的组成，则可以在每个表的前面冠以该表的名字，于是上例中的各表又可以写成：
①E()
-
②L(a，b)
③A(x，L(a，b))
④B(A(x，L(a，b))，y)
⑤C(A(x，l(a，b))，B(A(x，L(a，b))，y))
⑥D(a，D(a，D(…)))
广义表运算
广义表的两个基本运算：取表头head(Ls)和取表尾tail(Ls)。
根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。
【例】
head(L)=a，tail(L)=(b)
head(B)=A，tail(B)=(y)
由于tail(L)是非空表，可继续分解得到：
head(tail(L))=b， tail(tail(L))=()
对非空表A和(y)，也可继续分解。
注意:广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()。
看了下说明还是不能够很理解，让我们来做道例题来加强理解：
2009年软考真题：若广义表L=((x,y,z),a,(u,t,w)),则从L中取出原子项y的运算是___?
A.head(tail(tail(L)))
B.tail(head(head(L)))
C.head(tail(head(L)))
D.tail(tail(head(L)))
正确答案：C
head(L) = (x,y,z) ; tail(L) = (a,(u,t,w))
head(head(L)) = x
tail(head(L)) = (y,z) //这一步理解了就行 tail得到的却是head外组成的新的广义表
head(tail(head(L))) = y
要注意的是head得到的是一个原子,而tail得到的却是原子外组成的新的广义表,不管是只有一个元素,但也是一个广义表,而不是直接的元素。
閱讀更多 看到他請叫他快去學習 的文章
