廣義表（Lists，又稱列表）是線性表的推廣仰禽。線性表定義為n>=0個元素a1,a2,a3,…,an的有限序列吐葵。線性表的元素僅限于原子項，原子是作為結構上不可分割的成分粒褒，它可以是一個數(shù)或一個結構，若放松對表元素的這種限制，容許它們具有其自身結構清笨，這樣就產(chǎn)生了廣義表的概念刃跛。
廣義表是n (n>=0)個元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項检号，或者是一個廣義表。通常記作LS=（a1,a2,a3,…,an)齐苛。LS是廣義表的名字凹蜂，n為它的長度。若ai是廣義表汰瘫，則稱它為LS的子表擂煞。
抽象數(shù)據(jù)類型廣義表的定義如下：
ADT Glist
{
數(shù)據(jù)對象：D={ei | i=1,2,..,n;n>=0 ;ei?AtomSet或ei?Glist,
AtomSet為某個數(shù)據(jù)對象}
數(shù)據(jù)關系：R1={< ei-1, ei > | ei-1 , ei?D,2<=i<=n}
基本操作：
InitGList( &L);
操作結果：創(chuàng)建空的廣義表L。
CreateGList(&L,S);
初始條件：S是廣義表的書寫形式串蝗拿。
操作結果：由S創(chuàng)建廣義表L蛹磺。
DestroyGList(&L);
初始條件：廣義表L存在同仆。
操作結果：銷毀廣義表L。
CopyGList( &T,L);
初始條件：廣義表L存在俗或。
操作結果：由廣義表L復制得到廣義表T岁忘。
GListLength(L);
初始條件：廣義表L存在干像。
操作結果：求廣義表L的長度，即元素個數(shù)速客。
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剧蹂，用函數(shù)visit處理每個元素烦却。
｝
通常用圓括號將廣義表括起來，用逗號分隔其中的元素冒冬。為了區(qū)別原子和廣義表窄驹，書寫時用大寫字母表示廣義表证逻，用小寫字母表示原子囚企。若廣義表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)=egettail(B)=()
gethead(D)=Agettail(D)=(B,C)
由于（B待逞，C）為非空廣義表，則可繼續(xù)分解得到：
gethead(B,C)=Bgettail(B,C)=(C)
注意廣義表（）和( ( ) )不同震束。前者是長度為0的空表，
對其不能做求表頭的和表尾的運算嘉栓；而后者是長度為1的非空表（只不過該表中唯一的一個元素是空表）。對其可進行分解馋辈，得到表頭和表尾均為空表（）。
廣義表的存儲結構
由于廣義表(a1,a2,a3,…an)中的數(shù)據(jù)元素可以具有不同的結構答毫，（或是原子，或是廣義表）蚕脏，因此，難以用順序存儲結構表示挣棕，通常采用鏈式存儲結構固耘，每個數(shù)據(jù)元素可用一個結點表示。
由于廣義表中有兩種數(shù)據(jù)元素损敷，原子或廣義表，因此诱桂，需要兩種結構的結點：一種是表結點，用以表示列表触菜；一種是原子結點涡相，用以表示原子。
若列表不空丙号，則可分解成表頭和表尾；反之，一對確定的表頭和表尾可唯一確定列表枝恋。由此畦攘，一個表結點可由三個域組成：標志域、指示表頭的指針域和指示表尾的指針域朗徊；而原子結點只需兩個域：標志域和值域象踊。
1、僅有表結點由三個域組成：
標志域史隆、指示表頭的指針域和指示表尾的指針域；而原子域只需兩個域：標志域和值域熔酷。
頭尾鏈表存儲表示
[cpp]view plaincopy
typedefenum{ATOM,LIST?}?ElemTag;//ATOM==0:表示原子,LIST==1:表示子表
typedefstructGLNode?{
ElemTag??tag;//公共部分躺酒，用以區(qū)分原子部分和表結點
union{//原子部分和表結點的聯(lián)合部分
AtomType??atom;//atom是原子結點的值域,AtomType由用戶定義
struct{structGLNode?*hp,?*tp;}?ptr;
//?ptr是表結點的指針域,ptr.hp?和ptr.tp分別指向表頭和表尾
};
}?*Glist;//廣義表類型
示例如圖：
這種存儲結構的三個特點：
1量愧。除空表的表頭指針為空外偎肃，對任何非空列表，其表頭指針均指向一個表結點，且該結點中的hp域指示列表表頭岸啡，tp域指向列表表尾（除非表尾為空擂送，則指針為空，否則必為表結點）；
2嘀趟。容易分清列表中原子和子表所在層次酌泰。如在列表D中，原子e和a在同一層次上也糊，而b、c和d在同一層次且比e和a低一層，B和C是同一層的子表僧凰；
3隙弛。最高層的表結點個數(shù)即為列表的長度萍启。
2、表結點和原子結點均由三個域組成：標志域、指示表頭的指針域和指示表尾的指針域；原子結點的三個域為：標志域、值域和指示表尾的指針域瘾带。
其類型定義如下：
擴展線性鏈表存儲表示
[cpp]view plaincopy
Typedefenum{ATOM,LIST}?ElemTag;
//ATOM==0:表示原子,LIST==1:表示子表
TypedefstructGLNode?{
ElemTag????tag;//公共部分于颖，用以區(qū)分原子部分和表結點
union{//原子部分和表結點的聯(lián)合部分
AtomType????atom;//原子結點的值域
structGLNode??*hp;//表結點的表頭指針
};
structGLNode????*tp;
//相當于線性鏈表的next章母，指向下一個元素結點
}?*Glist;//廣義表類型Glist?是一種擴展的線性鏈表
示例如圖：
