高级数据表示

掌握链表所有权、ADT接口与实现、队列模拟、数组与链表权衡、二叉搜索树及比较回调

学习目标

能实现单向链表插入与销毁，证明 head 所有权和每个 malloc 节点的唯一 free 路径
能设计不透明 Queue ADT，并用 front/rear 不变量完成到达、服务、等待时间的队列模拟
能实现二叉搜索树插入、查找和后序销毁，并比较数组、链表与未平衡树的复杂度边界

从「固定函数名」到「可替换的行为」

前几章你已会用数组、struct、指针组织数据。但程序里还有另一类需求：同一套流程，具体步骤可换——排序按整数比还是按字符串比？菜单按编号执行不同操作？错误处理走默认分支还是自定义回调？

想象餐厅点菜系统：前台只认「下单接口」（菜号 + 做法），后厨可以换厨师、换菜谱，前台流程不变。C 没有类与继承，但可以用把「行为」作为参数或表项传递——再配合 struct 与动态内存，就能手写链表、队列、栈等。

没有这层抽象，你只能为每种排序、每种菜单写死函数名；标准库的 qsort/bsearch 也无法对任意元素类型工作。本章是全书最后一章：把指针、结构体、动态内存串成可扩展的数据结构能力，并看清 C 在抽象上的边界。

函数指针：声明、赋值与调用

对象指针指向对象，函数指针指向函数；两类指针的表示和可转换规则不必相同，不能靠 void * 在两者之间做可移植往返。声明语法最容易错在 * 与括号的优先级：

int  sum(double a, double b);           /* 普通函数原型 */
int (*pf)(double, double);              /* pf 是指针，指向这类函数 */

读法：pf 是一个指针，(*pf) 是被指向的函数。括号不可省——若写成 int *pf(double, double)，则 pf 是返回 int* 的函数，不是指针。

函数指针保存函数的入口地址；声明语法中括号不可省，否则 * 会绑定到返回类型上。

分步1 / 3

第一步：声明指针类型

函数指针保存函数的入口地址；声明语法中括号不可省，否则 * 会绑定到返回类型上。

写出返回类型、(*名字)、参数列表。与函数原型对照，只多一对括号包住 *。

typedef 可简化冗长声明：

typedef int (*Compare_fn)(const void *, const void *);
Compare_fn cmp = my_compare;

函数指针常见用途：回调（qsort）、状态机分派和插件式接口。可实现表驱动分派。

ADT：只承诺「能做什么」

的核心是接口与实现分离：

ADT	核心操作	规则
栈 Stack	push / pop / top	LIFO 后进先出
队列 Queue	enqueue / dequeue	FIFO 先进先出
链表 List	insert / remove / traverse	节点用 `next` 串联

C 语言没有内置 stack<T> 或 list<T>（那是 C++ STL）。ADT 在 C 里通常体现为：

头文件 .h：只放结构体不透明指针或最小字段 + 函数原型（接口）
源文件 .c：内部用数组/链表实现，对外隐藏细节（实现）

这样换实现（数组栈 → 链表栈）时，调用 push/pop 的代码不必改——只要接口语义不变。

队列与栈：两种相反的「进出顺序」

队列从队尾入、队头出；栈在同一端 push 与 pop。约束「谁先谁后」是 ADT 的核心规则。

栈像函数调用栈：最后 push 的帧最先 pop。表达式求值、括号匹配、深度优先搜索常用栈。

队列像排队：新元素从 rear 入队，从 front 出队。广度优先搜索、打印任务、消息缓冲常用队列。

用固定大小数组可实现简单版（栈顶下标 top、队头队尾下标 front/rear）；循环数组可复用空间。链式实现则在堆上分配节点，push/enqueue 改指针即可，无需预先知道最大容量。

猜一猜：用单个下标只从数组一端插入删除，得到的是栈还是队列？

Queue ADT：接口、实现与不变量

头文件可以只暴露不完整类型和操作，不让调用者直接改 front/rear：

/* queue.h */
#include <stddef.h>
 
typedef struct Queue Queue;
 
