广义表(Lists，又称列表)是一种非连续性的数据结构，是线性表的一种推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。它被广泛的应用于人工智能等领域的表处理语言LISP语言中。在LISP语言中，广义表是一种最基本的来自数据结构，就连LISP 语言的程序也表示为一系列的广义表。
广义表是n(n≥0)个元素a1，a2，…，ai，…，an的有限序列。
其中:
①ai--或者是原子或者是一个广义表。
②广义表通常记作:
来自 Ls=( a1，a2，…，ai，…，an)。
③Ls是广义表的名字，n为360百科它的长度。
④若ai是广义表，则称它为Ls的子表。
注意:
①广义表通常用圆括号括起来，用逗号分隔其中的元素。
②为了区分原子和广义表，书各件写时用大写字母表示广义表，用小写字母表示原子督烧移准策孩整变。
③若广义表Ls非空(间n≥1)，则al是Ls的表头，其余元素组成的表(a2，a3，…，an)称为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(…)))
来自由于广义表是对线性表和树的推广，并且具有共享和递归特性的广义表可以和有向图建立对应，因此广义表的大部分运算与这些数据结构上的运算类似。
在此，只讨景敌实空措促专假界论广义表的两个特殊的基本运算:取表头head(L360百科s)和取表尾tail(L旧阻容队双进独零觉且难s)。
根据表头、表尾的定义可知:任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。
【例】
head(L)=a， tail(L)=(b)
head(B)=行续于施A， tail(B)=(y)
响打好报 由于tail(L)是非空表，可继续分解得到:
head(tail(L))=b， tail(tail(L))=()
对非空表A和(y)，也可继续分解。
注意:广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算;而后者是长度为l的非空表(只不过该表中唯一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()四。
头尾链表存储结构
typedef enum {ATOM, LIST} ElemTag; /* ATOM=0，表示原子;LIST=1，表示子表*/
typedef struct GLN装伯苗原ode
{
ElemTag tag; /*标志位ta已分再料品员使g用来区别原子结点和表结点*/
union
{
AtomType atom; /*原子结点的值远湖无稳优域atom*/
struct { struct GLNod位衣住南翻e * hp, *tp;} htp; /*表结点的指针域htp， 至互条待独粒食雷包括
表头指针域hp和表尾指针域tp*/
} atom_htp; /* atom_htp 是原子结点的值域atom和
表结点的指针域htp的联合体域*/
} *GList;
扩展线事钱性存储
typede语f enum {ATOM并响里脱,LIST} ElemTag;
typedef struct GLNode
{ELemTag 超还步倍南善福曲乡tag;
union
{AtomType atom;
struct GLNode *hp;
}
struct GLNod分免给乡服e *ht;
}*GList;
关注微信