DSA Mastery理论与实验教程

外观

第 3 章 · 字符串与数组

3.4 广义表与递归算法

递归定义的线性结构：广义表的表头表尾、头尾链表存储与求深度等递归算法。

约 5 分钟阅读更新于 2026-08-17Fishmandraft

大家好喵，我们今天来学习广义表。广义表是线性表的推广：线性表的每个元素只能是一个原子（不可再分的数据元素），广义表的元素既可以是原子，也可以是另一个广义表（子表）。这种"元素又可以是表"的性质让广义表天然具有递归结构，也正因如此，它的定义、存储和算法都围绕递归展开。

学习目标 ​

  • 掌握广义表的递归定义，区分原子与子表；
  • 理解表头、表尾、长度、深度等术语并正确计算；
  • 说明头尾链表存储与扩展线性链表存储的取舍；
  • 实现求深度等递归算法，体会"递归定义对应递归算法"。

递归定义 ​

广义表 LS 是 n≥0 个元素的有限序列：

LS=(a1,a2,…,an),

其中每个 ai 或者是原子，或者是广义表。n 称为广义表的长度；n=0 时为空表，记作 ()。

广义表说明
A = ()空表，长度 0
B = (e)长度 1，唯一元素是原子 e
C = (a, (b, c, d))长度 2，a 是原子，(b, c, d) 是子表
D = (A, B, C)长度 3，三个元素都是子表
E = (a, E)递归表，长度 2，含对自身的引用

广义表与线性表的区别

线性表的元素只能是原子；广义表的元素可以是子表，因此它能表示"表中套表"的层次结构，这是线性表做不到的。E = (a, E) 还说明广义表可以被共享和递归引用，从而表示更复杂甚至无限的结构。

表头与表尾 ​

对非空广义表 LS=(a1,a2,…,an)：

  • 表头（Head）：a1，可以是原子，也可以是子表。
  • 表尾（Tail）：去掉表头后剩余元素组成的表 (a2,…,an)，一定是一个表（可能是空表）。

以 C = (a, (b, c, d)) 为例：Head(C) = a（原子），Tail(C) = ((b, c, d))。注意表尾比直觉多一层括号：去掉表头后，剩下的元素仍要套在原来的表里。

长度与深度 ​

  • 长度：最外层元素的个数。
  • 深度：括号的重数，即元素的最大嵌套层数。约定空表的深度为 1，原子的深度为 0；非空表 LS=(a1,…,an) 的深度为：
depth(LS)=max1≤i≤ndepth(ai)+1.

例如 F = (a, (b, (c, d)))：最内层 (c, d) 深度为 1，(b, (c, d)) 深度为 2，最外层再加一层，故 depth(F) = 3。手工计算时数"从最外层到最内层经过了几层括号"即可。

存储结构：头尾链表 ​

广义表的元素既可能是原子又可能是子表，节点需要用**标志位（tag）**区分两种身份。头尾链表表示把每个子表拆成"表头 + 表尾"：

cpp
enum class Tag { Atom, List };

struct GLNode {
    Tag tag;                                    // 节点类型标志
    union {
        int atom;                               // tag == Atom：原子值
        struct { GLNode* hp; GLNode* tp; } sub; // tag == List：表头与表尾指针
    };
};
generalized-list.cpp

tag == List 的节点中，hp 指向表头元素，tp 指向表尾（仍是一个表）。空表用 nullptr 表示。于是 C = (a, (b, c, d)) 表示为：根是 List 节点，hp 指向原子 a，tp 指向子表 ((b, c, d))；后者又是一个 List 节点，hp 指向 (b, c, d)，tp 为空表。

存储结构：扩展线性链表 ​

头尾链表每次取表头都要"剥一层"，按位置访问第 i 个元素不方便。扩展线性链表给每个节点加一个 next 指针，让同一层的元素串成单链表：List 节点的 hp 指向第一个元素，元素之间用 next 相连。这样遍历同一层元素更直观，代价是节点结构多一个指针。

cpp
struct ExtNode {
    Tag tag;
    ExtNode* next;          // 同层下一个元素（原子或子表）
    union {
        int atom;           // tag == Atom
        ExtNode* hp;        // tag == List：指向第一个元素
    };
};
generalized-list-extended.cpp

两种表示都来自同一思路：用标志位统一原子与子表，用指针表示嵌套关系。头尾链表更贴近"表头/表尾"的递归定义，扩展线性链表更便于顺序遍历。

递归算法：求深度 ​

广义表的定义是递归的，算法也自然用递归写出。以求深度为例：

cpp
int depth(const GLNode* ls) {
    if (!ls) return 1;                       // 空表深度为 1
    if (ls->tag == Tag::Atom) return 0;      // 原子深度为 0
    int maxDepth = 0;
    for (const GLNode* p = ls; p; p = p->sub.tp) {
        maxDepth = std::max(maxDepth, depth(p->sub.hp));   // 各元素的深度
    }
    return maxDepth + 1;                     // 非空表深度 = 最大元素深度 + 1
}
generalized-list-depth.cpp

函数沿 tp 指针遍历同一层元素，对每个表头元素递归求深度，再取最大加一。递归的终止条件是"空表"或"原子"这两种不能再拆的情况，正好对应深度的边界约定。

同样的递归模式可推广到复制与判等：复制一个表等于复制表头加复制表尾；判断两表相等等于表头相等且表尾相等。

cpp
GLNode* copy(const GLNode* ls) {
    if (!ls) return nullptr;                 // 空表
    GLNode* node = new GLNode;
    node->tag = ls->tag;
    if (ls->tag == Tag::Atom) {
        node->atom = ls->atom;
    } else {
        node->sub.hp = copy(ls->sub.hp);     // 递归复制表头
        node->sub.tp = copy(ls->sub.tp);     // 递归复制表尾
    }
    return node;
}
generalized-list-copy.cpp

应用：m 元多项式 ​

广义表可以表示多元多项式。一个 m 元多项式可看作"变元 + 系数多项式"的递归结构：例如把 P(x,y,z) 视为关于 z 的一元多项式，其系数又是关于 y 的一元多项式，逐层分解下去，最终每一层都是"系数 + 指数"的线性表。这种一层套一层的结构，正是广义表的典型应用。

小结 ​

广义表的本质是"元素可以又是表"的递归线性结构。表头表尾、长度深度、头尾链表存储、递归算法，四者由同一条递归定义贯穿：定义怎么递归，存储就怎么用指针嵌套，算法就怎么递归实现。

练习 ​

  1. 设广义表 L = ((a, b), c, d)，分别写出它的表头与表尾；再写出 ((a)) 的表头与表尾。提示：表尾一定是表，注意它比直觉多一层括号。
  2. 求广义表 G = (a, (b, c), (d, (e))) 的长度与深度。
  3. 已知 A = ((x, y, z), (a, b, c, d))，写出用 Head 与 Tail 操作取出原子 b 的运算式。
  4. 仿照文中 depth 的递归定义，手算广义表 (a, (b), (c, (d, e))) 的深度，并指出递归在何处终止。