小项目：通讯录

第 30 课，共 30 课 · 第 6 部分 · 再往前 · 约 20 分钟

是时候把学过的东西拼起来了。这一课一步一步写一个小通讯录。每一步都是一段能运行的完整程序，每一步都在上一步的基础上多加一点。计划是这样的：

部分	做什么	用到第几课
`Contact`	一个人：名字和电话	23、25
`Book`	所有联系人，放在一个会长大的数组里	22、24
`book_add`	加一个人，满了就先腾地方	20、22
`book_list`	把所有人列出来	17、24
`book_find`	按名字找人	14
`book_remove`	删掉一个人	11、23
`book_free`	把内存还回去	20、21

一个联系人

先定下一个联系人是什么样子：名字和电话号码，都是字符串。电话号码存成文字而不是 int：它可能以 0 开头，中间还有 -。

main.c

1#include <stdio.h>2 3typedef struct {4    char name[20];5    char phone[16];6} Contact;7 8void print_contact(const Contact *c) {9    printf("%s：%s\n", c->name, c->phone);10}11 12int main(void) {13    Contact friends[2] = {14        {"小林", "555-0101"},15        {"小王", "555-0102"}16    };17    for (int i = 0; i < 2; i++) {18        print_contact(&friends[i]);19    }20    return 0;21}

输出

小林：555-0101
小王：555-0102

print_contact 接收的是指针，结构体不用复制一份；const 表示这个函数只读不改。名字最多 19 个字节，再加一个 '\0'。一个汉字在 UTF-8 里占 3 个字节，小林 占 6 个。

会长大的通讯录

只能放 2 个人的数组太小了，而且谁也没法事先知道一个人有多少朋友。所以通讯录把联系人放在堆上，放在一个满了就翻倍的数组里，和第 22 课那个会长大的列表一样。count 是现在有几个人，capacity 是能放几个。

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_add(Book *book, const char *name, const char *phone) {17    if (book->count == book->capacity) {18        int new_capacity = book->capacity * 2;19        if (new_capacity == 0) {20            new_capacity = 2;21        }22        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));23        if (bigger == NULL) {24            return 0;25        }26        book->items = bigger;27        book->capacity = new_capacity;28    }29    strcpy(book->items[book->count].name, name);30    strcpy(book->items[book->count].phone, phone);31    book->count++;32    return 1;33}34 35void book_free(Book *book) {36    free(book->items);37    book->items = NULL;38    book->count = 0;39    book->capacity = 0;40}41 42int main(void) {43    Book book = {NULL, 0, 0};44    book_add(&book, "小林", "555-0101");45    book_add(&book, "小王", "555-0102");46    book_add(&book, "小陈", "555-0103");47    printf("%d 个联系人，能放 %d 个\n", book.count, book.capacity);48    book_free(&book);49    return 0;50}

输出

3 个联系人，能放 4 个

通讯录一开始是空的：items 是 NULL，一个位置也没有。realloc(NULL, 大小) 和 malloc(大小) 一样，所以第一次 book_add 拿到 2 个位置。第三次发现满了，就向 realloc 要 4 个位置。要是 realloc 失败了，原来的那块还在，book_add 返回 0。

点单步，盯着堆看：先出现一块能放 2 个人的内存，然后换成一块能放 4 个人的，小林和小王被复制过去，book.items 的箭头也指向了新的这块。最后 book_free 把这块也还回去：堆上的块全都是灰色的「已释放」，没有一块标着「内存泄漏」。

先猜一猜

加了 5 个人以后，通讯录能放几个人？

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_add(Book *book, const char *name, const char *phone) {17    if (book->count == book->capacity) {18        int new_capacity = book->capacity * 2;19        if (new_capacity == 0) {20            new_capacity = 2;21        }22        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));23        if (bigger == NULL) {24            return 0;25        }26        book->items = bigger;27        book->capacity = new_capacity;28    }29    strcpy(book->items[book->count].name, name);30    strcpy(book->items[book->count].phone, phone);31    book->count++;32    return 1;33}34 35int main(void) {36    Book book = {NULL, 0, 0};37    book_add(&book, "小林", "555-0101");38    book_add(&book, "小王", "555-0102");39    book_add(&book, "小陈", "555-0103");40    book_add(&book, "小张", "555-0104");41    book_add(&book, "小赵", "555-0105");42    printf("能放 %d 个\n", book.capacity);43    free(book.items);44    return 0;45}