Queue *queue_create(void);
int queue_enqueue(Queue *queue, unsigned value);
int queue_dequeue(Queue *queue, unsigned *value);
int queue_is_empty(const Queue *queue);
size_t queue_size(const Queue *queue);
void queue_destroy(Queue **queue);

源文件定义表示。关键不变量是：空队列时 front 和 rear 同时为空；单节点时二者指向同一节点；非空时 rear->next 为空。

/* queue.c */
#include "queue.h"
#include <stdint.h>
#include <stdlib.h>
 
struct QueueNode {
    unsigned value;
    struct QueueNode *next;
};
 
struct Queue {
    struct QueueNode *front;
    struct QueueNode *rear;
    size_t size;
};
 
Queue *queue_create(void) {
    return calloc(1, sizeof(Queue));
}
 
int queue_is_empty(const Queue *queue) {
    return queue == NULL || queue->front == NULL;
}
 
size_t queue_size(const Queue *queue) {
    return queue == NULL ? 0 : queue->size;
}
 
int queue_enqueue(Queue *queue, unsigned value) {
    struct QueueNode *node;
    if (queue == NULL || queue->size == SIZE_MAX)
        return 0;
    node = malloc(sizeof *node);
    if (node == NULL)
        return 0;                  /* 失败不改变原队列 */
    node->value = value;
    node->next = NULL;
    if (queue->rear != NULL)
        queue->rear->next = node;
    else
        queue->front = node;
    queue->rear = node;
    queue->size++;
    return 1;
}
 
int queue_dequeue(Queue *queue, unsigned *value) {
    struct QueueNode *node;
    if (queue == NULL || value == NULL || queue->front == NULL)
        return 0;
    node = queue->front;
    *value = node->value;
    queue->front = node->next;
    if (queue->front == NULL)
        queue->rear = NULL;
    queue->size--;
    free(node);
    return 1;
}
 
void queue_destroy(Queue **handle) {
    struct QueueNode *node, *next;
    if (handle == NULL || *handle == NULL)
        return;
    node = (*handle)->front;
    while (node != NULL) {
        next = node->next;
        free(node);
        node = next;
    }
    free(*handle);
    *handle = NULL;
}

calloc 让 create 从空不变量开始；destroy 沿 front 保存 next 后逐节点释放，最后释放 Queue 并把调用方指针置空。链式队列没有编译期固定容量，但仍受 size_t 计数上限、分配失败和进程内存限制。

用队列模拟单服务台

可以评估平均等待时间。下面假设 arrivals 已按非递减时刻排序，服务台每个 tick 最多处理一名顾客：

double simulate_wait(const unsigned arrivals[], size_t count,
                     Queue *queue) {
    size_t next = 0, served = 0;
    unsigned tick = 0, arrived, total_wait = 0;
 
    while (next < count || !queue_is_empty(queue)) {
        while (next < count && arrivals[next] <= tick) {
            if (!queue_enqueue(queue, arrivals[next]))
                return -1.0;
            next++;
        }
        if (queue_dequeue(queue, &arrived)) {
            total_wait += tick - arrived;
            served++;
        }
        tick++;
    }
    return served == 0 ? 0.0 : (double)total_wait / served;
}

真实模拟还要检查 tick 与 total_wait 溢出、支持每位顾客不同服务时长，并区分“分配失败”与合法的负指标。这里的价值是展示 FIFO 如何把到达顺序转成等待时间，而不是把 -1.0 当成通用错误协议。

单向链表：用 next 串起节点

数组元素连续，按下标随机访问 O(1)，但保持顺序的中间插入通常要搬移后续元素。链表的不要求地址连续，通过 struct Node *next 连接：

struct Node {
    int data;
    struct Node *next;
};
 
struct Node *head = NULL;   /* 空链表 */

单向链表每个节点知道「下一个是谁」；头指针是唯一固定入口，丢失 head 则整链无法访问。

分步1 / 4

第一步：定义节点

单向链表每个节点知道「下一个是谁」；头指针是唯一固定入口，丢失 head 则整链无法访问。

payload 可以是任意类型；next 类型必须是「指向同种节点的指针」。

