第17章 高级数据表示：链表与二叉树

Note

这一章是全书从”会写 C 语句”迈向”会做程序设计”的分水岭。前面学的是工具（变量、结构、函数、指针），本章学的是设计：如何为问题选择合适的数据表示（data representation），并用抽象数据类型（ADT, Abstract Data Type）方法把”数据怎么存”和”程序怎么用”分开。链表（linked list）、队列（queue）、二叉搜索树（binary search tree）是本章三大主角。

17.1 探索数据表示：先想清楚，再动手写

程序开发中最重要的环节常常不是写代码，而是为数据找到合适的表示。选表示方式要同时回答两个问题：数据怎么存？允许哪些操作？C 为内置类型定义了合法操作（int 能加减乘除，指针却不能相乘），而自定义类型的操作要靠你自己编写函数来定义。

以”记录一年看过的电影”为例，最直觉的方案是 struct film { char title[TSIZE]; int rating; }; 加一个 struct film movies[FMAX]; 结构数组（原书 films1.c）。三个硬伤：浪费空间（片名按最长 45 字节预留）；数量死板（FMAX 编译期锁死，设大浪费、设小装不下）；即使改用 malloc() 按用户输入一次性分配动态数组，也只是把”猜数量”的责任推给用户。根源是：许多决策本该推迟到运行时，却在编译期锁死了。

17.2 从数组到链表：一次 malloc 一块，串起来

理想方案是每录入一部电影就 malloc() 一个结构的空间。但连续多次 malloc() 的内存不保证相邻——数组只需记一个首地址，分散的 300 块内存岂不是要记 300 个指针？链表用漂亮的一招解决：让每个结构自带一个指向”下一个同类型结构”的指针。

struct film {
    char title[TSIZE];
    int  rating;
    struct film * next;      /* 指向下一个 film 结构 */
};

结构不能包含自身类型的成员（大小无法计算），但可以包含指向自身类型的指针——指针大小固定，这正是链表的合法基石。链表三要素：

• 节点（node）：链表中的每个结构，含数据 + 下一节点指针；
• 头指针（head pointer）：单独保管的指针，指向第一个节点——链表里没有任何节点知道”第一个节点在哪”；
• NULL 收尾：末节点的 next 置 NULL，表示”后面没有了”。

17.3 使用链表：创建、遍历、释放三步走

完整的链表版电影程序（原书清单 17.2，films2.c）：

/* films2.c -- 用结构链表存放电影信息（节选） */
struct film { char title[TSIZE]; int rating; struct film * next; };
 
int main(void)
{
    struct film * head = NULL, * prev, * current;
    char input[TSIZE];
    /* 建表：每输入一部电影就挂一个节点 */
    while (gets(input) != NULL && input[0] != '\0')
    {
        current = (struct film *) malloc(sizeof(struct film));
        if (head == NULL)            /* 第一个结构 */
            head = current;
        else                         /* 后续结构 */
            prev->next = current;
        current->next = NULL;        /* 暂时是最后一个 */
        strcpy(current->title, input);
        scanf("%d", &current->rating);
        prev = current;              /* 为下一轮做准备 */
    }
    /* 遍历显示 */
    current = head;
    while (current != NULL)
    {
        printf("Movie: %s Rating: %d\n", current->title, current->rating);
        current = current->next;
    }
    /* 释放内存：先存"下一站"地址再 free，详见下文 EmptyTheList() */
    return 0;
}

遍历：current = head 从头出发，打印后 current = current->next 跳到下一个；current 变 NULL 即到达表尾。为什么用 current 而不直接移动 head？head 一旦被改写，程序就再也找不到链表开头了。创建：每轮 malloc() 分配 → 存地址（第一个存进 head，之后存进上一节点的 next）→ 填数据、next 置 NULL；循环末尾 prev = current 让 prev 在下一轮指向”上一个节点”，prev->next = current 才能接上链条。释放：遍历同时逐个 free()，注意必须先保存”下一站”地址再释放。

Warning

