【正文】 。 由表頭、表尾的定義易知：任何一個非空列表 其表頭可能是原子，也可能是列表，而其表尾必定 是列表。 廣義表的長度：表中元素的個數(shù)，深度：層次數(shù)，即括號的個數(shù)。例如： ① A = ( )—— A是一個空表，它的長度為零，深度為 1。 ② B = (e)—— 列表 B只有一個原子 e， B的長度為 1，深度也為 1。 ③ C = (a, (b, c, d))—— 列表 C的長度為 2，深度為 2，兩個元素分 別為原子 a和子表 (b, c, d)。 ④ D = (A, B, C)—— 列表 D的長度為 3，深度為 1， 3個元素都是 列表。將子表的值帶入后，則有 D = (( ), (e), (a, (b, c, d)))。 ⑤ E = (a, E)—— 這是一個遞歸的表，它的長度為 2，深度為 ∞。 E相當于一個無限的列表 E = (a, (a, (a, …))) 。 （ 2）廣義表的抽象數(shù)據(jù)類型定義 ADT GList { 數(shù)據(jù)對象： D={ ei| i=1,2,…,n ； n≥0； ei∈ AtomSet 或 ei∈ GList。} 數(shù)據(jù)關系： R1＝ { ei1, ei |ei1, ei ∈ D, 2≤i≤n} 基本操作： InitGList (amp。L)。 操作結果：創(chuàng)建空的廣義表 L。 CreateGList(amp。L, S)。 初始條件： S是廣義表的書寫形式串。 操作結果：由 S創(chuàng)建廣義表 L。 DestroyGList(amp。L)。 初始條件：廣義表 L已存在。 操作結果：銷毀廣義表 L。 CopyGList(amp。T, L)。 初始條件：廣義表 L已存在。 操作結果：由廣義表 L復制得到廣義表 T。 GListLength(L)。 初始條件：廣義表 L已存在。 操作結果：求廣義表 L的長度，即元素個數(shù)。 GListDepth(L)。 初始條件：廣義表 L已存在。 操作結果：求廣義表 L的深度。 GListEmpty(L)。 初始條件：廣義表 L已存在。 操作結果：判定廣義表 L是否為空。 GetHead(L)。 初始條件：廣義表 L已存在。 操作結果：取廣義表 L的頭。 GetTail(L)。 初始條件：廣義表 L已存在。 操作結果：取廣義表 L的尾。 InsertFirst_GL(amp。L, e)。 初始條件：廣義表 L已存在。 操作結果：插入元素 e作為廣義表 L的第一個元素。 DeleteFirst_GL (amp。L, amp。e)。 初始條件：廣義表 L已存在。 操作結果：刪除廣義表 L的第一個元素，并用 e返回其值。 Traverse_GL(L, visit())。 初始條件：廣義表 L已存在。 操作結果：遍歷廣義表 L，用函數(shù) visit處理每個元素， }ADT GList ① 列表的元素可以是子表，而子表的元素還可以 是子表 …… 故，列表是一個多層次的結構。如圖 示的列表 D。圖中圓圈表示列表，以方塊表示原子。 ② 列表可為其他列表所共享。 ③ 列表可以是一個遞歸的表，即列表也可以是其 本身的一個子表。 （ 3） 3個重要結論： D A B C E e a b c d 圖 列表的圖形表示 廣義表的存儲結構 因為廣義表的數(shù)據(jù)元素是不定的，所以通常采用鏈式存儲結構來表示。 （ 1）頭尾鏈表存儲表示 ① 結點結構 原子結點 tag = 0 atom tag = 1 hp tp 表結點 tag：標志域。 tag＝ 1表示表結點； tag＝ 0表示原子結點。 hp：指示表頭的指針域。 tp：指示表尾的指針域。 atom：值域。 ② C語言描述 typedef enum {ATOM, LIST}ElemTag。 //ATOM = = 0:原子， LIST = = 1:子表 typedef struct GLNode { ElemTag tag。 //公共部分，用于區(qū)分原子結點和表結點 union { //原子結點和表結點的聯(lián)合部分 AtomType atom。 //atom是原子結點的值域， AtomType由用戶定義 struct {struct GLNode *hp, *tp。} ptr。 //ptr是表結點的指針域， 和表尾 }。 } *GList。 ③ 圖形表示 例 1， D = (A, B, C)，其中 A = ( )， B = (e)， C = (a, (b, c, d))。如圖 (a)所示。 例 2， E = (a, E) 。如圖 (b)所示。 A = NULL (b) 廣義表的鏈表表示 —— 遞歸表（ P109 圖 ) 0 b 0 c 0 d D 1 1 1 B 1 C 1 1 0 e 0 a 1 1 1 (a) 例 1 E 1 1 0 a 圖 廣義表的存儲結構示例 ④ 特點 1．除空表的表頭指針為空外，對任何非空表，其表頭指針均指向一個表結點。 2．容易分清列表中原子和子表所在層次。 3．最高層的表結點個數(shù)即為列表的長度。 （ 2）擴展性鏈表存儲表示 ① 結點結構 tag = 1 hp tp 表結點 tag = 0 atom tp 原子結點 tag：標志域。 tag＝ 1表示表結點； tag＝ 0表示原子結點。 hp：指示表頭的指針域。 tp：指示表尾的指針域。 atom：值域。 ② C語言描述 typedef enum {ATOM, LIST}ElemTag。 //ATOM = = 0:原子， LIST = = 1:子表 typedef struct GLNode { ElemTag tag。 //公共部分，用于區(qū)分原子結點和表結點 union { //原子結點和表結點的聯(lián)合部分 AtomType atom。 //atom是原子結點的值域， AtomType由用戶定義 struct GLNode *hp。 //表結點的表頭指針 }。 struct GLNode *tp。 //相當于線性鏈表的 next，指向下一個元素結點 } *GList。 //廣義表類型 GList是一種擴展的線性鏈表 ③ 圖形表示 A 1 D 1 0 b 0 c 0 d 1 1 1 B 1 C 1 0 e 0 a 1 0 a 1 E