廣義表定義
廣義表是n(n≥0)個元素a，a，…，a，…，a的有限序列。
其中：
①a--或者是原子或者是一個廣義表。
②廣義表通常記作：
Ls=( a，a，…，a，…，a)。
③Ls是廣義表的名字，n為它的長度。
④若a是廣義表，則稱它為Ls的子表。
注意：
①廣義表通常用圓括弧括起來，用逗號分隔其中的元素。
②為了區分原子和廣義表，書寫時用大寫字母表示廣義表，用小寫字母表示原子。
③若廣義表Ls非空(n≥1)，則a是Ls的表頭，其餘元素組成的表(a2，a3，…，a)稱為Ls的表尾。
④廣義表是遞歸定義的
廣義表表示
（1）廣義表常用表示
① E=()
E是一個空表，其長度為0。
② L=(a，b)
L是長度為2的廣義表，它的兩個元素都是原子，因此它是一個線性表
③ A=(x，L)=(x，(a，b))
A是長度為2的廣義表，第一個元素是原子x，第二個元素是子表L。
④ B=(A，y)=((x，(a，b))，y)
B是長度為2的廣義表，第一個元素是子表A，第二個元素是原子y。
⑤ C=(A，B)=((x，(a，b))，((x，(a，b))，y))
C的長度為2，兩個元素都是子表。
⑥ D=(a，D)=(a，(a，(a，(…))))
D的長度為2，第一個元素是原子，第二個元素是D自身，展開後它是一個無限的廣義表。
（2）廣義表的深度
一個表的"深度"是指表展開後所含括弧的層數。
【例】表L、A、B、C的深度為分別為1、2、3、4，表D的深度為∞。
（3）帶名字的廣義表表示
如果規定任何表都是有名字的，為了既表明每個表的名字，又說明它的組成，則可以在每個表的前面冠以該表的名字，於是上例中的各表又可以寫成：
①E()
②L(a，b)
③A(x，L(a，b))
④B(A(x，L(a，b))，y)
⑤C(A(x，l(a，b))，B(A(x，L(a，b))，y))
⑥D(a，D(a，D(…)))
廣義表運算
頭尾鍊表存儲結構
typedef enum {ATOM, LIST} ElemTag; /* ATOM=0，表示原子；LIST=1，表示子表*/
typedef struct GLNode
{
ElemTag tag; /*標誌位tag用來區別原子結點和表結點*/
union
{
AtomType atom; /*原子結點的值域atom*/
struct { struct GLNode * hp, *tp;} htp; /*表結點的指針域htp， 包括
表頭指針域hp和表尾指針域tp*/
} atom_htp; /* atom_htp 是原子結點的值域atom和
表結點的指針域htp的聯合體域*/
} *GList；
擴展線性存儲
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode
{ELemTag tag;
union
{AtomType atom;
struct GLNode *hp;
}
struct GLNode *ht;
}*GList;