#include <stdlib.h>
 
int list_push_front(struct Node **head, int value) {
    struct Node *node;
    if (head == NULL)
        return 0;
    node = malloc(sizeof *node);
    if (node == NULL)
        return 0;
    node->data = value;
    node->next = *head;
    *head = node;                 /* 最后提交，失败时原链不变 */
    return 1;
}
 
void list_destroy(struct Node **head) {
    struct Node *node, *next;
    if (head == NULL)
        return;
    node = *head;
    while (node != NULL) {
        next = node->next;        /* free 前保存后继 */
        free(node);
        node = next;
    }
    *head = NULL;
}

链表与数组：复杂度必须连同定位成本一起算

的权衡取决于操作分布：

操作	动态数组	单向链表
按下标访问	O(1)	O(n)
已知位置后的插入	搬移时 O(n)	已知前驱时 O(1)
查找值	无序 O(n)	O(n)
连续遍历	缓存局部性通常较好	节点跳转和指针开销
扩容	可能重新分配整块	每节点独立分配，逐次失败

“链表删除 O(1)”只在已经持有前驱或相应链接位置时成立；先从 head 查找目标仍是 O(n)。双向链表多一个 prev，可在已知节点时更容易删除，但增加内存和不变量维护成本。

上面的 list_destroy 把逐节点释放封装进容器实现，调用方不需要接触释放顺序。

二叉搜索树：树接口与树实现

可以用不透明 Tree 接口隐藏节点：

/* tree.h */
#include <stddef.h>
 
typedef struct Tree Tree;
enum TreeInsertResult {
    TREE_OUT_OF_MEMORY = -1,
    TREE_ALREADY_PRESENT = 0,
    TREE_INSERTED = 1
};
 
Tree *tree_create(void);
enum TreeInsertResult tree_insert(Tree *tree, int key);
int tree_contains(const Tree *tree, int key);
size_t tree_size(const Tree *tree);
void tree_destroy(Tree **tree);

树实现把“指向当前子树根指针的指针”作为插入位置，只有节点分配成功后才提交链接：

/* tree.c */
#include "tree.h"
#include <stdint.h>
#include <stdlib.h>
 
struct TreeNode {
    int key;
    struct TreeNode *left;
    struct TreeNode *right;
};
 
struct Tree {
    struct TreeNode *root;
    size_t size;
};
 
Tree *tree_create(void) {
    return calloc(1, sizeof(Tree));
}
 
enum TreeInsertResult tree_insert(Tree *tree, int key) {
    struct TreeNode **link, *node;
    if (tree == NULL || tree->size == SIZE_MAX)
        return TREE_OUT_OF_MEMORY;
    link = &tree->root;
    while (*link != NULL) {
        if (key == (*link)->key)
            return TREE_ALREADY_PRESENT;
        link = key < (*link)->key ? &(*link)->left : &(*link)->right;
    }
    node = malloc(sizeof *node);
    if (node == NULL)
        return TREE_OUT_OF_MEMORY;
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    *link = node;
    tree->size++;
    return TREE_INSERTED;
}
 
int tree_contains(const Tree *tree, int key) {
    const struct TreeNode *node = tree == NULL ? NULL : tree->root;
    while (node != NULL) {
        if (key == node->key)
            return 1;
        node = key < node->key ? node->left : node->right;
    }
    return 0;
}
 
size_t tree_size(const Tree *tree) {
    return tree == NULL ? 0 : tree->size;
}
 
static void destroy_nodes(struct TreeNode *node) {
    if (node == NULL)
        return;
    destroy_nodes(node->left);
    destroy_nodes(node->right);
    free(node);
}
 
void tree_destroy(Tree **handle) {
    if (handle == NULL || *handle == NULL)
        return;
    destroy_nodes((*handle)->root);
    free(*handle);
    *handle = NULL;
}

查找和插入都是 O(h)，h 为树高；未平衡树按有序键插入会退化成长度 n 的链，最坏 O(n)，不能笼统声称 O(log n)。中序遍历会按键递增访问节点。递归后序销毁简洁，但不可信数据形成的深退化树可能耗尽调用栈，工程实现可改用显式栈或在容器中采用平衡树。

