隨筆由來（不重要）：一開始還真不知道有這個(gè)廣義表，算法書上也沒有看到。直到做題才看到廣義表。度娘找了幾篇博客都講的很散很亂。所以寫下這篇博客希望能夠讓自己和看到這篇博客的人能夠理解廣義表。如果有錯(cuò)誤請?jiān)u論給我我看到后會(huì)及時(shí)更改

廣義表的介紹

廣義表：廣義表其實(shí)就是一個(gè)典型的單向鏈表，即線性表的一種。存儲(chǔ)的類型包括原子元素（單個(gè)數(shù)據(jù)）或另一個(gè)廣義表（子表）

廣義表的結(jié)構(gòu)

1. Tag:既然存儲(chǔ)類型是數(shù)據(jù)或表，就需要準(zhǔn)備一個(gè)標(biāo)簽來標(biāo)明當(dāng)前存儲(chǔ)數(shù)據(jù)是數(shù)據(jù)還是表，那個(gè)Tag的作用就是充當(dāng)一個(gè)標(biāo)識(shí)作用。0表示數(shù)據(jù)、1表示子表、2表示另一張廣義表^[1]。
2. List/Data：專門用于存儲(chǔ)數(shù)據(jù)
3. Link：用于連接同一層的下一個(gè)結(jié)點(diǎn)

[1]: 對于用2表示另一張廣義表我對度娘結(jié)果的少部分查詢中僅僅在一處發(fā)現(xiàn)，但是如果不用2表示對于代碼計(jì)算深度會(huì)出現(xiàn)無法計(jì)算的問題。這里我選擇使用2來表示另一張廣義表.

廣義表的表示

書面表示

以 L = (A,b,(c,d)) 為例

1. 書面表示法無需表示Tag與Link。
2. 大寫字母表示一個(gè)廣義表，當(dāng)僅僅只有一個(gè)廣義表時(shí)一般用大寫L表示
3. 用（）表示一張表，數(shù)據(jù)用,隔開。
   1. 如果嵌套一張子表，可以繼續(xù)用（）來表示
   2. 如果嵌套其他廣義表，可以用對應(yīng)表的大小字母表示

所以L = (A,b,(c,d))表示的意思是：有一張廣義表L，里面包含的數(shù)據(jù)是另一個(gè)廣義表A、數(shù)據(jù)b、子表。子表元素為數(shù)據(jù)b、數(shù)據(jù)c

注意點(diǎn)：

1. 空表的表示形式不是L=NULL,而是L=()
2. 在有些奇奇怪怪的地方，廣義表的表示可能會(huì)省略=。長的是這樣：L(a,(b,c))

畫圖表示

正確的畫法應(yīng)該是箭頭初始端應(yīng)該畫到框框內(nèi)，但是我用的畫圖軟件這樣子好麻煩就懶得弄了

注意點(diǎn)：

1. 每一張廣義表或子表都必須帶有一個(gè)頭結(jié)點(diǎn)去連接對應(yīng)的值
2. 當(dāng)內(nèi)容為空時(shí)，用∧來表示
3. 有些書上廣義表的數(shù)據(jù)如果連接的是另一張空的廣義表，則會(huì)在對應(yīng)數(shù)據(jù)位直接用∧表示，而不是選擇去連接^[2]。

[2]:我這里認(rèn)為如果這么表示可能對于像我一樣腦子不靈光的人去理解深度會(huì)有點(diǎn)What，所以我選擇畫圖的時(shí)候進(jìn)行連接

廣義表的長度與深度

深度

廣義表的深度：括號(hào)最大層數(shù)；可以理解為樹的結(jié)點(diǎn)最大層次?？蠢}

1. L=()深度為1
2. L=(a,b,c,d,e,f,g）深度為1
3. L=(a,b,(c,d),e) 深度為2
4. L=((),(),()) 深度為2
5. L=((a,c),(c,(d,e),f)) 深度為3

長度

廣義表的長度：第一層結(jié)點(diǎn)的個(gè)數(shù)或深度為1的結(jié)點(diǎn)個(gè)數(shù)?？蠢}

