廣義表（Lists，又稱列表）是線性表的推廣。線性表定義為n>=0個元素a1,a2,a3,…,an的有限序列。線性表的元素僅限于原子項，原子是作為結構上不可分割的成分，它可以是一個數或一個結構，若放松對表元素的這種限制，容許它們具有其自身結構，這樣就產生了廣義表的概念。

?????廣義表是n (n>=0)個元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項，或者是一個廣義表。通常記作LS=（a1,a2,a3,…,an)。LS是廣義表的名字，n為它的長度。若ai是廣義表，則稱它為LS的子表。

抽象數據類型廣義表的定義如下：

ADT Glist

{

???數據對象：?D={ei | i=1,2,..,n;n>=0 ;??ei?AtomSet?或ei??Glist,

?????????????????????????????????????AtomSet為某個數據對象}

???數據關系：R1={< ei-1, ei > | ei-1 , ei??D,2<=i<=n}

???基本操作：

???????InitGList( &L);

?????????????操作結果：創建空的廣義表L。

???????CreateGList(&L,S);

?????????????初始條件：S是廣義表的書寫形式串。

?????????????操作結果：由S創建廣義表L。

???????DestroyGList(&L);

????????????初始條件：廣義表L存在。

????????????操作結果：銷毀廣義表L。

CopyGList( &T,L);

????????????初始條件：廣義表L存在。

????????????操作結果：由廣義表L復制得到廣義表T。

???????GListLength(L);

????????????初始條件：廣義表L存在。

????????????操作結果：求廣義表L的長度，即元素個數。

???????GListDepth(L);

????????????初始條件：廣義表L存在。

????????????操作結果：求廣義表L的深度。

???????GListEmpty (L);

????????????初始條件：廣義表L存在。

????????????操作結果：判定廣義表L是否為空。

???????GetHead(L);

????????????初始條件：廣義表L存在。

????????????操作結果：取廣義表L的頭。

GetTail( &T,L);

????????????初始條件：廣義表L存在。

????????????操作結果：取廣義表L的尾。

???????InsertFirst_GL(&L,e);

????????????初始條件：廣義表L存在。

????????????操作結果：插入元素e作為廣義表L的第一元素。

???????DeleteFirst_GL(&L,&e);

????????????初始條件：廣義表L存在。

????????????操作結果：刪除廣義表L的第一元素，并用e返回其值。

???????Traverse_GL (L,visit());

????????????初始條件：廣義表L存在。

????????????操作結果：遍歷廣義表L，用函數visit處理每個元素。

｝

通常用圓括號將廣義表括起來，用逗號分隔其中的元素。為了區別原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示原子。若廣義表LS（n>=1)非空，則a1是LS的表頭，其余元素組成的表(a2,…an)稱為LS的表尾。

????顯然廣義表是遞歸定義的，這是因為在定義廣義表時又用到了廣義表的概念。廣義表的例子如下：

（1）A=（）——A是一個空表，其長度為零。

（2）B=（e）——表B只有一個原子e，B的長度為1。

（3）C=（a,(b,c,d))——表C的長度為2，兩個元素分別

?????????為原子a和子表(b,c,d)。

（4）D=（A，B，C）——表D的長度為3，三個元素

????????都是廣義表。顯然，將子表的值代入后，

?????????則有D=(( ),(e),(a,(b,c,d)))。

（5）E=（E）——這是一個遞歸的表，它的長度為2，E相當于一個無限的廣義表E=(a,(a,(a,(a,…)))).

從上述定義和例子可推出廣義表的三個重要結論：

（1）廣義表的元素可以是子表，而子表的元素還可以是子表，。由此，廣義表是一個多層次的結構，可以用圖形象地表示。P108

?

（2）廣義表可為其它表所共享。例如在上述例（4）中，廣義表A，B，C為D的子表，則在D中可以不必列出子表的值，而是通過子表的名稱來引用。

?

（3）廣義表的遞歸性。

?????綜上所述，廣義表不僅是線性表的推廣，也是樹的推廣。

由表頭、表尾的定義可知：任何一個非空廣義表其表頭可能是原子，也可能是列表，而其表尾必定是列表。

??????????gethead(B)=e?????????gettail(B)=(??)

??????????gethead(D)=A????????gettail(D)=(B,C)

?

??????由于（B，C）為非空廣義表，則可繼續分解得到：

?????????gethead(B,C)=B?????????gettail(B,C)=(C)

??

????注意廣義表（?）和( ( ) )不同。前者是長度為0的空表，

對其不能做求表頭的和表尾的運算；而后者是長度為1的非空表（只不過該表中唯一的一個元素是空表）。對其可進行分解，得到表頭和表尾均為空表（?）。

?

?

廣義表的存儲結構

由于廣義表(a1,a2,a3,…an)中的數據元素可以具有不同的結構，（或是原子，或是廣義表），因此，難以用順序存儲結構表示，通常采用鏈式存儲結構，每個數據元素可用一個結點表示。

????由于廣義表中有兩種數據元素，原子或廣義表，因此，需要兩種結構的結點：一種是表結點，用以表示列表；一種是原子結點，用以表示原子。?

?

　　若列表不空，則可分解成表頭和表尾；反之，一對確定的表頭和表尾可唯一確定列表。由此，一個表結點可由三個域組成：標志域、指示表頭的指針域和指示表尾的指針域；而原子結點只需兩個域：標志域和值域。

1、僅有表結點由三個域組成：

　　　　標志域、指示表頭的指針域和指示表尾的指針域；而原子域只需兩個域：標志域和值域。

頭尾鏈表存儲表示

示例如圖：

這種存儲結構的三個特點：

1。除空表的表頭指針為空外，對任何非空列表，其表頭指針均指向一個表結點，且該結點中的hp域指示列表表頭，tp域指向列表表尾（除非表尾為空，則指針為空，否則必為表結點）；

2。容易分清列表中原子和子表所在層次。如在列表D中，原子e和a在同一層次上，而b、c和d在同一層次且比e和a低一層，B和C是同一層的子表；

3。最高層的表結點個數即為列表的長度。

?

2、表結點和原子結點均由三個域組成：標志域、指示表頭的指針域和指示表尾的指針域；原子結點的三個域為：標志域、值域和指示表尾的指針域。

其類型定義如下：

?

擴展線性鏈表存儲表示

示例如圖：