输出

列出所有人

要显示通讯录，就把 items 从 0 走到 count - 1。到 count 为止，不是到 capacity：count 后面的位置还什么都没写。

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_add(Book *book, const char *name, const char *phone) {17    if (book->count == book->capacity) {18        int new_capacity = book->capacity * 2;19        if (new_capacity == 0) {20            new_capacity = 2;21        }22        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));23        if (bigger == NULL) {24            return 0;25        }26        book->items = bigger;27        book->capacity = new_capacity;28    }29    strcpy(book->items[book->count].name, name);30    strcpy(book->items[book->count].phone, phone);31    book->count++;32    return 1;33}34 35void book_list(const Book *book) {36    if (book->count == 0) {37        printf("（空的）\n");38    }39    for (int i = 0; i < book->count; i++) {40        printf("%d. %s：%s\n", i + 1, book->items[i].name, book->items[i].phone);41    }42}43 44void book_free(Book *book) {45    free(book->items);46    book->items = NULL;47    book->count = 0;48    book->capacity = 0;49}50 51int main(void) {52    Book book = {NULL, 0, 0};53    book_list(&book);54    book_add(&book, "小林", "555-0101");55    book_add(&book, "小王", "555-0102");56    book_add(&book, "小陈", "555-0103");57    book_list(&book);58    book_free(&book);59    return 0;60}

输出

（空的）
1. 小林：555-0101
2. 小王：555-0102
3. 小陈：555-0103

book_list 只读通讯录，所以参数是 const Book *；book_add 和 book_free 要改它，参数就是普通的 Book *。

按名字找

book_find 用 strcmp 一个一个比名字（字符串不能用 == 比，第 14 课）。找到了返回这个人的下标，没有这个名字就返回 -1：

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_add(Book *book, const char *name, const char *phone) {17    if (book->count == book->capacity) {18        int new_capacity = book->capacity * 2;19        if (new_capacity == 0) {20            new_capacity = 2;21        }22        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));23        if (bigger == NULL) {24            return 0;25        }26        book->items = bigger;27        book->capacity = new_capacity;28    }29    strcpy(book->items[book->count].name, name);30    strcpy(book->items[book->count].phone, phone);31    book->count++;32    return 1;33}34 35int book_find(const Book *book, const char *name) {36    for (int i = 0; i < book->count; i++) {37        if (strcmp(book->items[i].name, name) == 0) {38            return i;39        }40    }41    return -1;42}43 44void book_free(Book *book) {45    free(book->items);46    book->items = NULL;47    book->count = 0;48    book->capacity = 0;49}50 51int main(void) {52    Book book = {NULL, 0, 0};53    book_add(&book, "小林", "555-0101");54    book_add(&book, "小王", "555-0102");55    book_add(&book, "小陈", "555-0103");56    const char *wanted[2] = {"小王", "小周"};57    for (int k = 0; k < 2; k++) {58        int i = book_find(&book, wanted[k]);59        if (i == -1) {60            printf("%s：没找到\n", wanted[k]);61        } else {62            printf("%s：%s\n", wanted[k], book.items[i].phone);63        }64    }65    book_free(&book);66    return 0;67}

输出

小王：555-0102
小周：没找到

wanted 是一个数组，里面放着两个 const char *，各指向一个要找的名字。为什么返回下标，而不直接返回电话？因为别的函数也用得上：book_remove 要知道这个人在哪儿。

删掉一个人

