软考-软件设计师：数据结构-线性结构-线性表-广义表 作者：马育民 • 2026-02-09 20:58 • 阅读：10001 # 介绍 广义表是线性表的 **扩展**，也叫“列表”，官方定义： 广义表是 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)`。 # 存储结构 广义表的嵌套特性决定了它 **无法用数组存储**，只能用**链表** # 应用场景 1. **数据结构表示**：比如表示多维数组（`A = ( (1,2), (3,4) )` 对应二维数组）； 2. **表达式解析**：比如数学表达式 `3 + (4*5 - 6)` 可表示为 `(+, 3, (-, (*,4,5),6))`； 3. **文档结构**：比如XML/HTML的嵌套标签，本质是广义表结构； 4. **人工智能**：表示知识图谱、规则集等嵌套结构。 # 总结 1. 广义表是线性表的扩展，元素可以是原子或子表，核心特性是**嵌套（层次性）**； 2. 表头是第一个元素（原子/子表），表尾是剩余元素构成的新表（一定是表）； 3. 存储必须用异构链表（区分原子/表节点），遍历依赖递归； 4. 线性表是广义表的特例（无嵌套、全原子），广义表是线性表的通用形式。 原文出处：http://www.malaoshi.top/show_1GW2kRTTxKBz.html