廣義表的概念

??? 　廣義表(Lists，又稱列表)是線性表的推廣。即廣義表中放松對(duì)表元素的原子限制，容許它們具有其自身結(jié)構(gòu)。

1、廣義表定義
??? 　廣義表是n(n≥0)個(gè)元素a₁，a₂，…，a_i，…，a_n的有限序列。
? 其中：
??? 　①a_i--或者是原子或者是一個(gè)廣義表。
　? 　②廣義表通常記作：
?????????? ?? Ls=( a₁，a₂，…，a_i，…，a_n)。
　　? ③Ls是廣義表的名字，n為它的長(zhǎng)度。
　 　 ④若a_i是廣義表，則稱它為L(zhǎng)s的子表。
? 注意：
??? 　①?gòu)V義表通常用圓括號(hào)括起來(lái)，用逗號(hào)分隔其中的元素。
??? 　②為了區(qū)分原子和廣義表，書寫時(shí)用大寫字母表示廣義表，用小寫字母表示原子。
??? 　③若廣義表Ls非空(n≥1)，則a_l是LS的表頭，其余元素組成的表(a₁，a₂，…，a_n)稱為L(zhǎng)s的表尾。
???　 ④廣義表是遞歸定義的

2、廣義表表示
（1）廣義表常用表示
　　① E=()
???? 　E是一個(gè)空表，其長(zhǎng)度為0。
　　② L=(a，b)
???? 　L是長(zhǎng)度為2的廣義表，它的兩個(gè)元素都是原子，因此它是一個(gè)線性表
　　③ A=(x，L)=(x，(a，b))
???? 　A是長(zhǎng)度為2的廣義表，第一個(gè)元素是原子x，第二個(gè)元素是子表L。
　　④ B=(A，y)=((x，(a，b))，y)
　???? B是長(zhǎng)度為2的廣義表，第一個(gè)元素是子表A，第二個(gè)元素是原子y。
　　⑤ C=(A，B)=((x，(a，b))，((x，(a，b))，y))
???? 　C的長(zhǎng)度為2，兩個(gè)元素都是子表。
　　⑥ D=(a，D)=(a，(a，(a，(…))))
???? 　D的長(zhǎng)度為2，第一個(gè)元素是原子，第二個(gè)元素是D自身，展開后它是一個(gè)無(wú)限的廣義表。

（2）廣義表的深度
　　一個(gè)表的"深度"是指表展開后所含括號(hào)的層數(shù)。
? 【例】表L、A、B、C的深度為分別為1、2、3、4，表D的深度為∞。

（3）帶名字的廣義表表示
??? 　如果規(guī)定任何表都是有名字的，為了既表明每個(gè)表的名字，又說(shuō)明它的組成，則可以在每個(gè)表的前面冠以該表的名字，于是上例中的各表又可以寫成：
①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(zhuǎn)(a，D(a，D(…)))

（4）廣義表的圖形表示
（a）廣義表的圖形表示：
???　 ①圖中的分支結(jié)點(diǎn)對(duì)應(yīng)廣義表
???　 ②非分支結(jié)點(diǎn)一般是原子
??? 　③但空表對(duì)應(yīng)的也是非分支結(jié)點(diǎn)。
　　
（b）廣義表的圖形形狀劃分：
　　 ①與樹對(duì)應(yīng)的廣義表稱為純表，它限制了表中成分的共享和遞歸
　 　②允許結(jié)點(diǎn)共享的表稱再入表
? 【例】上圖(d),子表A是共享結(jié)點(diǎn)，它既是C的一個(gè)元素，又是子表B的元素；
　　 ③允許遞歸的表稱為遞歸表
? 【例】上圖(e)，表D是其自身的子表。

（5）遞歸表、再人表、純表、線性表之間的關(guān)系滿足：
?????
??　? 廣義表不僅是線性表的推廣，也是樹的推廣。

3、廣義表運(yùn)算
??? 　由于廣義表是對(duì)線性表和樹的推廣，并且具有共享和遞歸特性的廣義表可以和有向圖(見第7章)建立對(duì)應(yīng)，因此廣義表的大部分運(yùn)算與這些數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算類似。
??? 　在此，只討論廣義表的兩個(gè)特殊的基本運(yùn)算：取表頭head(Ls)和取表尾tail(Ls)。
??? 　根據(jù)表頭、表尾的定義可知：任何一個(gè)非空廣義表的表頭是表中第一個(gè)元素，它可以是原子，也可以是子表，而其表尾必定是子表。
? 【例】
????? head(L)=a， tail(L)=(b)
????? head(B)=A， tail(B)=(y)
? 由于tail(L)是非空表，可繼續(xù)分解得到：
????? head(tail(L))=b， tail(tail(L))=()
? 對(duì)非空表A和(y)，也可繼續(xù)分解。
? 注意:
??? 　廣義表()和(())不同。前者是長(zhǎng)度為0的空表，對(duì)其不能做求表頭和表尾的運(yùn)算；而后者是長(zhǎng)度為l的非空表(只不過(guò)該表中惟一的一個(gè)元素是空表)，對(duì)其可進(jìn)行分解，得到的表頭和表尾均是空表()。