要删掉下标 i 的那个人，就把它后面的每个人都往左挪一格，再让 count 少 1。结构体赋值会整个复制（第 23 课），名字和电话一起过去。其他人的顺序不变。

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_add(Book *book, const char *name, const char *phone) {17    if (book->count == book->capacity) {18        int new_capacity = book->capacity * 2;19        if (new_capacity == 0) {20            new_capacity = 2;21        }22        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));23        if (bigger == NULL) {24            return 0;25        }26        book->items = bigger;27        book->capacity = new_capacity;28    }29    strcpy(book->items[book->count].name, name);30    strcpy(book->items[book->count].phone, phone);31    book->count++;32    return 1;33}34 35void book_list(const Book *book) {36    if (book->count == 0) {37        printf("（空的）\n");38    }39    for (int i = 0; i < book->count; i++) {40        printf("%d. %s：%s\n", i + 1, book->items[i].name, book->items[i].phone);41    }42}43 44int book_find(const Book *book, const char *name) {45    for (int i = 0; i < book->count; i++) {46        if (strcmp(book->items[i].name, name) == 0) {47            return i;48        }49    }50    return -1;51}52 53int book_remove(Book *book, const char *name) {54    int i = book_find(book, name);55    if (i == -1) {56        return 0;57    }58    for (int j = i; j < book->count - 1; j++) {59        book->items[j] = book->items[j + 1];60    }61    book->count--;62    return 1;63}64 65void book_free(Book *book) {66    free(book->items);67    book->items = NULL;68    book->count = 0;69    book->capacity = 0;70}71 72int main(void) {73    Book book = {NULL, 0, 0};74    book_add(&book, "小林", "555-0101");75    book_add(&book, "小王", "555-0102");76    book_add(&book, "小陈", "555-0103");77    book_add(&book, "小张", "555-0104");78    book_remove(&book, "小王");79    if (!book_remove(&book, "小周")) {80        printf("没有小周，删不了\n");81    }82    book_list(&book);83    printf("%d 个联系人，能放 %d 个\n", book.count, book.capacity);84    book_free(&book);85    return 0;86}

输出

没有小周，删不了
1. 小林：555-0101
2. 小陈：555-0103
3. 小张：555-0104
3 个联系人，能放 4 个

循环到 count - 1 为止，因为 items[j + 1] 必须还是一个真的联系人。删掉小王以后，能放 4 个，只有 3 个人：通讯录不会变小，这没关系。整个通讯录就是这些了。再点一次单步，看小王的位置被小陈填上，小陈的位置又被小张填上。

全部释放

从 malloc 或 realloc 拿到的每一块，都要正好 free 一次。通讯录只有一块，就是 items，联系人都放在这一块里面，所以 book_free 只要一个 free。之后它把 items 设成 NULL、把两个数设成 0，通讯录就又是一个好好的空通讯录：还能接着 book_add，就算调用两次 book_free，也不会把同一块释放两次。

忘了 book_free，这块内存就一直被占着，直到程序结束。这就是第 21 课的内存泄漏。在一直运行的程序里，比如手机上的通讯录，泄漏会越积越多。

小技巧： 写「要内存」的函数时，就把「还内存」的函数一起写好。这样每个 book_add 从一开始就有对应的 book_free。

练一练

写好代码，点检查。提示随便看，实在想不出来再看答案。每道题都给通讯录加一个功能。

练习 1

改电话

写 book_set_phone：找到这个名字的联系人，把电话改成新的。改成了返回 1，没有这个人返回 0。改完以后，列表里 小王 的电话应该是 555-9999。

要显示

没有小周
1. 小林：555-0101
2. 小王：555-9999

exercise1.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_add(Book *book, const char *name, const char *phone) {17    if (book->count == book->capacity) {18        int new_capacity = book->capacity * 2;19        if (new_capacity == 0) {20            new_capacity = 2;21        }22        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));23        if (bigger == NULL) {24            return 0;25        }26        book->items = bigger;27        book->capacity = new_capacity;28    }29    strcpy(book->items[book->count].name, name);30    strcpy(book->items[book->count].phone, phone);31    book->count++;32    return 1;33}34 35void book_list(const Book *book) {36    for (int i = 0; i < book->count; i++) {37        printf("%d. %s：%s\n", i + 1, book->items[i].name, book->items[i].phone);38    }39}40 41int book_find(const Book *book, const char *name) {42    for (int i = 0; i < book->count; i++) {43        if (strcmp(book->items[i].name, name) == 0) {44            return i;45        }46    }47    return -1;48}49 50int book_set_phone(Book *book, const char *name, const char *phone) {51 52}53 54int main(void) {55    Book book = {NULL, 0, 0};56    book_add(&book, "小林", "555-0101");57    book_add(&book, "小王", "555-0102");58    book_set_phone(&book, "小王", "555-9999");59    if (!book_set_phone(&book, "小周", "555-0000")) {60        printf("没有小周\n");61    }62    book_list(&book);63    free(book.items);64    return 0;65}

