广义表

广义表（Generalized List，又称列表）是线性表的推广：元素既可以是原子（不可分的单元素），也可以是一个子表。因此它可以表达层次、共享甚至某些递归结构。

本文解决什么问题

• 广义表与普通线性表差在哪里
• 如何读括号表示、求长度与深度
• 和树、链表的概念联系
• 本教程中的定位（概念为主）

直观例子

LS = (a, (b, c), d)

• 长度为 3（顶层有三个元素）
• 第二个元素本身是子表 (b, c)
• 空表记为 ()

再如：

A = ()           长度 0，深度 1（空表深度按教材约定，常见为 1）
B = (e)          长度 1
C = (a, (b, c))  长度 2，深度 2

备注

不同教材对「空表深度」定义可能为 0 或 1。阅读时以当前教材为准。

和线性表、树的关系

结构	元素	关系
线性表	都是原子	一对一次序
广义表	原子或子表	可嵌套
树	结点 + 子树	也可用广义表表示某些树

广义表常用「表结点 + 原子结点」的链式结构存储，思想上接近「能指向子结构的链表」。若允许结点被多个地方指向，还能表示共享；若再有环，遍历时必须标记访问，否则死循环。

基本运算（了解）

运算	含义
head	取表头（第一个元素，可能是原子或子表）
tail	取表尾（去掉表头后剩下的表）
求长度	顶层元素个数
求深度	括号嵌套的最大层数
遍历 / 复制	注意共享与环

例：LS = (a, (b, c), d)

• head(LS) = a
• tail(LS) = ((b, c), d)

本教程中的定位

广义表在经典教材中占一席之地，但现代工程里更常直接使用：

• 树 / JSON / 嵌套容器
• vector 嵌套、异构结构用变体类型等

因此本篇以读懂概念与术语为目标，不展开完整存储代码。若你走考研或经典教材路线，可再对照严蔚敏等教材中的结点定义与头尾运算实现。

小结

广义表让「表中再套表」成为一等公民。先能读懂括号表示，分清长度与深度，再在需要时查阅具体存储实现。

下一章进入 树的基本概念。