C++广义表实现方法详解（从零开始掌握广义表数据结构）

什么是广义表？

广义表可以递归地定义为：

• 空表：() —— 表示一个没有元素的广义表。
• 非空表：(a₁, a₂, ..., aₙ)，其中每个 aᵢ 要么是一个原子（不可再分的数据项），要么是一个子表（另一个广义表）。

例如：(1, (2, 3), 4) 就是一个广义表，其中包含原子 1 和 4，以及子表 (2, 3)。

C++中如何表示广义表？

由于广义表具有递归和嵌套的特性，我们通常使用链式结构来实现。每个节点需要能区分是原子还是子表，因此我们可以设计一个联合体（union）或使用继承。这里我们采用更清晰的方式：使用一个结构体，包含一个类型标记和两个指针。

节点结构设计

我们定义一个 GLNode 结构体，它包含以下字段：

• tag：标记当前节点是原子（0）还是子表（1）。
• atom：如果 tag=0，存储原子值（如 int）。
• hp：如果 tag=1，指向子表的头指针（head pointer）。
• tp：指向下一个兄弟节点（tail pointer）。

C++代码实现

下面是一个完整的 C++ 广义表实现示例，包括节点定义、创建、打印等功能：

#include <iostream>#include <string>using namespace std;// 节点类型标记enum ElemTag { ATOM, LIST };// 广义表节点结构struct GLNode {    ElemTag tag;          // 标记：ATOM 或 LIST    union {        char atom;        // 原子值（这里以字符为例）        GLNode* hp;       // 指向子表的指针    };    GLNode* tp;           // 指向下一个元素（兄弟）    // 构造函数    GLNode(ElemTag t) : tag(t), tp(nullptr) {}};// 创建原子节点GLNode* createAtom(char c) {    GLNode* node = new GLNode(ATOM);    node->atom = c;    return node;}// 打印广义表（递归）void printGL(GLNode* L) {    if (L == nullptr) return;    if (L->tag == ATOM) {        cout << L->atom;    } else {        cout << "(";        printGL(L->hp);  // 打印子表        cout << ")";    }    if (L->tp != nullptr) {        cout << ", ";        printGL(L->tp);  // 打印兄弟节点    }}// 示例：构建广义表 (a, (b, c), d)GLNode* buildExampleList() {    // 构建原子节点    GLNode* a = createAtom('a');    GLNode* b = createAtom('b');    GLNode* c = createAtom('c');    GLNode* d = createAtom('d');    // 构建子表 (b, c)    b->tp = c;    GLNode* sublist = new GLNode(LIST);    sublist->hp = b;    // 构建主表 (a, sublist, d)    a->tp = sublist;    sublist->tp = d;    GLNode* head = new GLNode(LIST);    head->hp = a;    return head;}int main() {    GLNode* L = buildExampleList();    cout << "广义表内容: ";    printGL(L->hp);  // 注意：L 是表头节点，实际内容在 hp    cout << endl;    return 0;}

关键知识点解析

1. 递归结构

广义表的核心在于其递归定义。每个子表本身也是一个广义表，因此在实现时大量使用递归函数（如打印、深度计算、复制等）。

2. 联合体（union）的使用

由于一个节点不能同时是原子和子表，我们使用 union 来节省内存。这是 C++ 中处理“互斥数据类型”的经典技巧。

3. 表头节点设计

为了统一操作，我们通常为每个广义表设置一个表头节点（tag=LIST），其 hp 指向第一个元素。这样无论表是否为空，接口都保持一致。

应用场景

掌握 C++广义表实现 对理解高级数据结构至关重要。它广泛应用于：

• 编译器设计（语法树）
• 人工智能（知识表示）
• 符号计算系统
• Lisp 等函数式语言的底层实现

总结

通过本教程，你已经学会了如何用 C++ 实现一个基本的广义表结构。重点在于理解其递归本质和链式存储方式。虽然标准库中没有直接提供广义表，但掌握这一结构有助于提升你的广义表编程教程能力，特别是在处理嵌套数据时。

建议你动手修改上述代码，尝试添加“计算深度”、“判断相等”、“复制广义表”等功能，以加深对 广义表数据结构 和 C++递归结构 的理解。

提示：实际项目中可根据需求将原子类型改为模板（template），以支持任意类型的数据。