第19章 程序正确性：复杂度、测试和不变量
19.1 问题从哪来#
前面几章写过很多数据结构：数组、链表、栈、队列、树、哈希表。
这些结构都能保存或组织数据，其中数组、链表、树、哈希表还常用来查找数据。但写到这里会遇到两个很实际的问题：
- 这个版本是不是真的比另一个版本快？
- 插入、删除、查找很多次以后，结构有没有悄悄坏掉？
比如哈希表的理想查找是 $O(1)$，但如果所有 id 都落进同一个桶，它就退化成链表。二分查找很快，但前提是数组已经排好序。二叉搜索树查找很快，但前提是树没有退化得太严重。
这些前提不能只靠感觉。程序需要自己打印、计数、检查。不变量就是程序运行前后都应该守住的条件。
19.2 先看一个例子#
查找 13 这件事，几种结构走的路不同：
有序数组是 {1, 3, 5, 7, 9, 11, 13, 15}。顺序查找从第一个元素开始，一个一个往后比，看到 1, 3, 5, 7, 9, 11, 13 才停，一共检查 7 次。
二分查找利用“数组已经排好序”这个事实。第一次看中间的 7，发现 13 更大，就去右半边；第二次看 11，还是更大；第三次看 13，找到。它没有检查前面的每个数，只检查了 7, 11, 13 这 3 个位置。
链表查找也是从头往后走，但走几步取决于节点顺序。下面的程序用头插法建立链表，13 正好排在第二个节点，所以链表查找检查 2 次。二叉搜索树从根节点开始，比当前节点大就往右走，比当前节点小就往左走；这组数据里查找 13 会经过 7, 11, 13。哈希表更直接一些，先算 13 % 11 得到桶编号 2，再到 2 号桶里找。
可以给每个查找函数加一个 steps 计数器。每检查一个候选元素或节点，就让 steps 加一。运行后不只看到“找到了”，还能看到“找了几步”。
19.3 最小程序#
下面这个程序只做一件事：用几种结构查找同一个 id，并打印检查次数。第 18 章的哈希函数在这里命名为 bucket_of，意思是根据 id 算出桶编号。代码里还加了两个小检查：
- 有序数组必须真的有序。
- 哈希表里每个节点必须待在它应该待的桶里。
#include <stdio.h>
#include <stdlib.h>
#define N 8
#define TABLE_SIZE 11
struct Node {
int id;
struct Node *next;
};
struct TreeNode {
int id;
struct TreeNode *left;
struct TreeNode *right;
};
struct Entry {
int id;
struct Entry *next;
};
// 检查并打印测试结果：ok 非零打印 OK，否则打印 FAIL
int check(const char *name, int ok)
{
printf("%s: %s\n", name, ok ? "OK" : "FAIL");
return ok; // 返回 ok 值供调用者进一步判断
}
// 检查数组是否按升序排列（不变量检查）
int is_sorted(int a[], int n)
{
for (int i = 1; i < n; i++) { // 从第二个元素开始逐个比较
if (a[i - 1] > a[i]) { // 发现前一个大于后一个，说明未排序
return 0;
}
}
return 1; // 全部检查通过，数组有序
}
// 顺序查找：从头到尾逐个比较，返回下标或 -1（未找到）
int linear_search(int a[], int n, int target, int *steps)
{
*steps = 0; // 初始化比较次数
for (int i = 0; i < n; i++) {
(*steps)++; // 每比较一次就计数
if (a[i] == target) { // 找到目标
return i; // 返回下标
}
}
return -1; // 遍历完仍未找到
}
// 二分查找：要求数组有序，每次将范围缩小一半
int binary_search(int a[], int n, int target, int *steps)
{
int low = 0; // 查找范围下界
int high = n - 1; // 查找范围上界
*steps = 0; // 初始化比较次数
while (low <= high) { // 范围有效时继续
int mid = low + (high - low) / 2; // 防止溢出的中间位置计算
(*steps)++; // 记录本次比较
if (a[mid] == target) { // 找到目标
return mid;
}
if (a[mid] < target) { // 目标在右半部分
low = mid + 1; // 收缩下界
} else { // 目标在左半部分
high = mid - 1; // 收缩上界
}
}
return -1; // 范围缩小到空，未找到
}
// 链表头插：在链表头部插入新节点，返回新的头指针
struct Node *list_push_front(struct Node *head, int id)
{
struct Node *node = malloc(sizeof(*node)); // 分配新节点
if (node == NULL) { // 分配失败，保持链表不变
return head;
}
node->id = id; // 设置节点数据
node->next = head; // 新节点指向原来的头
return node; // 新节点成为新的头
}
// 链表查找：遍历链表，找到返回 1，否则返回 0
int list_search(struct Node *head, int target, int *steps)
{
*steps = 0; // 初始化比较次数
for (struct Node *cur = head; cur != NULL; cur = cur->next) {
(*steps)++; // 记录当前节点的比较
if (cur->id == target) { // 找到目标
return 1;
}
}
return 0; // 遍历结束未找到
}
// 二叉搜索树插入：按 BST 规则将 id 插入子树，返回子树根
struct TreeNode *tree_insert(struct TreeNode *root, int id)
{
if (root == NULL) { // 到达空位置，在此创建新节点
struct TreeNode *node = malloc(sizeof(*node)); // 分配节点
if (node == NULL) { // 分配失败
return NULL;
}
node->id = id; // 设置数据
node->left = NULL; // 新节点暂时没有子节点
node->right = NULL;
return node; // 返回新节点作为子树的根
}
if (id < root->id) { // 目标小于当前节点，往左子树插入
root->left = tree_insert(root->left, id);
} else if (id > root->id) { // 目标大于当前节点，往右子树插入
root->right = tree_insert(root->right, id);
}
return root; // 相等时不插入，返回原根
}
// 二叉搜索树查找：从根开始比较，根据大小走左或右子树
int tree_search(struct TreeNode *root, int target, int *steps)
{
*steps = 0; // 初始化比较次数
while (root != NULL) { // 非空节点继续查找
(*steps)++; // 记录本次比较
if (root->id == target) { // 找到目标
return 1;
}
// 目标更小走左边，更大走右边
root = (target < root->id) ? root->left : root->right;
}
return 0; // 到达空节点，未找到
}
// 哈希桶计算：对 TABLE_SIZE 取模得到桶编号
int bucket_of(int id)
{
return id % TABLE_SIZE; // 取模运算，确保返回值在 [0, TABLE_SIZE) 范围内
}
// 哈希表插入：计算桶编号，将新节点链入对应桶的头部
void hash_insert(struct Entry *table[], int id)
{
int bucket = bucket_of(id); // 计算归属的桶编号
struct Entry *entry = malloc(sizeof(*entry)); // 分配新节点
if (entry == NULL) { // 分配失败，放弃插入
return;
}
entry->id = id; // 设置数据
entry->next = table[bucket]; // 新节点指向桶的当前头部
table[bucket] = entry; // 新节点成为桶的新头部
}
// 哈希表查找：先定位桶，再遍历该桶的链表
int hash_search(struct Entry *table[], int target, int *steps)
{
int bucket = bucket_of(target); // 根据目标算出桶编号
*steps = 0; // 初始化比较次数
for (struct Entry *cur = table[bucket]; cur != NULL; cur = cur->next) {
(*steps)++; // 记录当前节点的比较
if (cur->id == target) { // 找到目标
return 1;
}
}
return 0; // 桶链表遍历完未找到
}
// 哈希表不变量检查：每个节点必须待在 bucket_of() 算出的桶中
int hash_bucket_ok(struct Entry *table[])
{
for (int bucket = 0; bucket < TABLE_SIZE; bucket++) { // 遍历每个桶
for (struct Entry *cur = table[bucket]; cur != NULL; cur = cur->next) {
if (bucket_of(cur->id) != bucket) { // 节点算出桶与当前桶不匹配
return 0; // 不变量被破坏
}
}
}
return 1; // 所有节点检查通过
}
// 释放整个链表：从头到尾逐个释放节点
void free_list(struct Node *head)
{
while (head != NULL) { // 还有节点未释放
struct Node *next = head->next; // 先保存下一个节点地址
free(head); // 释放当前节点
head = next; // 移到下一个节点
}
}
// 递归释放整个二叉搜索树：后序遍历，先释放子树再释放根
void free_tree(struct TreeNode *root)
{
if (root == NULL) { // 空树，递归基准情况
return;
}
free_tree(root->left); // 释放左子树
free_tree(root->right); // 释放右子树
free(root); // 最后释放根节点
}
// 释放整个哈希表：遍历每个桶，逐个释放桶中链表的所有节点
void free_hash(struct Entry *table[])
{
for (int i = 0; i < TABLE_SIZE; i++) { // 遍历每个桶
struct Entry *cur = table[i]; // 桶的头节点
while (cur != NULL) { // 逐个释放桶中链表
struct Entry *next = cur->next; // 保存下一个节点
free(cur); // 释放当前节点
cur = next; // 移到下一个
}
}
}
int main(void)
{
int sorted_ids[N] = {1, 3, 5, 7, 9, 11, 13, 15}; // 已经有序的数组，用于二分查找
int insert_order[N] = {7, 3, 11, 1, 5, 9, 13, 15}; // 动态结构的插入顺序
int target = 13; // 要查找的目标
int steps = 0; // 记录查找比较次数
struct Node *list = NULL; // 链表头
struct TreeNode *tree = NULL; // 二叉搜索树根
struct Entry *table[TABLE_SIZE] = {0}; // 哈希表，初始所有桶为空
// 按相同顺序向三个结构中插入数据
for (int i = 0; i < N; i++) {
list = list_push_front(list, insert_order[i]); // 链表头插
tree = tree_insert(tree, insert_order[i]); // 二叉搜索树插入
hash_insert(table, insert_order[i]); // 哈希表插入
}
// 运行不变量检查
check("Array sorted", is_sorted(sorted_ids, N)); // 验证 sorted_ids 有序
check("Hash bucket position correct", hash_bucket_ok(table)); // 验证哈希表每个节点在正确桶中
// 顺序查找（线性复杂度）
linear_search(sorted_ids, N, target, &steps);
printf("Linear search checks: %d\n", steps);
// 二分查找（对数复杂度）
binary_search(sorted_ids, N, target, &steps);
printf("Binary search checks: %d\n", steps);
// 链表查找（线性复杂度）
list_search(list, target, &steps);
printf("List search checks: %d\n", steps);
// 二叉搜索树查找（平均对数复杂度）
tree_search(tree, target, &steps);
printf("Tree search checks: %d\n", steps);
// 哈希表查找（平均常数复杂度）
hash_search(table, target, &steps);
printf("Hash search checks: %d\n", steps);
// 释放所有动态分配的内存
free_list(list);
free_tree(tree);
free_hash(table);
return 0;
}19.4 编译运行#
保存为 correctness.c，编译：
$ gcc correctness.c -o correctness
运行，这份程序的输出如下：
$ ./correctness
Array sorted: OK
Hash bucket position correct: OK
Linear search checks: 7
Binary search checks: 3
List search checks: 2
Tree search checks: 3
Hash search checks: 1
不同插入顺序会改变链表和树的检查次数。哈希表也会受桶数量和冲突影响。这正是计数实验有用的地方：把“好像更快”变成“这组数据下走了几步”。
19.5 测试不是只看一次输出#
只跑一次 target = 13，只能说明这一个输入看起来没问题。可以继续换输入：
| 输入 | 期望 |
|---|---|
target = 1 | 能找到 |
target = 15 | 能找到 |
target = 8 | 找不到 |
| 空链表 | 找不到，不崩溃 |
| 只有 1 个元素的树 | 能找到或安全返回找不到 |
测试就是把这些情况写成可以重复运行的小实验。
check("Array sorted", is_sorted(sorted_ids, N)); 这种写法很朴素，但已经有测试的味道：给一个名字，检查一个条件，打印 OK 或 FAIL。
19.6 不变量#
不变量是不管执行多少次操作，都应该一直成立的条件。
| 结构 | 不变量 |
|---|---|
| 有序数组 | 对所有 0 <= i < n - 1，都有 a[i] <= a[i + 1] |
| 栈 | 0 <= top <= capacity |
| 队列 | front 和 rear 始终落在数组范围内 |
| 二叉搜索树 | 左子树都小于根，右子树都大于根 |
| 哈希表 | 每个节点都在 id % TABLE_SIZE 对应的桶里 |
插入和删除最容易破坏不变量。比如二分查找依赖“数组有序”，如果插入新元素后忘了保持顺序，二分查找仍然会跑，但结果可能错。
19.7 常见坑#
坑 1：只测最顺的一条路径。 比如只查存在的 id，不查不存在的 id。程序可能在“找不到”时越界或返回乱值。
坑 2：只看输出，不看结构。 哈希表打印能找到某个 id，不代表所有节点都在正确的桶里。可以写 hash_bucket_ok 检查结构本身。
坑 3：把复杂度当成固定时间。 $O(1)$ 不是永远一步，$O(\log n)$ 也不是永远比 $O(n)$ 快。小数据下常数开销会影响结果。复杂度看的是数据量增长时的趋势。
坑 4：测试代码也可能有 bug。 如果 check 的条件写反，错误会被打印成 OK。测试代码要尽量短，条件要能读懂。
19.8 自己试试看#
Q1：换目标值。 把 target 改成 1、8、15，观察几种查找方式的检查次数。
Q2：破坏有序数组。 把 sorted_ids 改成 {1, 7, 5, 3, 9, 11, 13, 15}，看看 is_sorted 和二分查找会发生什么。
Q3：增加数据量。 把数组扩展到 16 个元素，再比较顺序查找和二分查找的检查次数。
Q4：制造哈希冲突。 把 TABLE_SIZE 改成 2，观察哈希查找的检查次数是否增加。
Q5：给链表加长度检查。 写一个 list_count，插入 8 个节点后确认长度确实是 8。
下一章的问题#
前面几章已经把保存记录、查找记录、排序、树、哈希和结构检查放在一起练过。写小数据库时，这些检查不会消失：记录要能插入和查找，计数器要落在正确范围内，删除后结构也不能留下坏状态。
数据库不是一种全新的语法。它先是一个普通的 C 结构体，里面放记录数组和计数器，再配上一组插入、查找、删除、列出的函数。
阶段项目#
数据结构段落的能力可以放在一起比一比：阶段项目 3：数据结构查找对比器。同一批 id 装进无序数组、有序数组+二分、BST、哈希表，对一组查询比较每种结构的查找次数。练完再进入数据库生长线。