什么是广义表

广义表是一种非线性的数据结构，它的表元素可以是原子或者广义表的一种线性表的扩展结构。

• 广义表的长度：为表中最上层元素的个数
• 广义表的深度：为表中括号的最大层数
• 表头和表尾：当广义表非空时，第一个元素为广义表的表头，其余元素组成的表是广义表的表尾

---

广义表的常用表示

① E=()
E是一个空表，其长度为0，其深度为1

② L=(a，b)
L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表，其深度为1

③ A=(x，L)=(x，(a，b))
A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L，其深度为2

④ B=(A，y)=((x，(a，b))，y)
B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y，其深度为3

⑤ C=(A，B)=((x，(a，b))，((x，(a，b))，y))
C的长度为2，两个元素都是子表，其深度为4

⑥ D=(a，D)=(a，(a，(a，(…))))
D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表，其深度为∞

注意：

1. 广义表通常用圆括号括起来，用逗号分隔其中的元素。
2. 为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。

---

广义表的存储结构

1. 头尾链表存储结构

表结点

链表结点

头尾链表存储表示

2. 扩展线性链表存储结构

表结点

原子结点

原子结点的表尾指针是指向下一个元素

扩展线性链表存储表示