文章目录
广义表的概念广义表的特性广义表的表头和表尾广义表的链接存储表示头尾表示法扩展线性链表表示法
广义表的概念
广义表的定义：广义表是
n
(
n
≥
0
)
n\ (n≥0)
n (n≥0) 个表元素组成的有限序列。
广义表的表示：
L
=
{
e
1
,
e
2
,
.
.
.
,
e
n
}
L=\{e_1,\ e_2,...,\ e_n\}
L={e1, e2,..., en}，其中
L
L
L为表名
e
i
e_i
ei是表元素
n
n
n是表长，
n
=
0
n=0
n=0是空表，
n
≠
0
n≠0
n=0是非空表“(” 和 ")"是表的分界符，不计入表的长度
广义表的表元素可以是不可再分的原子，还可以是广义表，称为广义表的子表。
广义表的特性
有次序：广义表的表元素的排列次序不能随意交换有层次：广义表的表元素可以是子表，子表还可以有子表有深度：最大嵌套层数即为广义表的深度，用括号重数来识别可共享：广义表的子表可为多个广义表的子表可递归：广义表的子表可以是自身
广义表的表头和表尾
广义表的表头：广义表的第一个表元素即为广义表的表头，它可以是原子，也可以是子表。广义表的表尾：除第一个元素外的其他元素组成的表为广义表的表尾，它一定是广义表。
广义表的链接存储表示
广义表的表元素都是原子时退化为线性表，它的连接存储表示为单链表。
一般情况下，广义表的链接存储表示是双链表。
头尾表示法
双链表有两种结点：
表结点：代表广义表或子表，它的
h
l
i
n
k
hlink
hlink指针指向表头，
t
l
i
n
k
tlink
tlink指向表尾，这是一种分支结点。原子结点：用于存储数据，指向它的指针是
h
l
i
n
k
hlink
hlink，它是链尾的表结点，省去了收尾指针。
特别的，空表没有结点，指向它的指针为NULL。
例如，对于广义表
L
=
(
c
,
(
d
,
e
,
f
)
,
(
)
)
L=(c,(d,e,f),())
L=(c,(d,e,f),())，它的头尾存储表示如下：
扩展线性链表表示法
这种表示法不分表头和表尾。
双链表有两种结点：
表结点：它的
h
l
i
n
k
hlink
hlink指针指向该表的第一个表元素结点，
t
l
i
n
k
tlink
tlink指针指向同一层下一个表元素结点。特别的，空表的
h
l
i
n
k
hlink
hlink和
t
l
i
n
k
tlink
tlink指针都为NULL。原子结点：用于存储数据，有
t
l
i
n
k
tlink
tlink指针，指向同一层下一个表元素结点。
例如，对于广义表
L
=
(
c
,
(
d
,
e
,
f
)
,
(
)
)
L=(c,(d,e,f),())
L=(c,(d,e,f),())，它的扩展线性链表存储表示如下：