第17章：高级数据表示
程序的数据表示不仅决定“把数据放在哪里”，还决定“哪些操作容易完成、需要付出多少代价”。同样是一组记录，可以放在数组里，也可以连接成链表，或者按照键组织成查找树。选择取决于实际需要的操作。
本章的主线是：先描述数据与操作，再设计接口，最后选择表示方式并实现算法。 链表、队列和二叉查找树是理解这个过程的具体例子。以下代码以 C11 为背景。
1. 设计数据表示，先列出操作
假设要记录看过的电影，每条记录包含片名和评分：
typedef struct {
char title[64];
int rating;
} Film;
这只解决了一条记录的表示，还没有回答如何管理全部电影。
在选择容器前，先考虑：
- 记录数量是否提前知道，运行中是否不断增加？
- 是经常按照下标访问，还是顺序遍历全部记录？
- 是否频繁插入、删除，是否需要保持排序？
- 是否经常按照片名查找，是否允许重复？
- 内存不足或达到容量上限时，调用者应该得到什么结果？
1.1 固定数组、动态数组与链式结构
| 表示方式 | 数量与容量 | 主要特点 |
|---|---|---|
| 固定长度数组 | 容量在声明中确定 | 简单、连续存储，可能预留过多或不足 |
| 动态分配的数组 | 分配时决定容量 | 能按运行时需求分配，元素仍连续 |
| 可扩容动态数组 | 保存长度与容量，必要时重新分配 | 随机访问方便，扩容可能移动全部元素 |
| 动态链式结构 | 通常逐个分配节点 | 不要求节点连续，但需要额外指针和分配管理 |
数组并不都要求在编译时确定长度。动态分配、变长数组和固定长度数组应分别理解；变长数组也不会因为加入新元素而自动扩容。
动态数组与链表都能处理运行时才知道的数量，区别在于布局和操作成本。
1.2 动态分配要检查长度和乘法
/* 已包含 <stdint.h>、<stdlib.h>，count 的类型是 size_t。 */
Film *movies = NULL;
if (count != 0 && count <= SIZE_MAX / sizeof *movies) {
movies = malloc(count * sizeof *movies);
if (movies == NULL) {
/* 报告分配失败。 */
}
}
输入的负数不能不经检查就转换成 size_t。分配前检查乘法是否溢出，分配后检查返回值。零个元素可以直接用空指针表示，不必依赖 malloc(0) 的返回形式。
使用 realloc() 扩容时，要通过临时指针接收结果；对于非零的新大小，分配失败时原内存块仍然有效。
2. 单向链表：让节点保存下一个节点的位置
数组通过连续布局和下标定位元素；单向链表通过节点里的指针定位后继节点。
typedef struct node {
Film item;
struct node *next;
} Node;
结构不能直接包含一个同类型的完整结构成员，否则无法得到有限大小；它可以包含指向自身类型的指针。
head
↓
[记录 A | next] → [记录 B | next] → [记录 C | NULL]
节点可以散布在不同内存位置。箭头表示保存的地址，不表示相邻的物理内存。
2.1 三类指针承担不同任务
| 指针 | 作用 |
|---|---|
头指针 head |
找到第一个节点，是整个链的入口 |
尾指针 tail |
找到最后一个节点，便于追加 |
临时指针 current |
遍历或处理某个节点 |
空链表的头指针是 NULL。最后一个节点的 next 是 NULL。
头指针不是头节点。这里也没有额外分配一个不存储有效记录的哨兵节点；采用哨兵是另一种实现选择。
2.2 遍历时移动临时指针
for (const Node *current = head;
current != NULL;
current = current->next) {
printf("%s: %d\n", current->item.title, current->item.rating);
}
current = current->next 改变的是当前访问位置，没有搬动节点。
如果只是显示数据，就不应不断修改唯一的头指针。失去头指针又没有其他入口时，程序可能再也无法找到原来的节点。
2.3 追加：先准备节点，再接入链中
推荐顺序：
- 分配节点，检查是否成功。
- 填好数据，并设置
next = NULL。 - 空链表时更新头指针；否则连接旧尾节点。
- 更新尾指针和数量。
Node *fresh = malloc(sizeof *fresh);
if (fresh == NULL) {
return false;
}
fresh->item = item;
fresh->next = NULL;
if (list->tail == NULL) {
list->head = fresh;
} else {
list->tail->next = fresh;
}
list->tail = fresh;
++list->size;
先完成可能失败的分配，再修改原链表，可以保证分配失败时原内容与计数不变。
Film 包含字符数组，结构赋值会复制这些数组的内容。如果把片名改成 char *，结构赋值只复制指针，字符串的所有权必须重新设计。
2.4 清空：先保存后继，再释放当前节点
Node *current = list->head;
while (current != NULL) {
Node *next = current->next;
free(current);
current = next;
}
list->head = NULL;
list->tail = NULL;
list->size = 0;
free(current) 之后，不能再读取 current->next。释放节点不会自动把所有指向它的指针设为 NULL。
循环条件应检查当前仍有效的链入口或遍历位置。不要一边释放节点，一边依赖没有同步更新的旧指针判断是否结束。
3. 抽象数据类型：把需求、接口与实现分开
抽象数据类型，简称 ADT，描述的是一类数据的属性，以及可以对它执行的操作。它首先是一份关于行为的约定，不依赖某一种编程语言或内存布局。
例如，“保存有先后顺序的电影记录，并允许追加、遍历和清空”，可以作为一个简单列表的抽象描述。
这里需要区分两个层次：列表描述逻辑上的序列；链表是一种用链接节点实现序列的方式。 一个列表接口也可以由数组实现。
3.1 从抽象到代码的三层
| 层次 | 要回答的问题 | C 中的常见形式 |
|---|---|---|
| 抽象描述 | 数据有什么性质，允许哪些操作？ | 类型与操作的文字约定 |
| 编程接口 | 调用者如何提出这些操作？ | 类型名、函数原型、参数与返回值约定 |
| 具体实现 | 用什么结构和算法完成操作？ | 结构定义、节点管理、函数定义 |
使用者关心“追加电影是否成功”；实现者负责 malloc()、尾指针以及错误情况下的清理。
3.2 接口要写清前提与结果
以追加操作为例：
/* 前提：list 指向已初始化的列表；item 是合法电影记录。
成功：在末尾保存 item 的副本，数量加一，返回 true。
失败：列表保持原状，返回 false。 */
bool list_append(List *list, Film item);
还应明确：是否允许重复；容量是否有限；输出参数在失败时是否保持不变；回调能否修改容器；保存的是副本还是借用的地址。
“指针不为空”只是前提的一部分，还要求它指向有效对象，并且对象已经正确初始化。
3.3 初始化和清空不等价
初始化把尚未建立内容的对象设置为空；清空释放它已经拥有的资源，然后恢复为空。
对非空容器再次执行“直接把指针写成 NULL”的初始化，会丢失旧节点并造成内存泄漏。复用一个容器时，应先调用清空操作。
3.4 为什么接口经常统一接收地址
void list_init(List *list);
bool list_empty(const List *list);
size_t list_count(const List *list);
修改容器需要通过地址影响调用者的对象。只读操作也接收地址，可以避免复制整个结构，并让调用方式一致。
小结构按值传递也可以，但需要明确：复制含有指针的结构只复制指针值，不会自动复制节点。对这个浅副本执行释放，仍会影响原对象引用的节点。
3.5 typedef 与 const 要一起看
typedef Node *ListHandle;
此时 const ListHandle *p 相当于 Node * const *p：不能经由 p 改写那个头指针，但节点内容仍可修改。
即使使用 const List * 指向一个容器结构，也不能自动使结构中所有指针指向的节点变成只读。实现只读遍历时，仍可主动使用 const Node * 限制访问。
3.6 文件分工与隐藏程度
film_list.h：类型名、函数原型、使用约定、包含保护
film_list.c：结构操作、内存管理、static 辅助函数
app.c：获取输入，调用接口，显示结果
static 辅助函数只在所在翻译单元中可见，不是“同文件夹内可见”。
如果头文件公开 List 和 Node 的全部成员，调用者在语法上仍能直接访问它们。此时的数据隐藏依赖接口约定；改变结构布局后，相关源文件通常需要重新编译。
需要更强的隐藏时，可以在头文件只声明不完整类型：
typedef struct film_list FilmList;
FilmList *film_list_create(void);
void film_list_destroy(FilmList *list);
完整结构放在实现文件。调用者只能通过指针和接口操作，也不能在不知道结构大小的情况下直接定义一个 FilmList 对象。
4. 一个完整的电影列表实现
下面把接口和实现放在一个文件中，便于观察完整流程。实际项目中可以按照上一节拆分。
列表拥有节点，记录按值复制；片名必须以空字符结尾，评分为 0～10。追加失败时不改变列表。
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
char title[64];
int rating;
} Film;
typedef struct node {
Film item;
struct node *next;
} Node;
typedef struct {
Node *head;
Node *tail;
size_t size;
} List;
static void list_init(List *list)
{
*list = (List){NULL, NULL, 0};
}
static bool list_append(List *list, Film item)
{
if (list->size == SIZE_MAX || item.rating < 0 || item.rating > 10 ||
memchr(item.title, '\0', sizeof item.title) == NULL) {
return false;
}
Node *fresh = malloc(sizeof *fresh);
if (fresh == NULL) {
return false;
}
*fresh = (Node){item, NULL};
if (list->tail == NULL) {
list->head = fresh;
} else {
list->tail->next = fresh;
}
list->tail = fresh;
++list->size;
return true;
}
static void list_visit(const List *list,
void (*visit)(const Film *, void *), void *context)
{
for (const Node *p = list->head; p != NULL; p = p->next) {
visit(&p->item, context);
}
}
static void list_clear(List *list)
{
Node *p = list->head;
while (p != NULL) {
Node *next = p->next;
free(p);
p = next;
}
list_init(list);
}
static void print_film(const Film *film, void *context)
{
FILE *out = context;
fprintf(out, "%s: %d\n", film->title, film->rating);
}
int main(void)
{
List movies;
const Film input[] = {{"Arrival", 9}, {"Soul", 8}, {"Dune", 9}};
list_init(&movies);
for (size_t i = 0; i < sizeof input / sizeof input[0]; ++i) {
if (!list_append(&movies, input[i])) {
fputs("cannot append film\n", stderr);
list_clear(&movies);
return EXIT_FAILURE;
}
}
list_visit(&movies, print_film, stdout);
printf("count: %zu\n", movies.size);
list_clear(&movies);
printf("after clear: %zu\n", movies.size);
return EXIT_SUCCESS;
}
输出：
Arrival: 9
Soul: 8
Dune: 9
count: 3
after clear: 0
context 是传给回调的附加状态，这里是输出流。这样同一个遍历函数既可以显示记录，也可以执行统计等其他任务。
回调接收的 const Film * 是对内部记录的临时只读借用，不能释放它。该接口还约定：遍历期间回调不得增加、删除或清空当前列表，否则遍历指针可能失效。
4.1 用不变量检查实现
不变量指容器在每次公开操作完成后必须满足的关系：
- 空表：
size == 0，且head == NULL、tail == NULL。 - 非空表：首尾指针有效，
tail->next == NULL。 - 从
head沿next能走过恰好size个节点，最后一个就是tail。 - 节点没有环，每个节点由这个列表负责释放一次。
头尾指针和计数让追加、读取数量都变成 O(1)，但也增加了必须同步维护的状态。
4.2 “是否已满”不能代替实际分配检查
固定容量容器可以根据数量判断是否达到上限。没有固定上限的动态链表则没有一个稳定的“剩余节点容量”。
先试着 malloc() 再立刻 free()，只能说明那一次分配是否成功，不能保证后面的实际分配成功。直接让追加操作尝试分配，并返回真实结果，通常更清楚。
底层容器也不一定要在失败时调用 exit()。返回错误可以让调用者决定重试、保存数据、清理资源或结束程序。
5. 队列：只从尾部加入，从头部取出
队列的核心约定是先进先出，即 FIFO。先进入的元素先离开。
出队 ← front → [A] → [B] → [C] ← rear ← 入队
队列的常见操作是初始化、判断空或满、读取数量、入队、出队和清空。队列描述取放顺序，既可以用链表实现，也可以用数组实现。
5.1 出队需要同时返回状态与数据
bool queue_pop(Queue *queue, int *out);
返回 true 表示取出成功，实际元素写入 *out。空队列返回 false，本例约定不改变输出对象。
不能拿某个普通整数作为“空队列”的标记，因为那个整数本身也可能是合法数据。
out 必须指向一个有效、可写的独立对象，不能指向将被释放的节点内部。用一个局部变量接收结果最直观。
5.2 入队与出队的边界
入队要处理空队列：第一个节点既是首节点，也是尾节点。
出队要处理只剩一个节点：移走该节点后，必须同时把首尾指针恢复为 NULL，不能留下指向已释放内存的尾指针。
有容量上限的链式队列有两种不同失败原因：达到逻辑上限、节点分配失败。下面用 false 统一表示失败；需要区分原因时，可以使用错误枚举。
5.3 完整的链式整数队列
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct qnode {
int item;
struct qnode *next;
} QNode;
typedef struct {
QNode *front;
QNode *rear;
size_t size;
size_t capacity;
} Queue;
static void queue_init(Queue *q, size_t capacity)
{
*q = (Queue){NULL, NULL, 0, capacity};
}
static bool queue_push(Queue *q, int item)
{
if (q->size >= q->capacity) {
return false;
}
QNode *fresh = malloc(sizeof *fresh);
if (fresh == NULL) {
return false;
}
*fresh = (QNode){item, NULL};
if (q->front == NULL) {
q->front = fresh;
} else {
q->rear->next = fresh;
}
q->rear = fresh;
++q->size;
return true;
}
static bool queue_pop(Queue *q, int *out)
{
if (q->front == NULL) {
return false;
}
QNode *old = q->front;
*out = old->item;
q->front = old->next;
--q->size;
if (q->front == NULL) {
q->rear = NULL;
}
free(old);
return true;
}
static void queue_clear(Queue *q)
{
int discarded;
while (queue_pop(q, &discarded)) {
/* 出队操作已经负责释放节点。 */
}
}
int main(void)
{
Queue q;
int value;
const int input[] = {40, 20, 55};
queue_init(&q, 3);
for (size_t i = 0; i < sizeof input / sizeof input[0]; ++i) {
if (!queue_push(&q, input[i])) {
queue_clear(&q);
return EXIT_FAILURE;
}
}
printf("extra accepted: %d\n", queue_push(&q, 99));
while (queue_pop(&q, &value)) {
printf("%d\n", value);
}
printf("remaining: %zu\n", q.size);
queue_clear(&q);
return EXIT_SUCCESS;
}
输出：
extra accepted: 0
40
20
55
remaining: 0
入队和出队只修改固定数量的链接，结构操作是 O(1)。这里的分析没有把通用内存分配器的内部成本视为固定的标准保证。
清空需要访问并释放全部节点，因此是 O(n)。清空后的队列仍保留原来的容量设置，可以继续入队。
6. 环形数组队列：移动边界，不搬动元素
如果普通数组每次出队都把后面的元素向前移动，出队就是 O(n)。另一种方式是记录首元素下标，取出后只移动这个下标。
当下标走到数组末尾时，让它回到开头，就能复用前面空出来的位置。这就是环形队列。
容量 4，逻辑队列是 C、D、E：
物理下标： 0 1 2 3
数组内容： [E] [空] [C] [D]
↑
front
逻辑第 i 项的位置：(front + i) % capacity
下一次入队的位置：(front + size) % capacity
这里用 size 区分满和空，所以容量为 4 的数组可以保存 4 项。其他实现可能保留一个空槽，规则不能混用。
6.1 一个不需要逐项分配的实现
#include <stdbool.h>
#include <stdio.h>
enum { CAPACITY = 4 };
typedef struct {
int data[CAPACITY];
size_t front;
size_t size;
} Ring;
static bool ring_push(Ring *q, int value)
{
if (q->size == CAPACITY) {
return false;
}
size_t pos = (q->front + q->size) % CAPACITY;
q->data[pos] = value;
++q->size;
return true;
}
static bool ring_pop(Ring *q, int *out)
{
if (q->size == 0) {
return false;
}
*out = q->data[q->front];
q->front = (q->front + 1) % CAPACITY;
--q->size;
return true;
}
int main(void)
{
Ring q = {0};
int value;
for (int i = 1; i <= CAPACITY; ++i) {
if (!ring_push(&q, i)) {
return 1;
}
}
printf("full rejects: %d\n", !ring_push(&q, 99));
for (int i = 0; i < 2; ++i) {
if (!ring_pop(&q, &value)) {
return 1;
}
printf("out: %d\n", value);
}
if (!ring_push(&q, 5) || !ring_push(&q, 6)) {
return 1;
}
while (ring_pop(&q, &value)) {
printf("out: %d\n", value);
}
return 0;
}
最终出队顺序仍然是 1、2、3、4、5、6。数组中的实际位置已经绕回，逻辑上的 FIFO 顺序没有变化。
本例容量很小，front + size 不会溢出。把实现推广到任意超大容量时，还要处理下标加法的溢出，不能只认为取模会修正已经溢出的结果。
| 实现 | 入队与出队的结构成本 | 主要代价 |
|---|---|---|
| 每次出队都搬移的数组 | 入队 O(1)，出队 O(n) | 反复移动元素 |
| 环形数组 | 都是 O(1) | 预留容量，管理环绕下标 |
| 保存首尾指针的链表 | 都是 O(1) | 节点指针、逐项分配与释放 |
7. 用队列模拟等待服务
队列可以表示等待咨询、购票或处理任务的人。容器解决先后顺序；模拟程序负责时间和业务规则。
7.1 保存的是顾客状态
typedef struct {
long arrive;
int service_minutes;
} Customer;
顾客开始服务时：
等待时间 = 开始服务的时刻 - 到达时刻
正在接受服务的顾客已经离开等待队列。因此，“队列长度”只计算等待的人，不包括服务中的人。
把整数队列改成顾客队列时，节点的元素类型以及相关参数、输出变量都要统一改成 Customer。这属于编译时替换类型；一个 typedef Item 并不会自动产生可同时储存任意类型的容器。
7.2 明确每分钟的事件顺序
一种离散时间模型可以写成：
每一分钟 t：
判断是否有新顾客到来
等待队列已满 → 记录被拒人数
否则 → 记录到达时间与服务时长，加入队列
如果服务员空闲，且队列非空：
从队首取出顾客
累计 t - arrive
设置剩余服务时间
开始服务人数加一
如果正在服务：
剩余服务时间减一
若减到零，完成服务人数加一
累计当前等待队列长度
这里先接收新顾客，再选择下一位开始服务，所以空闲时新顾客可能立即开始服务，等待时间为零。队满时的拒绝判断也发生在本轮取人之前。
这是模型的规则。改变事件顺序，边界时刻的统计也可能改变，应该先确定语义，再写代码。
7.3 统计量要用正确的分母
| 统计量 | 一种明确的计算方式 |
|---|---|
| 平均等待人数 | 每轮记录的等待人数总和 / 模拟轮数 |
| 已开始服务者的平均等待时间 | 这些顾客的等待时间总和 / 开始服务人数 |
| 接纳人数 | 成功入队的顾客数量 |
| 拒绝人数 | 因等待队列已满而未接纳的数量 |
| 完成服务人数 | 剩余服务时间减到零的次数 |
从队列取出一个顾客时，只能说明他开始接受服务，不能说明整个服务已经完成。模拟结束时，可能还有人在排队，也可能有人仍在接受服务。
如果没有顾客开始服务，平均等待时间的分母为零，应单独处理。模拟时长也必须大于零。
在没有顾客中途离开的模型中，应满足：
到达人数 = 接纳人数 + 拒绝人数
接纳人数 = 等待人数 + 已开始服务人数
已开始服务人数 = 已完成人数 + 正在服务人数
最后一项“正在服务人数”对单服务台是 0 或 1。
7.4 每分钟最多一人到达的限制
如果每小时平均到达 r 人，每分钟到达一人的概率可以设为 p = r / 60.0。这种模型要求 0 <= r <= 60，每分钟只进行一次是否到达的判断。
/* 已包含 <stdlib.h>；p 已检查在 [0, 1] 内。 */
double u = (double)rand() / ((double)RAND_MAX + 1.0);
bool arrives = u < p;
分母写成浮点数形式，避免先计算整数 RAND_MAX + 1 可能溢出。这个简单方案受到伪随机数离散精度限制，适合教学模拟。
如果输入每小时 120 人却仍每分钟只尝试生成一人，模型无法表达需求。需要缩短步长，或采用允许一个时间段内多次到达的模型。
服务时长用 rand() % 3 + 1 可得到 1、2、3 分钟；由于取模可能存在轻微偏差，它不是对任意实现都严格均匀的保证。
7.5 从结果理解负载
如果三种服务时长等概率，平均每人需要 2 分钟，一个服务台的平均工作能力约为每小时 30 人。
到达率接近这个水平时，随机波动容易形成长队；有容量上限时，多余需求表现为拒绝。即使平均到达率低于服务能力，也不代表任何时刻都无人等待。
应对多服务台时，可以选择共用一个队列，也可以为每个服务台分配队列。分配规则、每个服务台的忙闲状态和统计口径都属于模型的一部分。
固定随机种子有利于重现同一实现中的一次实验；不同 C 库不保证生成相同序列。比较模型时，宜观察多次运行结果和结束时的未完成工作，而不是只看一次短时间运行。
8. 数组和链表：把查找位置的成本算进去
| 操作 | 连续数组 | 单向链表 |
|---|---|---|
| 根据下标访问第 k 项 | O(1) | O(k)，最坏 O(n) |
| 遍历全部元素 | O(n)，通常具有较好的局部性 | O(n)，节点可能分散 |
| 在已知位置中间插入并保持顺序 | 最坏移动 O(n) 项 | 已知前驱时，链接修改 O(1) |
| 删除指定位置并保持顺序 | 最坏移动 O(n) 项 | 已知前驱或入口链接时，链接修改 O(1) |
| 按值查找，未排序 | O(n) | O(n) |
| 已排序时二分查找 | O(log n) | 无法靠下标直接跳到中间 |
上表的链表插入、删除没有把节点分配、释放的内部成本当作语言标准保证的常数。
“链表删除是 O(1)”有前提：已经掌握需要修改的链接。若只有待删除的值，还要先遍历查找，整个操作仍可能是 O(n)。
只有头指针时，每次追加都需要找尾部，连续追加 n 项总成本可能是 O(n²)。保存尾指针可以让这些链接操作合计为 O(n)。
动态数组通过成倍扩容，也可以实现平均摊销 O(1) 的追加，只是某次扩容可能搬动 O(n) 个元素，并使指向旧缓冲区的指针失效。
8.1 有序链表也可以提前停止查找
顺序扫描一个有序序列时，一旦当前元素已经大于目标，就可以确定目标不存在。这样可以省下一部分比较，但最坏情况依然是 O(n)。
链表并非在逻辑上完全不能做“比较中点、缩小范围”，而是寻找中点需要沿链接移动。没有额外索引时，它不能像数组二分查找那样获得 O(log n) 的总访问时间。
9. 二分查找：维护尚未排除的范围
二分查找要求数组已经按照查找时使用的同一规则排好序。
每次比较中间元素后，排除一半候选范围。若数据未排序，排除的那一半可能恰好包含目标，算法就不再正确。
9.1 使用左闭右开的区间
用 [lo, hi) 表示候选下标，即包含 lo，不包含 hi：
初始：lo = 0，hi = n
非空：lo < hi
中点：mid = lo + (hi - lo) / 2
a[mid] < target → lo = mid + 1
a[mid] > target → hi = mid
a[mid] == target → 找到
这样不需要表示下标 -1，也避免在空数组上计算 n - 1 导致无符号下溢。
lo + (hi - lo) / 2 比 (lo + hi) / 2 更稳妥：前者在 0 <= lo <= hi <= n 的约束下不会因为两个大下标相加而溢出。
9.2 完整示例
#include <stdbool.h>
#include <limits.h>
#include <stdio.h>
/* a 指向含 n 项的升序数组；n == 0 时允许 a == NULL。
index 可为 NULL；找不到时不修改 *index。 */
static bool binary_find(const int *a, size_t n, int target, size_t *index)
{
size_t lo = 0;
size_t hi = n;
while (lo < hi) {
size_t mid = lo + (hi - lo) / 2;
if (a[mid] < target) {
lo = mid + 1;
} else if (a[mid] > target) {
hi = mid;
} else {
if (index != NULL) {
*index = mid;
}
return true;
}
}
return false;
}
int main(void)
{
const int data[] = {INT_MIN, -4, 0, 7, 7, 19, INT_MAX};
const int targets[] = {7, 8, INT_MIN, INT_MAX};
for (size_t i = 0; i < sizeof targets / sizeof targets[0]; ++i) {
size_t index;
if (binary_find(data, sizeof data / sizeof data[0],
targets[i], &index)) {
printf("%d at %zu\n", targets[i], index);
} else {
printf("%d absent\n", targets[i]);
}
}
printf("empty found: %d\n", binary_find(NULL, 0, 7, NULL));
return 0;
}
重复元素存在时，这个版本返回命中的某一个位置，不保证是第一个。若需要第一个位置，应继续缩小到最左边的匹配边界。
每次迭代都减小候选区间，因此最终能够停止。时间复杂度是 O(log n)，额外空间为 O(1)。排序本身的成本需要另算；不能把“排序后再查找一次”的全部过程都算成 O(log n)。
10. 二叉查找树：把有序关系编码到链接里
二叉树的每个节点最多有两个子节点。二叉查找树，简称 BST，在此基础上增加顺序约束。
对于不允许重复键的版本，每个节点都必须满足：
左子树中的所有键 < 当前键 < 右子树中的所有键
约束作用于整棵子树，而不只是直接的左、右孩子。
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
根是整棵树的入口；子树是某个节点和它的全部后代；没有子节点的节点叫叶节点。空指针表示相应子树为空。
10.1 查找只沿一条路径前进
查找 7：与 8 比较向左，与 3 比较向右，与 6 比较向右，最后命中 7。
如果走到 NULL，说明应该容纳目标的路径已经结束，目标不在树里。
比较后可以排除另一棵子树，但不保证排除的是全部节点的一半。只有树的高度得到控制，才能保证较短的查找路径。
10.2 插入是在空链接处建立新节点
沿查找路径前进：键小就向左，键大就向右，相等则按重复策略处理。最终遇到空链接时，把新节点接在这里。
新节点的左右指针都应初始化为 NULL。如果分配失败，树的链接和数量应保持原状。
与先查重、再从根重新寻找插入位置相比，一次遍历直接找到“待写入的空链接”可以避免重复走路。
10.3 比较规则是容器定义的一部分
宠物记录可以先比较名字，名字相同再比较种类：
/* Pet 的 name、kind 都是有效的 C 字符串。 */
static int pet_compare(const Pet *a, const Pet *b)
{
int result = strcmp(a->name, b->name);
return result != 0 ? result : strcmp(a->kind, b->kind);
}
名字和种类都相同，才视为同一个键。若只按名字比较，“同名不同种类”也会变成重复项。
插入、查找和删除必须使用一致的比较规则。记录已经入树后，不能直接修改参与排序的字段；需要先移除旧键，再插入新键。
strcmp() 返回值看正、负、零即可，不保证恰好为 1 或 -1。比较整数时直接用 < 和 >，避免用相减的结果判断大小而发生有符号溢出。
11. 删除树节点：先保证剩余节点仍能找到
11.1 没有子节点
把指向它的链接改为 NULL，再释放节点。
11.2 只有一个子树
把指向它的链接改成指向唯一的子树根，再释放旧节点。整个子树的位置随入口变化，内部节点不需要逐个移动。
11.3 同时有左右子树
一种直接重接子树的方法是：
- 找到左子树最右边的节点，也就是左子树中最大的键。
- 把旧右子树接到这个节点的空右链接上。
- 用旧左子树替换被删节点的位置。
- 释放被删节点。
删除下图中的 8：
删除前： 删除后：
8 3
/ \ / \
3 10 1 6
/ \ / \
1 6 4 7
/ \ \
4 7 10
这个连接是合法的，因为旧右子树的所有键都大于被删键，也就大于旧左子树的所有键。
另一种常见方法是用中序前驱或后继的记录替换目标记录，再删除相应的前驱或后继节点。涉及动态字符串等资源时，记录替换还必须遵守所有权约定。
11.4 二级指针表示“应该修改的链接”
需要修改的可能是：
tree->root
parent->left
parent->right
它们的类型都是 TreeNode *；取地址以后，类型都是 TreeNode **。因此可以用同一套逻辑处理根节点和普通子节点。
TreeNode **link = &tree->root;
此时 link 指向一个指针对象，*link 才是当前节点。向下走时：
link = &(*link)->left;
找到目标后，给 *link 赋值，就会实际修改树的入口或父节点的孩子指针。与保存“父节点、当前节点”两个指针相比，这是另一种表达同一修改需求的方法。
12. 一个完整的整数二叉查找树
下面的树不允许重复键，设置容量上限，并分别报告重复、已满和分配失败。所有操作要求传入有效的树对象；遍历回调不得修改这棵树。
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct tree_node {
int key;
struct tree_node *left;
struct tree_node *right;
} TreeNode;
typedef struct {
TreeNode *root;
size_t size;
size_t capacity;
} Tree;
typedef enum {
INSERTED, DUPLICATE, TREE_FULL, NO_MEMORY
} InsertResult;
static void tree_init(Tree *tree, size_t capacity)
{
*tree = (Tree){NULL, 0, capacity};
}
static bool tree_contains(const Tree *tree, int key)
{
const TreeNode *p = tree->root;
while (p != NULL) {
if (key == p->key) {
return true;
}
p = key < p->key ? p->left : p->right;
}
return false;
}
static InsertResult tree_insert(Tree *tree, int key)
{
TreeNode **link = &tree->root;
while (*link != NULL) {
if (key == (*link)->key) {
return DUPLICATE;
}
link = key < (*link)->key ? &(*link)->left : &(*link)->right;
}
if (tree->size >= tree->capacity) {
return TREE_FULL;
}
TreeNode *fresh = malloc(sizeof *fresh);
if (fresh == NULL) {
return NO_MEMORY;
}
*fresh = (TreeNode){key, NULL, NULL};
*link = fresh;
++tree->size;
return INSERTED;
}
static bool tree_erase(Tree *tree, int key)
{
TreeNode **link = &tree->root;
while (*link != NULL && (*link)->key != key) {
link = key < (*link)->key ? &(*link)->left : &(*link)->right;
}
if (*link == NULL) {
return false;
}
TreeNode *old = *link;
if (old->left == NULL) {
*link = old->right;
} else if (old->right == NULL) {
*link = old->left;
} else {
TreeNode *max_left = old->left;
while (max_left->right != NULL) {
max_left = max_left->right;
}
max_left->right = old->right;
*link = old->left;
}
free(old);
--tree->size;
return true;
}
static void inorder(const TreeNode *p,
void (*visit)(int, void *), void *context)
{
if (p == NULL) {
return;
}
inorder(p->left, visit, context);
visit(p->key, context);
inorder(p->right, visit, context);
}
static void free_nodes(TreeNode *p)
{
if (p == NULL) {
return;
}
free_nodes(p->left);
free_nodes(p->right);
free(p);
}
static void tree_clear(Tree *tree)
{
free_nodes(tree->root);
tree->root = NULL;
tree->size = 0;
}
static void print_key(int key, void *context)
{
FILE *out = context;
fprintf(out, "%d ", key);
}
int main(void)
{
Tree tree;
const int keys[] = {8, 3, 10, 1, 6, 14, 4, 7, 13};
const int removed[] = {3, 14, 1, 8};
tree_init(&tree, 9);
for (size_t i = 0; i < sizeof keys / sizeof keys[0]; ++i) {
if (tree_insert(&tree, keys[i]) != INSERTED) {
tree_clear(&tree);
return EXIT_FAILURE;
}
}
printf("duplicate rejected: %d\n", tree_insert(&tree, 8) == DUPLICATE);
printf("full rejected: %d\n", tree_insert(&tree, 2) == TREE_FULL);
inorder(tree.root, print_key, stdout);
putchar('\n');
for (size_t i = 0; i < sizeof removed / sizeof removed[0]; ++i) {
if (!tree_erase(&tree, removed[i])) {
tree_clear(&tree);
return EXIT_FAILURE;
}
}
inorder(tree.root, print_key, stdout);
putchar('\n');
printf("contains 7: %d; contains 8: %d\n",
tree_contains(&tree, 7), tree_contains(&tree, 8));
printf("erase absent: %d; count: %zu\n",
tree_erase(&tree, 99), tree.size);
tree_clear(&tree);
return EXIT_SUCCESS;
}
输出：
duplicate rejected: 1
full rejected: 1
1 3 4 6 7 8 10 13 14
4 6 7 10 13
contains 7: 1; contains 8: 0
erase absent: 0; count: 5
示例依次删除了两个子树的节点、一个子树的节点、叶节点和根节点。找不到目标时，不修改链接和计数。
清空后保留容量设置。这个实现只让树拥有整数节点；若节点记录另有动态资源，释放节点前还需要释放记录自身拥有的资源。
13. 树的遍历与清空
每个节点有两个分支，递归很自然地对应“对左子树做同样的事、处理当前节点、对右子树做同样的事”。
| 遍历方式 | 访问顺序 | 常见用途 |
|---|---|---|
| 前序 | 当前节点 → 左子树 → 右子树 | 先处理上层，再处理后代 |
| 中序 | 左子树 → 当前节点 → 右子树 | 按 BST 的键顺序输出 |
| 后序 | 左子树 → 右子树 → 当前节点 | 先释放后代，再释放父节点 |
中序遍历能输出升序序列，依赖于 BST 的顺序不变量；对任意二叉树，中序结果不一定有序。
三种遍历都访问每个节点一次，因此时间为 O(n)。递归调用所需的额外空间是 O(h)，其中 h 是树高。
13.1 清空时的有效访问顺序
完整示例使用后序释放：先清空左右子树，再释放当前节点。读取 p->left、p->right 时，p 仍然有效。
也可以先释放左子树，再释放当前节点，最后处理右子树，但必须在释放当前节点之前保存右子树地址。不能释放父节点以后，再通过父节点读取孩子指针。
13.2 空树与空的树指针不同
Tree tree;
tree_init(&tree, 20);
这是一个有效的空树对象，tree.root == NULL。但 Tree *p = NULL 根本没有指向树对象。
如果接口允许传入空的树指针，必须在解引用前完整处理：
if (tree == NULL) {
return;
}
只给递归释放加上空指针判断，然后无条件执行 tree->root = NULL，并不能防止空指针解引用。本笔记中的完整实现采用更简单的接口前提：树对象的地址必须有效。
14. 树高决定查找效率
BST 的查找、插入和删除主要沿树的路径进行，成本都与树高 h 有关。
| 树的形状 | 树高 | 查找、插入、删除 |
|---|---|---|
| 高度保持平衡 | O(log n) | O(log n) |
| 普通 BST 的最坏情况 | O(n) | O(n) |
若依次插入 1、2、3、4、5，普通 BST 可能变成：
1
\
2
\
3
\
4
\
5
查找 5 要经过所有节点。此时它在搜索路径上已经接近单向链表。
输入顺序会影响树形。普通 BST 不会自动保持平衡；随机顺序在适当假设下有较好的期望高度，但不是对所有输入的保证。
14.1 满、完全、平衡不是同一概念
对于一棵有 h 层的二叉树，最多有 2^h - 1 个节点，这对应每层都被填满的情况。
平衡强调路径高度受到约束，不要求节点填满每一层，也不要求左右子树节点数量完全相等。高效查找需要控制高度，不需要等待树“满员”。
14.2 平衡树增加了维护工作
AVL 树会维护各节点左右子树高度差不超过 1，并在插入、删除后通过调整链接恢复平衡。这样可以保证树高为 O(log n)。
代价是实现更复杂，需要额外状态和维护步骤。普通 BST 更适合用来理解有序链接、查找路径与删除重接，不能直接把它当作已有最坏情况效率保证的索引。
递归遍历和清空也受树高影响。退化树可能产生很深的递归；处理规模大或输入不可控的数据时，应考虑平衡机制或适当的非递归实现。
15. 重复数据：键与记录不一定一一对应
“不允许重复”只是某个容器的策略，并不是树的必然属性。需要先说明什么算相同，以及重复时如何处理。
15.1 词频：一个键对应计数
typedef struct {
char word[64];
size_t count;
} WordCount;
键是 word，count 是这个键关联的数据。第一次出现时插入节点并设为 1；再次出现时找到同一节点并增加计数。
比较时不能把 count 算进键，否则同一个单词在计数变化以后就可能改变排序位置。
这还需要明确单词边界、大小写规则、超长词处理以及计数溢出规则。数据结构负责保存与查找，文本解析负责判定哪些输入表示同一个词。
15.2 同名宠物：一个键对应多个记录
如果名字是树的键，同名宠物的种类可以放进该节点管理的列表：
名字索引树
↓
"Sam" → [猫] → [狗] → [山羊]
树负责按名字定位，列表负责管理这个名字对应的多条记录。这是把两种数据结构组合使用。
需要区分“删除 Sam 的一条记录”和“删除整个 Sam 节点”：删除某个种类后，如果列表为空，才可能继续移除名字节点。释放整个树时，每个节点内部的列表也要清空。
16. 从单向链表扩展到双向链表和栈
16.1 双向链表增加前驱链接
typedef struct dnode {
Film item;
struct dnode *previous;
struct dnode *next;
} DNode;
保存尾指针后，可以从尾部沿 previous 反向遍历。插入和删除时，必须同时维护两个方向的链接，以及首尾边界。
已知某个有效节点时，双向链表通常可以直接取得它的前驱；单向链表若只给节点地址，通常还要从头寻找前驱。增加的能力需要额外指针空间和维护成本。
单向链表也可以借助递归实现逆序显示：先处理后继，再显示当前记录。这不改变链接，但需要 O(n) 层调用空间，不适合无界长度。
16.2 栈限制在同一端取放
栈是后进先出，即 LIFO。后压入的元素先弹出。
push A → push B → push C
pop 的顺序：C、B、A
它可以由数组实现，也可以用单向链表的头部实现。链式实现把头指针作为栈顶，压入与弹出都只操作头部，不需要寻找尾部。
栈的接口通常包括初始化、判空、判满、压入、弹出、查看栈顶与清空。弹出和出队一样，可以通过返回值报告成功与否，通过输出参数传出数据。
用栈反转字符时，逐个压入，再逐个弹出即可。若处理的是 UTF-8 中文，逐字节反转会破坏编码；需要先明确元素代表字节、Unicode 码点，还是用户看到的完整字符。
17. 接口边界、资源与输入处理
17.1 容器拥有资源时不能随意浅复制
List first;
list_init(&first);
/* 向 first 添加记录后…… */
List second = first;
这不会复制节点。两个容器的头尾指针会指向同一组节点，分别清空它们可能导致重复释放。
如果需要独立副本，应逐项分配并复制；中途失败时还要清理已经复制的部分。如果需要转移所有权，转移完成后应把原容器恢复为空，并明确这种操作的接口。
17.2 替换实现仍需保持行为约定
一个列表可以由链表改成数组，但如果原来允许持续追加，新的固定容量实现却只能存 100 项，这就是可观察的行为差异。
接口不变只能减少调用代码的修改。要做到可替换，还需要兼容容量、失败、顺序、重复处理和指针有效期等约定。
同样，把 Item 改成另一种类型，并不总能只改一行 typedef：比较、复制、销毁和格式化输出是否依赖元素类型，都需要检查。
17.3 输入循环必须能处理 EOF
int ch;
while ((ch = getchar()) != '\n' && ch != EOF) {
/* 丢弃当前行剩余内容。 */
}
只等换行而不检查 EOF，可能在输入已经结束时永远循环。getchar() 的结果应先保存在 int 中，以区分所有字符值和 EOF。
交互程序读取菜单、评分和名称时，都要检查读取是否成功。数字可用 fgets() 读整行后再解析，确认范围与末尾内容合法，避免错误输入污染下一轮。
大小写归一化也要一致：插入、查找、删除都使用同一种规则。调用字符分类和转换函数时，用 toupper((unsigned char)*p) 等形式避免把负的普通 char 值直接作为参数；这类逐字节处理也不等于完整的 Unicode 大小写转换。
17.4 调试容器时优先观察不变量
链表重点观察头尾关系、实际节点数、末尾空链接和是否成环。队列重点观察空队列、单节点队列、满队列及反复入出队后的状态。BST 还要检查所有后代的排序范围，而不仅是每对父子节点。
分配失败应当发生在“原结构尚未被破坏”的位置。删除成功后检查计数，删除不存在的项时检查原内容，清空后检查是否能再次使用。
调试输出不应通过解引用已经释放的节点来确认释放结果。内存检查工具可以帮助发现越界、释放后访问和重复释放，但接口约定与所有权仍需在设计阶段说明。
18. 按操作需求选择表示方式
| 主要需求 | 可优先考虑 | 需要留意 |
|---|---|---|
| 经常通过下标读取 | 连续数组或动态数组 | 扩容及中间插入的移动成本 |
| 顺序遍历，已知位置频繁插入删除 | 链表 | 定位成本、节点额外空间 |
| 固定容量、先进先出 | 环形数组队列 | 满空判定与下标环绕 |
| 按需分配、先进先出 | 保存首尾指针的链式队列 | 分配失败与首尾边界 |
| 按键查找并保持有序 | 二叉查找树 | 普通 BST 的退化风险 |
| 后进先出 | 栈 | 栈顶边界和容量规则 |
先明确数据的含义、允许的操作和失败规则，再选择能让这些操作简单可靠的表示。接口负责稳定地表达需求，实现负责维护链接、顺序和资源，不变量负责把两者连接起来。