廣義表是啥？
廣義表(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得到的卻是原子外組成的新的廣義表,不管是隻有一個元素,但也是一個廣義表,而不是直接的元素。
閱讀更多 看到他請叫他快去學習 的文章