qsort 与 bsearch：标准库里的回调

<stdlib.h> 提供两个依赖比较函数的泛型工具：

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));
 
void *bsearch(const void *key, const void *base,
              size_t nmemb, size_t size,
              int (*compar)(const void *, const void *));

接收 const void *（指向元素的指针），需 cast 成实际类型再比：

int int_compare(const void *a, const void *b) {
    int ia = *(const int *)a;
    int ib = *(const int *)b;
    return (ia > ib) - (ia < ib);   /* 安全的三值比较 */
}

qsort 通过函数指针传入比较逻辑；bsearch 依赖有序性做二分。二者是 C 标准库对「回调 + 泛型指针」的典型用法。

qsort 对任意完整对象类型的数组重排，只要提供元素大小与一致的比较关系。标准不规定算法、复杂度或稳定性；相等元素的原顺序可能改变。比较函数不得通过参数修改元素，并应对所有可能比较对给出自洽顺序。

bsearch 要求数组已经按同一 compar 形成相容分区；找到返回某个匹配元素指针，否则返回 NULL。若存在多个相等元素，不指定返回哪一个。未排序或换用不一致比较器会破坏接口前置条件，结果没有可依赖的查找保证。

C 在数据抽象上的边界

C 能做好：struct + 函数指针 + 动态内存 → 链表、表驱动状态机、简单 OOP 风格（struct 首成员 + 统一接口）。

C 不提供：泛型容器、异常安全、构造/析构自动调用、namespace 隔离、真正的信息隐藏（头文件仍可能暴露 struct 布局）。

实践建议：

小项目：固定数组栈/队列足够
需要排序/查找：优先 qsort/bsearch，少手写排序
大型 ADT：.h 用不透明指针 typedef struct Queue Queue;，.c 内定义真实 struct

代码示例：菜单分派与整数排序

函数指针表（简化菜单驱动）：

typedef void (*Action_fn)(void);
 
void cmd_new(void)  { puts("新建"); }
void cmd_open(void) { puts("打开"); }
 
int main(void) {
    Action_fn table[] = { cmd_new, cmd_open };
    int choice = 0;   /* 假设已验证 0..1 */
    table[choice]();  /* 间接调用 */
    return 0;
}

qsort + bsearch：

#include <stdio.h>
#include <stdlib.h>
 
int int_compare(const void *a, const void *b) {
    int ia = *(const int *)a, ib = *(const int *)b;
    return (ia > ib) - (ia < ib);
}
 
int main(void) {
    int arr[] = { 42, 7, 19, 3, 88 };
    size_t n = sizeof arr / sizeof arr[0];
 
    qsort(arr, n, sizeof(int), int_compare);
 
    int key = 19;
    int *found = bsearch(&key, arr, n, sizeof(int), int_compare);
    printf("%s\n", found ? "找到" : "未找到");
    return 0;
}

容易踩的坑

小结

函数指针指向兼容函数类型：int (*pf)(...)，赋值 pf = func，调用 pf(...) 或 (*pf)(...)
ADT 强调接口与实现分离；栈 LIFO、队列 FIFO，C 需手写或用库封装
链表以 head 为所有权根；已知链接位置可 O(1) 修改，但定位仍可能 O(n)，销毁前先保存 next
Queue ADT 维护空、单节点和多节点的 front/rear 不变量；队列模拟把 FIFO 到达顺序转换成等待指标
BST 查找和插入为 O(h)，未平衡树最坏退化到 O(n)；后序销毁先释放左右子树
qsort/bsearch 通过 void * 与比较回调处理任意元素类型；bsearch 前提是有序
C 的抽象靠约定与 discipline；全书 17 章从初识 C、控制流、函数、指针、字符串、内存、文件、struct、预处理器、位操作，到本章的数据结构能力——你已具备阅读与编写中等规模 C 程序的基础

练习

问题 1（问答型） 函数指针 int (*pf)(double, double) 与函数声明 int *pf(double, double) 有何区别？

