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

廣義表的介紹

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

廣義表的結構

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

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

廣義表的表示

書面表示

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

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

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

注意點：

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

畫圖表示

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

注意點：

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

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

廣義表的長度與深度

深度

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

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

長度

廣義表的長度：第一層結點的個數(shù)或深度為1的結點個數(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指令（表尾）：，將頭結點指向廣義表第一層第二個元素，并拋棄第一個元素。

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

結論：表尾的結果一定是子表

Head指令

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

• 書面表示形式：
  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
• 畫圖表示：

結論：表頭的結果可以是原子，也可以是子表

擴展線性表的存儲結構

作為拓展和了解

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

真題訓練

現(xiàn)在已經講解完了廣義表的全部內容，因為屬于理論科學，如果你是要考試的人建議您還是仔細閱讀你考試大綱對于此處的解釋，可能我講的和你們考的有些區(qū)別

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

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

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

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

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

解析：

1. 題目一：B，表尾必是子表，表頭可以是子表可以是原子。若錯誤可以查看Tail指令和Head指令
2. 題目二：C，長度表示廣義表第一層的元素個數(shù)，深度為括號最大層數(shù)
3. 題目三：B，
   1. 注意A的操作是沒有意義的NULL != ()
   2. B中Tail[L]應該是空，但是空的表示不是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