films2.c 没有检查 malloc() 的返回值。内存不足时 malloc() 返回 NULL，随后对 current->next 赋值就是解引用空指针，程序直接崩溃。每次 malloc() 之后都必须判空。另外示例中的 gets() 无法限制读入长度，本身就是危险函数，现代代码应用 fgets()。

17.4 抽象数据类型（ADT）：把”做什么”和”怎么做”分开

films2.c 能用，却把 malloc()、prev->next 这些底层细节和”往列表加一部电影”这个概念搅在一起。计算机科学的三步法：先抽象描述类型（不绑定任何实现与语言，即 ADT）；再设计编程接口（C 中典型做法是头文件：类型定义 + 函数原型）；最后实现接口（.c 文件），使用者无需知道实现细节。一个类型的本质 = 属性集合 + 操作集合——数学上的”整数”是抽象概念，C 的 int 只是不完美的一种实现（2 字节 int 只能表示 65536 个整数）。

17.4.1 简单列表 ADT 与接口：list.h

电影项目需要的”简单列表（simple list）“ADT：属性是”能容纳一列按顺序排列的项”；操作包括初始化为空、判空、判满、统计项数、末尾添加项、遍历（对每项执行某动作）、清空。接口的关键技巧是用 typedef 定义通用 Item 类型，让接口与具体数据解耦：

/* list.h（节选）-- 简单列表接口 */
#include <stdbool.h>             /* C99 特性 */
 
#define TSIZE 45
struct film { char title[TSIZE]; int rating; };
typedef struct film Item;        /* 第 1 层：数据是什么 */
 
typedef struct node {
    Item item;                   /* 第 2 层：节点 = 数据 + 链接 */
    struct node * next;
} Node;
 
typedef Node * List;             /* 第 3 层：列表 = 指向头节点的指针 */
 
void InitializeList(List * plist);
bool ListIsEmpty(const List * plist);
bool ListIsFull(const List * plist);
unsigned int ListItemCount(const List * plist);
bool AddItem(Item item, List * plist);
void Traverse(const List * plist, void (* pfun)(Item item));
void EmptyTheList(List * plist);

三个设计要点：数据隐藏（data hiding）——用户只该写 InitializeList(&movies) 而不是自己写 movies = NULL，将来把 List 从”指针”改成”结构”时接口调用一行不用变；统一用指针传参——严格说只有初始化、添加、清空需要修改列表，其余可传值，但为免用户记忆”哪些传址”，干脆全部传地址，只读函数加 const；函数指针（pointer to function）——Traverse() 的 pfun 指向”接受一个 Item、无返回值”的函数，遍历时对每个节点调用一次。

17.4.2 使用接口：films3.c

接口定好后，主程序完全用”问题语言”来写，看不见任何 malloc()：

/* films3.c -- 使用 ADT 风格的链表（与 list.c 一起编译） */
#include "list.h"            /* 定义 List、Item */
void showmovies(Item item);  /* 符合 Traverse() 要求的原型 */
 
int main(void)
{
    List movies;
    Item temp;
 
    InitializeList(&movies);                    /* 初始化 */
    while (gets(temp.title) != NULL && temp.title[0] != '\0')
    {
        scanf("%d", &temp.rating);
        if (AddItem(temp, &movies) == false)    /* 添加 */
        {
            fprintf(stderr, "Problem allocating memory\n");
            break;
        }
    }
    if (ListIsEmpty(&movies))
        printf("No data entered. ");
    else
    {
        printf("Here is the movie list:\n");
        Traverse(&movies, showmovies);          /* 函数名即函数指针 */
    }
    printf("You entered %d movies.\n", ListItemCount(&movies));
    EmptyTheList(&movies);                      /* 清理 */
    return 0;
}
/* showmovies(Item item) 定义：printf("Movie: %s Rating: %d\n", ...) */

Success

对比 films2.c 与 films3.c：底层机制完全相同（动态分配的链式结构），但 films3.c 读起来像在描述任务本身——“初始化列表、添加电影、遍历显示”。更妙的是 list.h + list.c 成了可复用包：想存亲戚通讯录？只需把 Item 重新 typedef 成新结构，其余代码原封不动。

17.4.3 实现接口：list.c

