第20章 数组版数据库
20.1 问题从哪来#
前面几章学了结构体、数组、指针、函数，也开始用测试和不变量检查程序。用结构体能表示一个学生，用数组能存一批学生，用函数能把逻辑拆开。
但这些能力分散在不同的小程序里。每次写一个新功能，就得在 main 里重新声明数组、重新写循环、重新管理 count。如果要同时管理两份学生名单，比如一班和二班，就得复制一份数组和一份计数器。
上一章还留了一个提醒：程序不只是能跑，还要守住自己的边界。这里最重要的边界就是 count：它不能小于 0，也不能超过数组容量；插入、查找、删除、列出都只能围着有效记录转。
能不能把这些数据和操作打包在一起，让"数据库"变成一个独立的东西？
20.2 先看一个例子#
假设有一个程序，用户做了这几步操作：
- 插入学号 1，Alice，92 分。
- 插入学号 2，Bob，78 分。
- 插入学号 3，Carol，85 分。
- 按学号 2 查找，找到 Bob。
- 删除学号 2。
- 列出所有学生，只剩 Alice 和 Carol。
这几步的关键变化，是 rows 里有效记录的范围和 count 一起移动：
插入时新记录写到 rows[count]，然后 count 加一。查找只读数组，不改变 count。删除时找到那条记录，把后面的记录往前挪一格，再让 count 减一。列出时只读 count 以内的记录。
20.3 最小实验#
数据库的核心结构只有两样东西：一个数组，一个计数器。
#define DB_CAPACITY 100
struct Student {
int id;
char name[32];
int score;
};
struct DB {
struct Student rows[DB_CAPACITY]; // 最多 100 条记录
int count; // 当前有多少条
};
rows 是一个长度为 100 的数组，每个元素是一个 struct Student。count 记录当前有多少条有效数据。下标小于 count 的位置属于有效记录；从 count 开始的位置暂时不读，里面可能还保留着旧值。
四个操作围绕 struct DB 展开，每个函数都接收一个 struct DB *db 参数：
20.3.1 插入#
// 插入一条记录，成功返回 1，表满返回 0
int db_insert(struct DB *db, int id, const char *name, int score)
{
if (db->count >= DB_CAPACITY) {
return 0; // 表满了
}
struct Student *s = &db->rows[db->count]; // 指向下一个空位
s->id = id;
snprintf(s->name, sizeof(s->name), "%s", name);
s->score = score;
db->count = db->count + 1; // 计数器加一
return 1;
}
插入先用 count 找到下一个空位，再把新记录写进去，最后把 count 往后移一格。新记录永远追加在已有数据的后面。
20.3.2 查找#
// 按学号查找，找到返回该记录的指针，没找到返回 NULL
struct Student *db_find(struct DB *db, int id)
{
for (int i = 0; i < db->count; i++) {
if (db->rows[i].id == id) {
return &db->rows[i]; // 找到了，返回指针
}
}
return NULL; // 没找到
}
查找从第 0 条开始，逐条比对学号。找到了就返回那条记录的地址，找不到就返回 NULL。最坏情况要把所有记录都扫一遍。
20.3.3 删除#
// 按学号删除，成功返回 1，没找到返回 0
int db_delete(struct DB *db, int id)
{
int found = -1;
for (int i = 0; i < db->count; i++) {
if (db->rows[i].id == id) {
found = i; // 记住位置
break;
}
}
if (found == -1) {
return 0; // 没找到
}
// 把后面的元素往前挪一格
for (int j = found; j < db->count - 1; j++) {
db->rows[j] = db->rows[j + 1];
}
db->count = db->count - 1; // 计数器减一
return 1;
}
删除函数先从头比较 rows[0]、rows[1]，找到 Bob 的位置以后，把 found 设成 1。
找到目标以后，第二个循环执行 rows[1] = rows[2]，让 Carol 补到空位。最后 count 减一，后面的旧内容不再算记录。
20.3.4 列出全部#
// 打印所有记录
void db_list(struct DB *db)
{
if (db->count == 0) {
printf("Database is empty.\n");
return;
}
printf("ID Name Score\n");
printf("------------------------\n");
for (int i = 0; i < db->count; i++) {
printf("%-6d%-12s%d\n",
db->rows[i].id,
db->rows[i].name,
db->rows[i].score);
}
printf("------------------------\n");
printf("Total %d records.\n", db->count);
}
列出就是遍历 rows[0] 到 rows[count-1]，逐条打印。循环条件是 i < db->count，不是 i < 100，这样只输出有效数据。
20.3.5 接上菜单循环#
把插入、查找、删除、列出四个函数接到菜单循环里。菜单本身不是重点，重点是每个选项最后调用哪一个数据库函数：
| 菜单项 | 读入内容 | 调用 |
|---|---|---|
| 1-插入 | id、name、score | db_insert(&db, id, name, score) |
| 2-查找 | id | db_find(&db, id) |
| 3-删除 | id | db_delete(&db, id) |
| 4-列出 | 无 | db_list(&db) |
| 0-退出 | 无 | break |
可以先让 main 只支持插入和列出，确认 count 正确变化；再加查找；最后加删除。每加一个菜单项，都只检查一件事：这个分支有没有把输入转换成一次数据库函数调用。
20.4 编译运行#
把前面的结构体和函数接到一个小菜单里，就能得到一份完整的 db.c。先看完整程序，运行时再对照上面的四个函数。
#include <stdio.h>
#define DB_CAPACITY 100
struct Student {
int id;
char name[32];
int score;
};
struct DB {
struct Student rows[DB_CAPACITY]; // 最多 100 条记录
int count; // 当前有多少条
};
// 插入一条记录，成功返回 1，表满返回 0
int db_insert(struct DB *db, int id, const char *name, int score)
{
if (db->count >= DB_CAPACITY) {
return 0; // 表满了
}
struct Student *s = &db->rows[db->count]; // 指向下一个空位
s->id = id;
snprintf(s->name, sizeof(s->name), "%s", name);
s->score = score;
db->count = db->count + 1; // 计数器加一
return 1;
}
// 按学号查找，找到返回该记录的指针，没找到返回 NULL
struct Student *db_find(struct DB *db, int id)
{
for (int i = 0; i < db->count; i++) {
if (db->rows[i].id == id) {
return &db->rows[i]; // 找到了，返回指针
}
}
return NULL; // 没找到
}
// 按学号删除，成功返回 1，没找到返回 0
int db_delete(struct DB *db, int id)
{
int found = -1;
for (int i = 0; i < db->count; i++) {
if (db->rows[i].id == id) {
found = i; // 记住位置
break;
}
}
if (found == -1) {
return 0; // 没找到
}
// 把后面的元素往前挪一格
for (int j = found; j < db->count - 1; j++) {
db->rows[j] = db->rows[j + 1];
}
db->count = db->count - 1; // 计数器减一
return 1;
}
// 打印所有记录
void db_list(struct DB *db)
{
if (db->count == 0) {
printf("Database is empty.\n");
return;
}
printf("ID Name Score\n");
printf("------------------------\n");
for (int i = 0; i < db->count; i++) {
printf("%-6d%-12s%d\n",
db->rows[i].id,
db->rows[i].name,
db->rows[i].score);
}
printf("------------------------\n");
printf("Total %d records.\n", db->count);
}
int main(void)
{
struct DB db;
db.count = 0; // 初始化计数器
while (1) {
int choice;
printf("1-Insert 2-Search 3-Delete 4-List 0-Exit\n");
printf("Choice: ");
if (scanf("%d", &choice) != 1) {
break; // 输入非法，退出程序
}
if (choice == 0) {
printf("Exited.\n");
break;
}
if (choice == 1) {
// 插入：读入学生信息，调用 db_insert
int id;
char name[32];
int score;
printf("ID: ");
scanf("%d", &id);
printf("Name: ");
scanf("%31s", name);
printf("Score: ");
scanf("%d", &score);
if (db_insert(&db, id, name, score)) {
printf("Inserted successfully. Total %d records.\n", db.count);
} else {
printf("Database full, insertion failed.\n");
}
} else if (choice == 2) {
// 查找：读入学号，调用 db_find
int id;
printf("Enter ID: ");
scanf("%d", &id);
struct Student *s = db_find(&db, id);
if (s != NULL) {
printf("Found: ID %d, Name %s, Score %d\n",
s->id, s->name, s->score);
} else {
printf("Not found.\n");
}
} else if (choice == 3) {
// 删除：读入学号，调用 db_delete
int id;
printf("Enter ID: ");
scanf("%d", &id);
if (db_delete(&db, id)) {
printf("Deleted successfully. Total %d records.\n", db.count);
} else {
printf("Not found, deletion failed.\n");
}
} else if (choice == 4) {
db_list(&db); // 列出全部记录
} else {
printf("Unknown option.\n");
}
printf("\n");
}
return 0;
}保存为 db.c，编译：
$ gcc db.c -o db
运行，依次操作：
1-Insert 2-Search 3-Delete 4-List 0-Exit
Choice:
$ 1
ID:
$ 1
Name:
$ Alice
Score:
$ 92
Inserted successfully. Total 1 records.
1-Insert 2-Search 3-Delete 4-List 0-Exit
Choice:
$ 1
ID:
$ 2
Name:
$ Bob
Score:
$ 78
Inserted successfully. Total 2 records.
1-Insert 2-Search 3-Delete 4-List 0-Exit
Choice:
$ 1
ID:
$ 3
Name:
$ Carol
Score:
$ 85
Inserted successfully. Total 3 records.
1-Insert 2-Search 3-Delete 4-List 0-Exit
Choice:
$ 2
Enter ID:
$ 2
Found: ID 2, Name Bob, Score 78
1-Insert 2-Search 3-Delete 4-List 0-Exit
Choice:
$ 3
Enter ID:
$ 2
Deleted successfully. Total 2 records.
1-Insert 2-Search 3-Delete 4-List 0-Exit
Choice:
$ 4
ID Name Score
------------------------
1 Alice 92
3 Carol 85
------------------------
Total 2 records.
1-Insert 2-Search 3-Delete 4-List 0-Exit
Choice:
$ 0
Exited.
删除 Bob 之后，Carol 从 rows[2] 挪到了 rows[1]，count 从 3 变成 2。列出时只打印前两条，Carol 不会丢失。
20.5 数据/内存/流程里发生了什么#
20.5.1 DB 结构在内存里的样子#
struct DB 包含一个数组和一个整数。数组在内存里是连续的一大片，每个元素紧挨着下一个：
count = 3 表示前三个位置有有效记录。后面的 97 个位置不属于当前数据库内容，程序不会把它们打印出来；至于里面的字节是什么，暂时不靠它们表达含义。
20.5.2 插入的流程#
插入学号 4，David，88 分：
检查 db->count 没有超过容量以后，s 指向 rows[3]。新记录写进这个位置，count 再从 3 变成 4。新记录总是追加在已有数据的末尾，不需要移动任何已有记录。
20.5.3 查找的流程#
查找学号 2：
第 1 轮看 rows[0]，Alice 的学号不是 2；第 2 轮看 rows[1]，Bob 的学号是 2，函数返回 &rows[1]。最多比较 count 次。如果要找的学号不在表里，整个循环走完，返回 NULL。
20.5.4 删除的流程#
删除学号 2（Bob）：
先查找目标学号，找到 Bob 在 rows[1]。然后执行 rows[1] = rows[2]，Carol 从位置 2 挪到位置 1。最后 count 从 3 变成 2。图里的 rows[2] 标成旧值，是因为数组没有自动擦除旧内容；程序只会访问 rows[0] 和 rows[1]，是 count 决定哪些位置还算数据库里的记录。
注意：移动元素这一步是删除操作最慢的地方。如果表里有 1 万条记录，删除第 1 条就要挪 9999 次。数组版数据库的删除效率取决于被删除记录的位置。
20.6 四个操作的复杂度#
| 操作 | 最好情况 | 最坏情况 | 说明 |
|---|---|---|---|
| 插入 | $O(1)$ | $O(1)$ | 总是写到末尾，不需要移动 |
| 查找 | $O(1)$ | $O(n)$ | 第一条就命中 vs 扫完全部 |
| 删除 | $O(1)$ | $O(n)$ | 表为空或只有一条时很快；一般要查找，找到后还可能移动后面的元素 |
| 列出 | $O(n)$ | $O(n)$ | 必须遍历全部 |
插入最快，因为它总是在末尾追加。查找需要从头扫描，这是线性查找的代价。删除也要先查找；如果删的是中间或靠前的位置，还要把后面的元素往前挪。删除最后一条时不需要移动元素，但为了找到它，仍然要从前面一路比较过去。
20.7 和第 8 章的对比#
第 8 章也用结构体数组存学生记录。区别在哪里？
| 第 8 章 | 本章 | |
|---|---|---|
| 数据存放 | main 里的局部变量 | struct DB 结构体 |
| 操作方式 | 代码直接写在 main 的 if-else 里 | 独立函数，接收 DB * 参数 |
| 功能 | 添加、查找、打印 | 插入、查找、删除、列出 |
| 多实例 | 容易写成一堆分散变量 | 可以声明多个 struct DB |
把数据和操作装进结构体和函数，最大的好处是：一个程序里可以同时运行多个数据库。
struct DB class_a;
struct DB class_b;
class_a.count = 0;
class_b.count = 0;
db_insert(&class_a, 1, "Alice", 92);
db_insert(&class_b, 1, "Bob", 78);两个数据库各自独立，互不干扰。这里的两份数据库都保存学生记录；如果要保存课程记录，需要再定义一套适合课程的结构体和函数。
20.8 常见坑#
坑 1：忘记初始化 count。
struct DB db;
// 忘了 db.count = 0;
db_insert(&db, 1, "Alice", 92); // db.count 的值不确定
局部变量不会自动清零。db.count 可能是任意值，插入时可能写到数组的随机位置。声明 struct DB 后，第一件事就是 db.count = 0。
坑 2：删除时只挪了一格。
// 错：只挪了一次
db->rows[found] = db->rows[found + 1];
// 对：要把 found 之后的所有元素都往前挪
for (int j = found; j < db->count - 1; j++) {
db->rows[j] = db->rows[j + 1];
}如果只挪一格，rows[found+1] 的数据被覆盖了，但 rows[found+2] 及之后的数据没有动，中间会出现一个"洞"。
坑 3：删除后忘了 count 减一。
for (int j = found; j < db->count - 1; j++) {
db->rows[j] = db->rows[j + 1];
}
// 忘了 db->count = db->count - 1;
结果：count 没变，但最后一条记录被挪走了，rows[count-1] 位置上会有重复数据。
坑 4：查找返回指针后，数据库发生了变化。
struct Student *s = db_find(&db, 2);
db_delete(&db, 1); // 删除 Alice，Bob 会被前移
printf("%s\n", s->name); // s 指向的位置可能已经被覆盖
db_find 返回的是指向 rows 数组内部的指针。上面的例子里，s 原来指向 Bob 所在的位置；删除 Alice 后，Carol 会前移到那个位置，s 看到的内容就可能变了。安全做法是找到之后立刻把数据复制出来：
struct Student *s = db_find(&db, 2);
if (s != NULL) {
struct Student copy = *s; // 复制一份
// 之后用 copy，不用担心被移动
}坑 5：snprintf 的缓冲区大小写错。
snprintf(s->name, sizeof(s->name), "%s", name); // 对：用 sizeof 自动算大小
snprintf(s->name, sizeof(s->name), "%s", name); // 更好：自动算大小
snprintf(s->name, 100, "%s", name); // 错：name 只有 32 字节，越界了
snprintf 的第二个参数是目标缓冲区的大小。写大了会越界，写小了会截断。用 sizeof(s->name) 最安全。
20.9 自己试试看#
Q1：给 struct Student 加一个 age 字段（年龄），修改插入和列出函数。
提示：在 struct Student 里加 int age;，插入时多读一个数字，打印时多输出一列。
Q2：写一个 db_count 函数，返回数据库当前的记录数。
提示：直接返回 db->count。
Q3：写一个 db_clear 函数，清空数据库的所有记录。
提示：把 count 设成 0 就行。不需要真的擦除数组里的数据——count 为 0 时，程序不会访问任何记录。
Q4：修改程序，让查找和删除操作在表为空时直接提示"数据库为空"，而不是让用户输入学号再告诉"没找到"。
提示：在操作开始前检查 db->count == 0。
Q5：声明两个 struct DB，一个存一班学生，一个存二班学生，分别插入几条记录，验证它们互不影响。
Q6：修改 db_delete 函数，让它删除所有匹配的记录，而不是只删第一条。
提示：删除一条后，后面的元素会前移到当前位置。这个时候不要立刻跳到下一个下标，要继续检查当前位置的新记录。
下一章的问题#
数组版数据库能插入、查找、删除、列出，四个操作都有了。但 DB_CAPACITY 现在写成 100，编译出来的数组容量就是固定的——最多只能放 100 条记录。
如果一个学校有 500 个学生，第 101 条记录插不进去。如果只存了 5 条记录，剩下的 95 个位置白白占着内存。
怎样让数据库的容量能根据数据量自动变大或变小？