建议先阅读: 链表 — 广义表是线性表的推广,通常用链式结构存储,“表头/表尾”的递归定义与链表的头尾操作一脉相承。

广义表(Generalized List)是线性表的推广:线性表的元素只能是原子,而广义表的元素既可以是原子,也可以是另一个广义表(子表)。这个”元素可以是表”的递归定义,使它成为 Lisp 的 S-表达式、树/森林的孩子兄弟表示、嵌套结构的统一模型。


原理

什么是广义表

定义:广义表是 ()个元素 的有限序列,记作

其中每个 要么是原子(不可再分的单元素),要么是子表(另一个广义表)。 时称为空表,记作 ()。

概念含义例()
原子不可再分的元素a、b、c、d
子表作为元素的广义表(b,c)
表头 Head第一个元素(原子或子表)Head(LS)=a
表尾 Tail去掉表头后剩余元素组成的广义表Tail(LS)=((b,c),d)
长度 Length最外层元素的个数Length(LS)=3
深度 Depth括号嵌套的最大层数Depth(LS)=2

注意:表尾一定是广义表(一定带括号,可以是空表 ());表头是”第一个元素”,可能是原子,也可能是子表。例如 Tail((a)) = (),Tail((a,b)) = (b)。

广义表的两个基本运算:Head 与 Tail

这两个运算只动”最外层”,是嵌套提取的全部基础:

  • Head(LS):取第一个元素。空表没有表头,非法。
  • Tail(LS):去掉第一个元素,剩余元素仍组成一个广义表(带括号)。空表没有表尾,非法;单元素表的表尾是空表 ()。

嵌套提取要由内向外逐层算。以 为例:

表达式结果说明
Head(A)a第一个元素是原子
Tail(A)(b,(c,d),e)去掉 a,剩余仍是表
Head(Tail(A))b表尾的第一个元素
Tail(Tail(A))((c,d),e)再去掉 b
Head(Tail(Tail(A)))(c,d)第三个元素是子表
Tail(Head(Tail(Tail(A))))(d)子表去掉 c
Head(Tail(Head(Tail(Tail(A)))))d最终取出 d
Tail(Head(Tail(Tail(A)))) 再 Tail()(d) 去掉 d 得空表

手算口诀:从最内层括号开始,一层层把 Head/Tail 换成具体结果;Tail 的结果永远保留括号。

长度与深度

  • 长度:最外层元素的个数,只数”逗号分隔的项”,不往括号里数。Length((a,(b,c),d))=3,Length(())=0,Length((a))=1。
  • 深度:括号嵌套的最大层数。约定 原子深度为 0,空表深度为 1,非空表深度为
广义表长度深度
()01
(a)11
(a,b,c)31
(a,(b,c))22
((a,b),c,d)32
((a,(b,c)),d)23

长度看”最外层有几项”,深度看”最多套了几层括号”。二者不要混。

递归表

若广义表包含自身,则称为递归表。例如

它的展开是 ,括号可以无限套下去,因此递归表的深度为无穷大 。同理,若通过子表间接包含自身(如 ),深度也为 。

考点:普通广义表的深度是有限整数;只要出现”自己包含自己”(直接或间接),深度就是 。实现求深度时必须检测环,否则会无限递归。

广义表的存储结构

广义表不能用简单的顺序结构存储——因为元素可以是子表,长度和嵌套层数都不固定,顺序存储难以表达”表中套表”。教材给出两种链式结构,都用 tag 区分原子/子表:

(1)头尾链表存储结构(最经典)

typedef enum { ATOM, LIST } ElemTag;
 
typedef struct GLNode {
    ElemTag tag;              /* ATOM:原子;LIST:子表 */
    union {
        char atom;            /* tag == ATOM:原子值 */
        struct GLNode *hp;    /* tag == LIST:指向子表的第一个结点 */
    } ptr;
    struct GLNode *tp;        /* 指向同层的下一个元素 */
} GLNode, *GList;
  • 整个广义表是一条由 tp 串起来的链;
  • 原子结点用 ptr.atom 存值;子表结点用 ptr.hp 指向子表内部的第一条链;
  • 空表用 NULL 表示;空子表 () 是一个 LIST 结点且 hp == NULL。
graph LR
  A["a | tp"] --> B["LIST | hp | tp"] --> C["e | tp"] --> N["NULL"]
  B -.hp.-> D["b | tp"] --> E["c | tp"] --> N2["NULL"]

(2)扩展线性链表(同层链)存储结构

原子结点存 data + next;子表结点存 hp + next。它把”同层元素”和”子表入口”分开表示,本质与头尾链相同,只是结点字段组织不同(类似树的孩子兄弟表示法)。考试若只问”广义表适合什么存储结构”,答**链式存储(头尾链表 / 同层链)**即可。


实现

下面用头尾链表示给出核心操作的 C 实现(原子用 char 演示)。

求长度