实现文件里最有代表性的两个函数：

/* list.c（节选）-- 列表操作的实现 */
static void CopyToNode(Item item, Node * pnode);  /* 内部辅助函数 */
 
bool AddItem(Item item, List * plist)
{
    Node * pnew;
    Node * scan = *plist;
    pnew = (Node *) malloc(sizeof(Node));
    if (pnew == NULL)              /* 分配失败，提前退出 */
        return false;
    CopyToNode(item, pnew);        /* 拷贝数据到新节点 */
    pnew->next = NULL;             /* 新节点暂时是末节点 */
    if (scan == NULL)              /* 空表：新节点即头节点 */
        *plist = pnew;
    else
    {
        while (scan->next != NULL) /* 找到链表末尾 */
            scan = scan->next;
        scan->next = pnew;         /* 挂到末尾 */
    }
    return true;
}
 
void EmptyTheList(List * plist)
{
    Node * psave;
    while (*plist != NULL)
    {
        psave = (*plist)->next;    /* 先保存下一节点地址 */
        free(*plist);              /* 再释放当前节点 */
        *plist = psave;            /* 前进到下一节点 */
    }
}

EmptyTheList() 两处精妙细节：List 本身是指针，所以 plist 是指向指针的指针（Node **），循环结束时 *plist 为 NULL，调用方的头指针也被安全置空；必须先保存后释放——free() 之后内存内容原则上不再可用，不先存 next 就找不到下一个节点了。辅助函数 CopyToNode() 用 static 修饰，把可见性限制在本文件内——这是 C 实现”私有方法”的方式。

17.4.4 const 的局限

const List * plist 能防止函数修改 *plist（头指针本身），但不能防止修改头指针所指向的数据：*plist = (*plist)->next; 不允许，而 (*plist)->item.rating = 3; 完全合法。

Warning

const List * p 的承诺是”不通过 p 修改 p 指向的那个指针变量”，不是”链表内容不可侵犯”。不要指望 const 替你抓出所有意外修改——它只保护”第一层”。

17.5 队列 ADT：先进先出的排队模型

队列（queue）是带两条规则的列表：新项只能加到末尾（入队），删除只能发生在开头（出队）——像排队买票，先来先走，即先进先出（FIFO, First In First Out）。用数组实现队列很尴尬：出队若把后面元素整体前移，开销大；只改”队头”下标，数组前端又积累死空间。聪明的补救是循环队列（circular queue）——把数组想象成首尾相接的纸圈。更自然的做法是继续用链表：出队只需把 front 指针移向下一个节点，谁也不用挪。

/* queue.h（节选）-- 队列接口 */
typedef int Item;                /* 使用时按需替换 */
#define MAXQUEUE 10
 
typedef struct node {
    Item item;
    struct node * next;
} Node;
 
typedef struct queue {
    Node * front;                /* 指向队头 */
    Node * rear;                 /* 指向队尾 */
    int    items;                /* 当前项数 */
} Queue;
 
void InitializeQueue(Queue * pq);
bool QueueIsFull(const Queue * pq);   bool QueueIsEmpty(const Queue * pq);
bool EnQueue(Item item, Queue * pq);  bool DeQueue(Item * pitem, Queue * pq);
void EmptyTheQueue(Queue * pq);

Queue 结构三件套各司其职：front 供出队用，rear 让入队不必从头遍历，items 让判空/判满/计数都是常数时间。

/* queue.c（节选）-- 入队与出队 */
bool EnQueue(Item item, Queue * pq)
{
    Node * pnew;
    if (QueueIsFull(pq))
        return false;
    pnew = (Node *) malloc(sizeof(Node));
    if (pnew == NULL)
    { fprintf(stderr, "Unable to allocate memory!\n"); exit(1); }
    CopyToNode(item, pnew);
    pnew->next = NULL;
    if (QueueIsEmpty(pq))
        pq->front = pnew;          /* 空队：新节点既是头也是尾 */
    else
        pq->rear->next = pnew;     /* 挂到原队尾之后 */
    pq->rear = pnew;               /* 更新队尾指针 */
    pq->items++;
 
    return true;
}
 
