介绍
广义表是线性表的 扩展，也叫“列表”，官方定义：
广义表是 n（n≥0）个元素的有限序列，每个元素既可以是 单个数据元素（原子），也可以是 另一个广义表（子表）。
类比
普通线性表（如数组 [1,2,3]）像“只有单层抽屉的柜子”，每个抽屉里只有具体物品；
广义表像“多层嵌套抽屉的柜子”，每个抽屉里可以放具体物品，也可以放另一个小柜子（子表）。
符号约定
- 用
()表示空广义表； - 用
(a1,a2,...,an)表示非空广义表，ai可以是原子（如数字、字符）或子表； - 通常用
LS表示广义表，head(LS)表示取表头，tail(LS)表示取表尾（核心操作）。
特性
层次性（最核心）
广义表是多层嵌套结构，有“深度”的概念：
- 原子的深度为 0；
- 空表的深度为 1；
- 非空广义表的深度 = 子表的最大深度 + 1。
示例：
A = ()→ 深度 1；B = (a, b)→ 原子构成，深度 1；C = (a, (b, c), d)→ 子表(b,c)深度 1，整体深度 2；D = ( ( (a) ), b )→ 子表((a))深度 2，整体深度 3。
共享性
多个广义表可以共享同一个子表（类似指针引用），比如：E = (a, b)，F = (E, c) → F 共享了 E 这个子表，而非复制。
递归性
广义表可以包含自身作为子表（递归表），比如：G = (a, G) → G 的第二个元素是它自己，深度为无穷大。
线性表是广义表的特例
当广义表的所有元素都是原子，且无嵌套时，就是普通线性表（数组、单链表）。
操作
表头（head）和表尾（tail）
这是广义表最常用的操作，必须牢记规则：
- 表头（head）：广义表的第一个元素（可以是原子或子表）；
- 表尾（tail）：广义表去掉表头后，剩余元素构成的新广义表（一定是表，哪怕只剩一个元素）。
示例
| 广义表 | 表头（head） | 表尾（tail） | 说明 |
|---|---|---|---|
(a, b, c) |
a（原子） |
(b, c)（子表） |
去掉表头a，剩余构成表 |
( (a, b), c ) |
(a, b)（子表） |
(c)（子表） |
表头是第一个子表，表尾是(c) |
(a) |
a（原子） |
()（空表） |
去掉唯一元素，剩余空表 |
() |
无 | 无 | 空表无表头/表尾 |
注意：表尾永远是“表”，不是单个元素！比如 (a,b,c) 的表尾不是 b，而是 (b,c)。
存储结构
广义表的嵌套特性决定了它 无法用数组存储，只能用链表
应用场景
- 数据结构表示：比如表示多维数组（
A = ( (1,2), (3,4) )对应二维数组）； - 表达式解析：比如数学表达式
3 + (4*5 - 6)可表示为(+, 3, (-, (*,4,5),6))； - 文档结构：比如XML/HTML的嵌套标签，本质是广义表结构；
- 人工智能：表示知识图谱、规则集等嵌套结构。
总结
- 广义表是线性表的扩展，元素可以是原子或子表，核心特性是嵌套（层次性）；
- 表头是第一个元素（原子/子表），表尾是剩余元素构成的新表（一定是表）；
- 存储必须用异构链表（区分原子/表节点），遍历依赖递归；
- 线性表是广义表的特例（无嵌套、全原子），广义表是线性表的通用形式。