int GLLength(GList L) {
    int n = 0;
    for (GList p = L; p != NULL; p = p->tp)   /* 只数最外层 */
        n++;
    return n;
}

求深度

int GLDepth(GList L) {
    if (L == NULL) return 1;                  /* 空表深度为 1 */
    int maxd = 0;
    for (GList p = L; p != NULL; p = p->tp) {
        int d = (p->tag == ATOM) ? 0 : GLDepth(p->ptr.hp);
        if (d > maxd) maxd = d;
    }
    return maxd + 1;                          /* 非空表 = 1 + 子项最大深度 */
}

递归表(如 L=(a,L))会让上面的函数无限递归。工程实现要带一个 visited 集合检测环;一旦检测到环,直接返回 的标记。

取表头 / 表尾

/* 取表头:返回第一个元素结点(原子或子表);空表返回 NULL */
GList GLHead(GList L) {
    return L;                                 /* 第一个结点就是表头 */
}
 
/* 取表尾:返回去掉首元素后的链;空表返回 NULL */
GList GLTail(GList L) {
    return (L == NULL) ? NULL : L->tp;
}

调用者根据返回结点的 tag 判断是原子还是子表:ATOM 读 ptr.atom,LIST 读 ptr.hp。注意 Tail 返回的仍是一条链,它对应的广义表隐含外层括号。

从括号串递归建表

/* s 指向 '(' 之后;返回建好的表;结束时 *s 停在 ')' */
GList GLCreate(char **s) {
    GList head = NULL, tail = NULL;
    while (**s != '\0' && **s != ')') {
        GLNode *node = malloc(sizeof(GLNode));
        if (**s == '(') {
            node->tag = LIST;
            (*s)++;
            node->ptr.hp = GLCreate(s);       /* 递归建子表 */
            if (**s == ')') (*s)++;
        } else {
            node->tag = ATOM;
            node->ptr.atom = **s;
            (*s)++;
        }
        node->tp = NULL;
        if (head == NULL) head = node;
        else tail->tp = node;
        tail = node;
        if (**s == ',') (*s)++;
    }
    return head;
}

销毁

void GLDestroy(GList L) {
    while (L != NULL) {
        GList next = L->tp;
        if (L->tag == LIST) GLDestroy(L->ptr.hp);  /* 先递归销毁子表 */
        free(L);
        L = next;
    }
}

高频考点(含典型题)

先给概念考点速记,再给典型题——考点在上、题目在下。广义表不在 408 统考大纲内,但期末、自命题、教材习题必考,下面按考试题型整理。

概念考点速记

1. Head / Tail 的定义与边界

运算结果空表单元素表
Head(LS)第一个元素(原子或子表)非法(无表头)该元素
Tail(LS)去掉表头后的广义表(带括号)非法(无表尾)() 空表
  • Tail 的结果一定是广义表,可能为空表;
  • Head 的结果可能是原子,也可能是子表;
  • 嵌套提取从最内层开始算,Tail 的结果始终带括号。

2. 长度与深度

  • 长度 = 最外层元素个数(只数逗号分隔的项),空表长度 0;
  • 深度 = 括号最大嵌套层数;原子深度 0,空表深度 1,非空表深度 子项深度;
  • 递归表(直接或间接包含自身)深度为 。
广义表长度深度
()01
(a,b,c)31
(a,(b,c))22
((a,b),c,d)32
((a,(b,c)),d)23
L=(a,L)2

3. 结构特性辨析

  • 广义表是线性表的推广:线性表的元素只能是原子,广义表的元素还可以是表;
  • 表尾一定是广义表(可以是空表),表头不一定是广义表(可能是原子);
  • “表头不能是空表”这类绝对化说法要结合定义:若第一个元素本身就是空子表 (),Head 的结果就是 ();考试以教材定义为准;
  • 广义表不适合简单顺序存储:元素长度不一、嵌套层数不定,需要链式结构;
  • 广义表可以共享子表(同一子表被多个表引用),形成**有向无环图(DAG)**结构。

4. 存储结构

结构结点特点
头尾链表tag + (atom / hp) + tp最经典,hp 指向子表、tp 指向同层下一个
扩展线性链表(同层链)原子:data + next;子表:hp + next与孩子兄弟表示法同构
顺序存储难以表达嵌套只适合极简单的定长情形

典型题索引

题目考点本题解位置
求 Head / Tail 嵌套提取Head/Tail 逐层拆解典型题 1:嵌套 Head/Tail
求长度与深度长度/深度定义典型题 2:长度与深度
递归表的深度递归表典型题 3:递归表的深度
表头/表尾辨析结构特性典型题 4:表头与表尾辨析

典型题 1:嵌套 Head/Tail

题目:已知 ,求 Head(Tail(Head(Tail(Tail(A)))))。