bool DeQueue(Item * pitem, Queue * pq)
{
    Node * pt;
    if (QueueIsEmpty(pq))
        return false;
    CopyToItem(pq->front, pitem);  /* 1. 把队头数据交给调用者 */
    pt = pq->front;                /* 2. 暂存待释放节点 */
    pq->front = pq->front->next;   /* 3. 队头后移 */
    free(pt);                      /* 4. 释放原队头 */
    pq->items--;
    if (pq->items == 0)            /* 5. 删空了，队尾也归位 */
        pq->rear = NULL;
 
    return true;
}

两个容易忽略的细节：删除最后一项时没有显式给 front 置 NULL——第 3 步已把 front 赋成被删节点的 next，而末节点的 next 本来就是 NULL，一石二鸟；pt 临时指针必不可少——pq->front 马上要被改写，不先用 pt 记住旧队头地址，free() 就没有对象了。清空队列则是反复调用 DeQueue() 直到 QueueIsEmpty() 为真。

Success

队列包做成后，把 Item 从 int 换成”顾客结构”（到达时间 + 咨询时长），接口一行不改，立刻能做商场咨询亭模拟：每分钟检查是否有新顾客（rand() 决定），队满算”被拒”，Sigmund 忙完一位就从队头叫下一位。对比实验显示：每小时 20 位顾客平均等待约 1.35 分钟，25 位涨到 3.5 分钟，30 位飙升到 11.83 分钟且大量拒客——排队系统在接近饱和时性能断崖式恶化。这正是 ADT 的价值：让你专注于模拟逻辑，而非指针细节。

Warning

定义了 ADT 接口后，就应当只用接口函数操作数据。直接伸手改 pq->front 或某个节点的 next，可能破坏 EnQueue() 与 DeQueue() 之间的指针约定（如”队尾节点的 next 必须为 NULL”），让整个包悄悄出错。

17.6 链表与数组：各有千秋的选择题

数据形式	优点	缺点
数组	C 直接支持；支持随机访问（random access，下标直达）	大小编译期定死；插入/删除要搬动大量数据
链表	大小运行时按需增长；插入/删除只需改两个指针	无随机访问，只能顺序访问（sequential access）；需自建管理代码

访问方式的差异在查找上被急剧放大。对有序数组可用二分查找（binary search）：每次取中点比较，一次排除一半候选——127 个元素最多 7 次比较出结果，一般 n 次比较可处理 2ⁿ−1 个元素。但二分查找依赖”跳到中间”的能力：数组下标 (0+99)/2 一算就到，链表只能一步一步爬，根本用不了这个算法。选择口诀：频繁增删、很少查找 → 链表；数据稳定、查找频繁 → 数组。又增删又频繁查找呢？该请出二叉搜索树了。

17.7 二叉搜索树 ADT：鱼与熊掌兼得

二叉搜索树（binary search tree, BST）把二分查找策略织进链式结构。每个节点含一个数据项和两个孩子指针（左、右），并遵守铁律：左子树所有项排在父项之前，右子树所有项排在父项之后，且对每个节点都成立。树顶节点有个反直觉的名字：根（root）（植物学家请勿较真）；每个节点连同后代构成子树（subtree），树是天然的递归结构。查找 puppy：与根 melon 比 → 更大走右边；与 style 比 → 更小走左边；与 plenum 比 → 更大但其右分支为空——3 次比较断定不在树中。

17.7.1 接口：tree.h

/* tree.h（节选）-- 二叉搜索树接口（不允许重复项） */
typedef struct item { char petname[20]; char petkind[20]; } Item;
#define MAXITEMS 10
 
typedef struct node {
    Item item;
    struct node * left;          /* 左孩子 */
    struct node * right;         /* 右孩子 */
} Node;
 
typedef struct tree { Node * root; int size; } Tree;  /* 根指针 + 项数 */
 
void InitializeTree(Tree * ptree);
bool TreeIsEmpty(const Tree * ptree);   bool TreeIsFull(const Tree * ptree);
bool AddItem(const Item * pi, Tree * ptree);   bool InTree(const Item * pi, const Tree * ptree);
bool DeleteItem(const Item * pi, Tree * ptree);
void Traverse(const Tree * ptree, void (* pfun)(Item item));
void DeleteAll(Tree * ptree);