问题 2（概念型） 同样三个元素按 1→2→3 顺序入容器：栈 pop 的顺序是什么？队列 dequeue 的顺序是什么？

问题 3（实现型） 写比较函数，使 qsort 对 double arr[] 升序排序，并规定所有 NaN 排在普通数值之后。

#include <math.h>
 
int dbl_compare(const void *a, const void *b) {
    double da = *(const double *)a;
    double db = *(const double *)b;
    if (isnan(da))
        return isnan(db) ? 0 : 1;
    if (isnan(db))
        return -1;
    return (da > db) - (da < db);
}
/* qsort(arr, n, sizeof(double), dbl_compare); */

若不单独处理 NaN，(da > db) - (da < db) 在任一操作数为 NaN 时返回 0，会把 NaN 与每个普通数都判为等价，无法形成自洽排序关系。这里把所有 NaN 归为同一等价类并放到末尾。

名词解释

本章出现的专业名词，用大白话再讲一遍。

函数指针（function pointer）: 指向兼容函数类型的指针，可用于间接调用。表示不要求等同对象地址或机器入口整数，声明时 (*名字) 必须加括号。见 FunctionPointerDiagram。
间接调用: 通过函数指针而非固定函数名调用代码；(*pf)(args) 或 pf(args)。
函数指针表: 元素为同一兼容函数指针类型的数组或字段集合。按已验证索引或标签选择后间接调用，用于表驱动分派。
抽象数据类型: 只暴露操作规则（接口），隐藏内部表示（实现）的数据类型思想；与 ADT 同义，C 中用 struct + 函数指针模拟。
抽象数据类型（ADT）: 只暴露操作语义、隐藏内部表示的数据类型思想；C 中用 .h 接口 + .c 实现模拟。
栈（stack）: LIFO 结构；push/pop 在同一端（栈顶）。见 QueueStackDiagram。
队列（queue）: FIFO 结构；rear 入队、front 出队。见 QueueStackDiagram。
单向链表（singly linked list）: 节点含 data 与 next；head 指向首节点，末 next 为 NULL。见 LinkedListDiagram。
节点（node）: 链表的基本单位；通常 malloc 分配，通过 next 连接。
头指针（head）: 指向链表第一个节点的指针；空链表为 NULL。
qsort: stdlib 通用排序；参数含 base、元素个数、元素大小、比较函数指针。
bsearch: stdlib 查找接口；要求数组已按同一 compar 形成相容顺序。重复等值元素中返回哪一个不指定，未排序时没有可依赖结果。
比较函数（comparison function）: qsort/bsearch 的回调；const void * 需 cast 后比较，返回负/零/正。见 QsortBsearchDiagram。
回调（callback）: 库函数通过函数指针「回叫」用户提供的逻辑，如 qsort 的 compar。
void *: 可与对象指针互相转换的通用对象指针类型；不能直接解引用，比较器需转换成真实元素指针。它不提供函数指针的可移植中转表示。
队列模拟: 按离散时间把到达事件入队、让服务台从队首取出顾客，并累计等待时间等指标。分配失败和计数溢出必须单独处理。
链表与数组: 连续数组与指针链表示的权衡。数组下标 O(1) 且局部性好；链表已知前驱后局部修改 O(1)，但定位通常 O(n)。
二叉搜索树（BST）: 维持左子树键小、右子树键大的二叉树。操作复杂度为 O(h)；未平衡时 h 可达 n，销毁通常使用后序遍历。

高级数据表示

学习目标

从「固定函数名」到「可替换的行为」

函数指针：声明、赋值与调用

第一步：声明指针类型

ADT：只承诺「能做什么」

队列与栈：两种相反的「进出顺序」

Queue ADT：接口、实现与不变量

用队列模拟单服务台

单向链表：用 next 串起节点

第一步：定义节点

链表与数组：复杂度必须连同定位成本一起算

二叉搜索树：树接口与树实现

qsort 与 bsearch：标准库里的回调

C 在数据抽象上的边界

代码示例：菜单分派与整数排序

容易踩的坑

小结

练习

名词解释

名词解释

讨论