解析:由内向外:

  1. Tail(A) = (b,(c,d),e)
  2. Tail(Tail(A)) = ((c,d),e)
  3. Head(Tail(Tail(A))) = (c,d)
  4. Tail(Head(Tail(Tail(A)))) = (d)
  5. Head(Tail(Head(Tail(Tail(A))))) = d

答案:d。若再求一次 Tail,得到 ()。

典型题 2:长度与深度

题目:求 与 的长度和深度。

解析:

  • :最外层有 3 项 (a,b)、c、d,长度 3;最深括号是内层 (a,b),共 2 层,深度 2。
  • :最外层有 2 项 a、(b,(c,d)),长度 2;嵌套为 a(0 层)、(b,(c,d))(1 层)、(c,d)(2 层),最深 3 层,深度 3。

答案: 长度 3、深度 2; 长度 2、深度 3。

典型题 3:递归表的深度

题目:广义表 的深度是多少?

解析: 包含自身,展开为 ,括号可以无限嵌套,故深度为 。实现求深度时必须检测环,否则无限递归。

答案:。

典型题 4:表头与表尾辨析

题目:判断下列说法:
① Tail((a,b,c)) = (b,c);
② Head((a,b,c)) = a;
③ Tail((a)) = ();
④ Head(()) 合法。

解析:①②③ 正确。④ 错误:空表没有表头,Head(()) 非法(同理 Tail(()) 也非法)。

答案:①②③ 正确,④ 错误。


扩展

广义表与 Lisp / S-表达式

Lisp 的代码和数据都用 S-表达式表示,而 S-表达式就是广义表:原子是符号/数字,子表是括号包起来的列表。(defun square (x) (* x x)) 本身就是一个广义表。car 对应 Head(取第一个元素),cdr 对应 Tail(取剩余部分)——广义表的两个基本运算正是 Lisp 的基石。

广义表与树、森林的孩子兄弟表示

孩子兄弟表示法把一棵多叉树变成二叉树:firstChild 指向第一个孩子,nextSibling 指向同层下一个兄弟。这与广义表的”头尾链”完全同构:

广义表树/森林
子表 hp第一个孩子 firstChild
同层 tp下一个兄弟 nextSibling
原子叶子/结点数据

因此,广义表可以表示树和森林,树的先根遍历对应广义表的深度优先展开。

共享子表与 DAG

广义表允许子表被多个表共享。例如 、 共享同一个 。若把共享子表画成结点,整个结构就是一个**有向无环图(DAG)**而非树——这也是广义表比普通树更一般的地方。实现时要小心:销毁时不能重复释放共享子表(需要引用计数或不做深销毁)。


各语言标准库对比

语言广义表/嵌套列表表示说明
Lisp / Scheme原生 S-表达式car/cdr 即 Head/Tail
Python嵌套 listlst[0] 近似 Head,lst[1:] 近似 Tail
JavaScript嵌套 Array同理,但要注意浅拷贝
C手写 GLNode头尾链 / 同层链,最能看清指针
JavaList<Object> 嵌套用 Object 兼容原子与子表
Rustenum GL { Atom(T), List(Vec<GL>) }枚举天然表达”原子或子表”

Python/JS 的嵌套列表是广义表最直观的”高层等价物”;C 的头尾链则展示了它真正的指针结构。


应用场景

  • Lisp / Scheme 的代码与数据:S-表达式即广义表;
  • 树与森林的存储:孩子兄弟表示法与广义表同构;
  • 嵌套配置/文档结构:JSON、XML 的嵌套对象可看作广义表;
  • 符号计算:计算机代数系统用嵌套表表示表达式;
  • 编译器的抽象语法树(AST):本质是带标签的广义表;
  • 共享子结构的建模:DAG、表达式共享。

练习

核心推演清单

题目考点答案
,求 Head(A)、Tail(A)Head/Taila、((b,c),d)
,求长度、深度长度/深度3、2
,求 Head(Tail(Head(Tail(Tail(A)))))嵌套提取d
的深度递归表
Tail((a))边界()
Head(()) 是否合法边界非法

LeetCode / 练习题

题号题目说明
341扁平化嵌套列表迭代器嵌套列表的遍历(广义表的展开)
385迷你语法分析器从括号串递归建广义表
339嵌套列表加权和(会员)递归求深度加权
364嵌套列表加权和 II(会员)自底向上递归

动手实验

编号题目说明
E1头尾链建表与打印实现 GLCreate,把 (a,(b,c),d) 建成头尾链,再递归打印回原串,验证括号与逗号正确
E2长度/深度/Head/Tail对 E1 的表实现 GLLength、GLDepth、GLHead、GLTail,并验证典型题 1、2 的结果
E3递归表检测构造 L=(a,L)(让 tp 或 hp 指回自身),给 GLDepth 加 visited 检测,验证返回 而不是栈溢出
E4广义表转树把 (a,(b,c),d) 按”孩子兄弟”规则转成二叉树,比较先根遍历与广义表深度优先展开的顺序