Tree 用结构（根指针 + 计数器）而非单纯根指针，方便常数时间查知树的大小。

17.7.2 添加节点：顺着规矩往下走

/* tree.c（节选）-- 添加节点 */
static void AddNode(Node * new_node, Node * root)
{
    if (ToLeft(&new_node->item, &root->item))
    {
        if (root->left == NULL)          /* 左子树为空，就地安家 */
            root->left = new_node;
        else
            AddNode(new_node, root->left);  /* 否则递归处理左子树 */
    }
    else if (ToRight(&new_node->item, &root->item))
    {
        if (root->right == NULL)
            root->right = new_node;
        else
            AddNode(new_node, root->right);
    }
    else   /* 既不左也不右 = 重复项 */
    { fprintf(stderr, "location error in AddNode()\n"); exit(1); }
}
 
static bool ToLeft(const Item * i1, const Item * i2)
{
    int comp1;
    if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)
        return true;
    else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) < 0)
        return true;   /* 同名宠物再按种类比 */
    else
        return false;
}

ToLeft()/ToRight() 是树的”小于/大于号”。把比较逻辑独立成函数而非硬编码在 AddNode() 里，将来换数据类型只需重写这两个函数。查找交给 SeekItem()：返回 Pair 结构（parent + child 两个指针），于是 InTree() 只看 child 是否为 NULL，删除操作还能顺便拿到父节点——一处实现，三处复用（添加查重、查找、删除定位）。

17.7.3 删除节点：全章最难的指针手术

删除分三种情形：叶节点（leaf，无孩子）——把父节点中指向它的指针置 NULL 再 free()；单孩子节点——让父节点”收养”孩子，把孩子的地址填进父节点中原指向被删节点的位置；双子节点——最麻烦：把左子树整体接替被删节点的位置，再把右子树挂到左子树最右下角的空位（右子树所有项大于左子树所有项，又都小于被删节点的父节点）。

/* tree.c（节选）-- 删除节点：ptr 是"父节点中指向目标的那根指针"的地址 */
static void DeleteNode(Node ** ptr)
{
    Node * temp;
 
    if ((*ptr)->left == NULL)        /* 情形 A：无左孩子（含无孩子） */
    {
        temp = *ptr;
        *ptr = (*ptr)->right;        /* 右孩子（或 NULL）顶替 */
        free(temp);
    }
    else if ((*ptr)->right == NULL)  /* 情形 B：无右孩子 */
    {
        temp = *ptr;
        *ptr = (*ptr)->left;
        free(temp);
    }
    else                             /* 情形 C：两个孩子 */
    {
        /* 沿左子树的右臂找到最右空位 */
        for (temp = (*ptr)->left; temp->right != NULL;
             temp = temp->right)
            continue;
        temp->right = (*ptr)->right; /* 右子树嫁接过去 */
        temp = *ptr;
        *ptr = (*ptr)->left;         /* 左子树顶替被删节点 */
        free(temp);
    }
}
 
bool DeleteItem(const Item * pi, Tree * ptree)
{
    Pair look;
 
    look = SeekItem(pi, ptree);
    if (look.child == NULL)
        return false;                        /* 没找到 */
    if (look.parent == NULL)                 /* 删的是根 */
        DeleteNode(&ptree->root);
    else if (look.parent->left == look.child)
        DeleteNode(&look.parent->left);      /* 传左指针的地址 */
    else
        DeleteNode(&look.parent->right);     /* 传右指针的地址 */
    ptree->size--;
    return true;
}

这段代码的精华在于 Node **ptr：所有情形归根结底都是”修改父节点里的某一根指针”，要修改一个 Node * 变量，就必须把它的地址传进来。DeleteItem() 根据查找结果，把”父节点.left”、“父节点.right”或”树根”三根指针之一的地址交给 DeleteNode()——接口层谈”项”和”树”，实现层才见指针。

