广义表存储结构图 - 宇佐见函钩

📚 什么是广义表？

广义表（Generalized List）是线性表的推广，是一种递归的数据结构。

原子（Atom）：不可再分的元素，如字母、数字
子表（Sublist）：作为元素的广义表，可以嵌套

例如：

A = () — 空表
B = (a, b, c) — 只含原子
C = (a, (b, c), d) — 含子表
D = ((a, b), (c, (d, e))) — 多层嵌套

🔧 方式一：头尾链表法

原子节点和表节点结构相同，都有 tp 指针：

原子节点 (tag=0)

tag=0

atom

tp

表节点 (tag=1)

tag=1

hp

tp

字段	说明
tag	标志位：0表示原子，1表示子表
atom	原子节点存放的数据值
hp	表头指针，指向子表的第一个元素
tp	表尾指针，指向同级的下一个元素

🔧 方式二：扩展线性链表法

原子节点没有 tp 指针，结构更紧凑：

原子节点 (tag=0)

tag=0

atom

表节点 (tag=1)

tag=1

hp

tp

特点	说明
原子节点	只有 tag 和 atom 两个字段，没有 tp
表节点	有 tag、hp、tp 三个字段（与方式一相同）
连接方式	原子直接挂在表节点的 hp 下，同级元素通过表节点的 tp 连接
优点	节省原子节点的空间，每个原子少存一个指针

📝 画图规则

Step 1: 识别结构

从左到右扫描广义表，遇到 ( 创建表节点，遇到字母创建原子节点。

Step 2: 连接 hp（表头）

表节点的 hp 指向该括号内的第一个元素（向下指）。

Step 3: 连接 tp（表尾）

同级元素之间用 tp 串联（向右指）。最后一个元素的 tp 为 ∧（空）。

Step 4: 递归处理子表

如果元素是子表，对其递归应用以上规则。

💻 C语言结构定义

方式一：头尾链表法

typedef struct GLNode {
    int tag;           // 0: 原子, 1: 子表
    union {
        char atom;      // 原子值
        struct GLNode *hp; // 表头指针
    };
    struct GLNode *tp;  // 表尾指针
} GLNode, *GList;
                    

方式二：扩展线性链表法

typedef struct GLNode {
    int tag;           // 0: 原子, 1: 子表
    union {
        char atom;      // tag=0: 原子值
        struct {        // tag=1: 表节点
            struct GLNode *hp; // 表头指针
            struct GLNode *tp; // 表尾指针
        } ptr;
    };
} GLNode, *GList;
                    

📊 广义表存储结构图