1. L=（）長度為1
2. L=（a,b）長度為2
3. L=（a,（b,c））長度為2
4. L=（（a）,（b），（c,(a,())）長度為3

TAIL表尾指令和HEAD表頭指令

Tail指令

Tail指令（表尾）：，將頭結(jié)點(diǎn)指向廣義表第一層第二個(gè)元素，并拋棄第一個(gè)元素。

• 書面表示形式：
  1. L=(a,b,c);Tail[L]=(b,c)
  2. L=((a,b),c);Tail[L]=(c)
• 畫圖表示：

結(jié)論：表尾的結(jié)果一定是子表

Head指令

Head指令（表頭）：直接獲取廣義表的第一層的第一個(gè)元素

• 書面表示形式：
  1. L=(a,b,c);Head[L]=a
  2. L=((a,b),c);Head[L]=((a,b));Head[Head[L]]=(a,b);Head[Head[Head[L]]]=a
• 畫圖表示：

結(jié)論：表頭的結(jié)果可以是原子，也可以是子表

擴(kuò)展線性表的存儲(chǔ)結(jié)構(gòu)

作為拓展和了解

由之前的圖可知廣義表存儲(chǔ)結(jié)構(gòu)的一個(gè)很大的缺點(diǎn)。
一、tag竟然出現(xiàn)了2，這樣每個(gè)表在tag字段就需要用2bit來存儲(chǔ)，且會(huì)造成11(B)被浪費(fèi)。那么可以讓每次連接其他的廣義表時(shí)直接連接其第一個(gè)元素而不是表頭
二、對于畫圖階段，每次連接一個(gè)子表或其他廣義表時(shí)都需要先在數(shù)據(jù)處連接表頭，再連接數(shù)據(jù)。這樣對于計(jì)算深度及其不方便。那么對于同一層的結(jié)點(diǎn)都用Link去連接

真題訓(xùn)練

現(xiàn)在已經(jīng)講解完了廣義表的全部內(nèi)容，因?yàn)閷儆诶碚摽茖W(xué)，如果你是要考試的人建議您還是仔細(xì)閱讀你考試大綱對于此處的解釋，可能我講的和你們考的有些區(qū)別

題目一：一個(gè)非空廣義表的表尾（）——廣東工業(yè)大學(xué)2019
A：不可能是子表；B：只能是子表；C：只能是原子；D：可能是子表或原子

題目二：設(shè)廣義表L=((a,b,c)),則L的長度和深度分別為()——上海海事大學(xué)2018
A：1 1；B：1 3；C：1 2；D： 2 3

題目三：若廣義表L滿足Head(L)=Tail(L),則L為()——揚(yáng)州大學(xué)2017
A：()；B：(())；C：((),())；D：((),(),())

題目四：已知廣義表L=((x,y,z),a,(u,y,t))，從L中取出y的操作時(shí)？——此題簡化

----------------------------------解析線-----------------------------------

解析：

1. 題目一：B，表尾必是子表，表頭可以是子表可以是原子。若錯(cuò)誤可以查看Tail指令和Head指令
2. 題目二：C，長度表示廣義表第一層的元素個(gè)數(shù)，深度為括號(hào)最大層數(shù)
3. 題目三：B，
   1. 注意A的操作是沒有意義的NULL != ()
   2. B中Tail[L]應(yīng)該是空，但是空的表示不是NULL而是()。() == ()
   3. C：() != (())
   4. D：() != ((),())
4. 題目四：Head[Tail[Head[Tail[Tail[L]]]]]
   1. Tail[L] = (a,(u,y,t))
   2. Tail[Tail[L]] = ((u,y,t))
   3. Head[Tail[Tail[L]]] = (u,y,t)
   4. Tail[Head[Tail[Tail[L]]]] = (y,t)
   5. Head[Tail[Head[Tail[Tail[L]]]]] = y