17.7.4 遍历与清空：递归的天然舞台

/* tree.c（节选）-- 中序遍历与整树清空 */
static void InOrder(const Node * root, void (* pfun)(Item item))
{
    if (root != NULL)
    {
        InOrder(root->left, pfun);   /* 先处理左子树 */
        (*pfun)(root->item);         /* 再处理本节点 */
        InOrder(root->right, pfun);  /* 最后处理右子树 */
    }
}
 
static void DeleteAllNodes(Node * root)
{
    Node * pright;
 
    if (root != NULL)
    {
        pright = root->right;        /* 释放前先记住右子树 */
        DeleteAllNodes(root->left);
        free(root);
        DeleteAllNodes(pright);
    }
}

“左→根→右”的**中序遍历（inorder traversal）**让所有项按字母序输出——二叉搜索树天生是排序机。DeleteAllNodes() 在 free(root) 前先存下右子树地址，与链表清空的”先保存后释放”同一道理。

17.8 树的思考：平衡与变体

BST 的效率建立在**树足够茂盛（balanced，平衡）**的前提上。若按字母序输入数据，每个新节点都挂到右边，整棵树退化成一根”藤条”，查找效率与逐个遍历链表无异（如图所示）。对抗失衡的经典方案是 AVL 树（以发明者 Adel’son-Vel’skii 和 Landis 命名）：插入/删除后按需局部旋转重组，保持近似平衡，代价是建树稍慢。实用变体还有：允许重复项时给节点加计数器（统计词频）；或按名字排序、把同名的多个项组织成链表挂在同一节点上。手工实现 ADT 工作量大、易出错，工程中可选用现成库——但亲手写过一遍链表、队列和树，你才有能力看懂并信任那些库。

17.9 本章要点回顾

• 数据类型 = 存储方式 + 合法操作；ADT 三步法：抽象描述 → 接口（头文件）→ 实现（源文件），实现可随时换血。
• 链表每个节点自带”下一站地址”，头指针是唯一入口，末节点以 NULL 收尾。
• 队列是 FIFO 列表，front/rear/items 三件套让入队出队都是常数时间。
• 数组擅长随机访问与二分查找，链表擅长动态增删，二叉搜索树两者兼得但要求平衡。
• 凡 malloc() 必有对应的 free()，且释放前要先保存”下一站”地址。

自测五题（点击展开答案）

1. 为什么结构可以包含指向自身类型的指针，却不能包含自身类型的成员？ 结构成员会使结构的大小无限递归，编译器无法确定其大小；而指针的大小固定（与指向什么类型无关），存放”下一个同类型结构的地址”完全合法——这正是链表的实现基础。 2. 遍历链表时为什么要用临时指针 current，而不直接移动 head？ 链表中没有任何节点存着第一个节点的地址，head 是找到链表开头的唯一线索。一旦 head = head->next 走出去，链表头部就永久丢失了。规则：遍历用临时指针，head 只读不动。 3. 简述 ADT 三步法，并说明”数据隐藏”体现在哪一步。 第一步抽象描述类型的属性与操作（不绑定语言）；第二步设计编程接口（头文件：类型定义 + 函数原型 + 前置/后置条件注释）；第三步编写实现代码。数据隐藏体现在接口层：用户只知道 InitializeList(&movies) 这样的调用，不知道 List 到底是指针还是结构，实现因此可随时更换而不影响使用方代码。 4. DeQueue() 删除最后一项后，为什么不用显式执行 pq->front = NULL？ 因为 pq->front = pq->front->next 已把 front 赋值为被删节点的 next；末节点的 next 本来就是 NULL，删空时 front 自然变成 NULL。但 rear 没有这层”巧合”，必须显式执行 pq->rear = NULL。 5. 向二叉搜索树按字母序插入 n 个节点会发生什么？如何补救？ 每个新节点都成为上一个节点的右孩子，整棵树退化成一条只有右侧分支的”链”，查找从 O(log n) 退化为 O(n)。补救办法是使用自平衡树（如 AVL 树）：插入、删除后检测失衡并旋转重组，以少量建树开销换取稳定的查找效率。