输出

点「运行」或按 Ctrl+Enter

练习 2

不要重复

现在 小林 能加两次。改 book_add：名字已经在通讯录里时，什么也不加，返回 0。程序应该显示 小林已经在里面了，列表里只有 2 个人。

要显示

小林已经在里面了
1. 小林：555-0101
2. 小王：555-0102

exercise2.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_find(const Book *book, const char *name) {17    for (int i = 0; i < book->count; i++) {18        if (strcmp(book->items[i].name, name) == 0) {19            return i;20        }21    }22    return -1;23}24 25int book_add(Book *book, const char *name, const char *phone) {26    if (book->count == book->capacity) {27        int new_capacity = book->capacity * 2;28        if (new_capacity == 0) {29            new_capacity = 2;30        }31        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));32        if (bigger == NULL) {33            return 0;34        }35        book->items = bigger;36        book->capacity = new_capacity;37    }38    strcpy(book->items[book->count].name, name);39    strcpy(book->items[book->count].phone, phone);40    book->count++;41    return 1;42}43 44void book_list(const Book *book) {45    for (int i = 0; i < book->count; i++) {46        printf("%d. %s：%s\n", i + 1, book->items[i].name, book->items[i].phone);47    }48}49 50int main(void) {51    Book book = {NULL, 0, 0};52    book_add(&book, "小林", "555-0101");53    book_add(&book, "小王", "555-0102");54    if (!book_add(&book, "小林", "555-0199")) {55        printf("小林已经在里面了\n");56    }57    book_list(&book);58    free(book.items);59    return 0;60}

输出

点「运行」或按 Ctrl+Enter

练习 3

存到文件里

写 book_save：每个联系人在文件里写一行，名字、一个空格、电话，比如 小林 555-0101。文件打不开返回 0，否则返回 1。main 里已经写好了把文件读回来显示的部分。

要显示

小林 555-0101
小王 555-0102
小陈 555-0103

exercise3.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct {6    char name[20];7    char phone[16];8} Contact;9 10typedef struct {11    Contact *items;12    int count;13    int capacity;14} Book;15 16int book_add(Book *book, const char *name, const char *phone) {17    if (book->count == book->capacity) {18        int new_capacity = book->capacity * 2;19        if (new_capacity == 0) {20            new_capacity = 2;21        }22        Contact *bigger = realloc(book->items, new_capacity * sizeof(Contact));23        if (bigger == NULL) {24            return 0;25        }26        book->items = bigger;27        book->capacity = new_capacity;28    }29    strcpy(book->items[book->count].name, name);30    strcpy(book->items[book->count].phone, phone);31    book->count++;32    return 1;33}34 35int book_save(const Book *book, const char *filename) {36 37}38 39int main(void) {40    Book book = {NULL, 0, 0};41    book_add(&book, "小林", "555-0101");42    book_add(&book, "小王", "555-0102");43    book_add(&book, "小陈", "555-0103");44    book_save(&book, "contacts.txt");45    free(book.items);46 47    char line[100];48    FILE *f = fopen("contacts.txt", "r");49    if (f == NULL) {50        printf("什么也没存上\n");51        return 1;52    }53    while (fgets(line, sizeof line, f) != NULL) {54        printf("%s", line);55    }56    fclose(f);57    return 0;58}

输出

点「运行」或按 Ctrl+Enter

这一课学会了

大一点的程序是用小函数搭起来的，每个函数只做一件事：加、列、找、删、放。
一个结构体存一条记录；另一个结构体存数组、它的 count 和 capacity。
数组放在堆上，满了用 realloc 翻倍；realloc(NULL, 大小) 和 malloc(大小) 一样。
只读的函数用 const 指针做参数，要改通讯录的函数用普通指针。
从中间删除，就是把后面的元素都往左挪一格。
拿到的每一块内存都要 free 一次；释放以后把指针设成 NULL。