通讯录整理这个题目，我第一次见到是在别人的课设清单里，当时的第一反应是"这有什么好做的"。后来自己动手整理手机里攒了五六年的联系人，两千多条，重复的、缺号码的、备注写半截的、分组乱成一锅粥的，才意识到这活儿没那么简单：一次导入就卡住、删一条记录整个列表错位、三个备份文件合起来重复了四百多条。通讯录整理这件事，表面上是"增删改查"四个字，实际牵扯到数据结构里的存储结构选型、哈希索引设计、排序策略、集合归并去重、持久化读写、内存管理一整条链路，是个非常适合拿来把课本知识变成手上功夫的小项目。

这篇文章我按自己实际做一遍的顺序写：先把"整理通讯录"翻译成一个数据结构问题，再讲存储结构怎么选、为什么最后没选数组，然后把核心数据模型、关键代码、容量参数估算摊开讲，接着把"多份通讯录合并去重"这个最容易翻车的环节单独拎出来，最后附一份我自己踩出来的问题速查表。适合正在做课程设计的同学，也适合想拿一个小项目把链表、哈希表从"考试会写"练到"手上会写"的开发者。代码用 C 语言写，换成 Java、Python、Go 思路完全一样。

1. 先把"整理通讯录"翻译成数据结构问题

1.1 通讯录的本质是一张带索引的表

通讯录说白了就是一张二维表：每行是一个联系人，每列是一个字段。姓名、手机号、分组、单位、备注，这几列基本覆盖了日常需求。所有"整理"动作，无论听起来多花哨，本质都是对这张表做四类操作：行的插入与删除、列的条件筛选、整体的排序、多张表的归并去重。数据结构要回答的核心问题只有一个——这张表在内存里到底长什么样，才能让这四类操作都跑得够快。

这个问题一旦问清楚，后面所有的选择都有了判断依据。比如"按姓名找一个人"，如果是顺序表，得从头比到尾，两千条就要比两千次；如果是哈希表，把姓名或手机号算成桶下标，一次就能定位。再比如"删掉一个人"，顺序表删除要搬移后面所有元素，链表只需要改两个指针。所谓选型，其实就是先把自己的操作分布统计出来，再挑一个平均代价最低的方案，而不是看哪个数据结构名字听起来高级。

我自己的习惯是先列一张操作频次表，把每个操作大概占多少比例写下来。日常使用里，查找大约占七成，新增和修改各占一成多，删除不到半成，剩下的是排序和批量导入。这个比例非常关键，它直接决定了后面所有设计的重心必须压在"查找快"上，而不是压在"插入快"上。

1.2 五个基本操作和两个容易被忽略的需求

把需求拆细，通讯录整理至少包含这五个基本操作：按关键字段精确查找、新增联系人、修改联系人、删除联系人、按条件列出一批人。前四个是骨架，第五个是日常用得最多的——"把同事分组的都列出来"、"把三个月没联系过的列出来"，本质上都是条件筛选。

真正容易被忽略的是另外两个需求。第一个是主键唯一性。手机号在一份通讯录里理论上不该重复，但现实里一定重复：同一个人存了两次、一个人有两个号、导入时格式没对齐导致同一个号出现两遍。如果没有一个稳定主键，去重就无从谈起。第二个是批量归并。通讯录几乎不会只存在于一个地方，旧手机一份、新手机一份、表格导出一份，整理的核心动作其实是把多份合一份。这个操作对数据结构的要求和单条增删完全不同，它要求能快速判断"这个人是不是已经存在"，也就把哈希表推到了台前。

提示：动手写代码之前，先花十分钟把自己手机里的通讯录导出来看一眼，统计有多少条、有多少重复号码、有多少字段是空的。真实数据的脏乱程度会直接决定你后面要写多少容错代码，比任何教科书例题都有参考价值。

2. 存储结构怎么选：四种方案的实测对比

2.1 顺序表、单链表、哈希表、平衡树的量化对比

四种常见方案我都实际写过一遍，用十万条模拟数据压测，结论很明确。下面这张表是我当时记录的大致结果，具体的绝对数字会随机器不同而变化，但量级关系是稳定的：

单纯看复杂度，哈希表在精确查找上碾压其他三个。但哈希表有个致命短板：它不保序。你想"按姓名首字母排序列出全部联系人"，哈希表做不到，只能把数据全捞出来再排一遍。而通讯录这个东西，用户打开的第一眼就是要看到有序的列表，无序的哈希表没法直接当主结构用。

顺序表也不是一无是处。它的内存是连续的，遍历起来对 CPU 缓存极其友好，十万条顺序扫一遍比链表快好几倍。如果我的场景是"一年只改几次、天天要全量浏览"，顺序表反而是最省事的选择，配一个排好序的数组加二分查找，查找也能做到 O(log n)。问题在于通讯录的修改是随机的，用户在任意位置删一条，后面全要搬，两千条以内感觉不出来，十万条就明显卡顿。

2.2 我为什么最终用"哈希索引 + 双向链表"这套组合

绕了一圈，我最后用的是组合结构：一条双向链表负责维护顺序和遍历，一张哈希表负责按手机号快速定位。同一条联系人记录同时挂在两个结构上，链表里用 prev/next 串起来，哈希桶里用另一个指针串起来。相当于给一本书同时做了页码顺序和目录索引，翻页靠链表，查条目靠目录。

这么设计有三个直接好处。第一，查找是 O(1)，输入手机号立刻定位到节点，不用扫链表。第二，遍历是有序的，链表天然保持插入顺序，如果需要按姓名排序，排序只动链表指针，不用碰哈希表，哈希桶里的位置和顺序完全无关。第三，删除是 O(1) 且不用搬移，从哈希桶摘一次链、从双向链表摘一次链，两次指针操作搞定，这在数组方案里是做不到的。

代价也很清楚：每条记录多了三个指针（prev、next、哈希链的 next），在 64 位机器上就是 24 字节。十万条多出 2.4MB，相对于整体内存占用完全可以接受。另外删除时必须两边同步摘链，漏一边就是内存泄漏或者野指针，这是这套结构唯一需要小心的地方，后面第 6 节会专门讲。

注意：双结构挂载的关键纪律是"同生共死"。插入时两边都要挂上，删除时两边都要摘掉，任何一条路径只做了一半，程序都会在某个意想不到的地方崩掉。我建议把插入和删除各自封装成一个函数，绝不在业务代码里手写指针操作。

2.3 容量与参数的估算过程

哈希桶的数量不能拍脑袋定。负载因子（元素数除以桶数）控制在 0.75 以下比较稳妥，超过这个值冲突链变长，查找退化。假设目标支持十万条联系人，桶数至少要 100000 / 0.75 ≈ 133333，取附近的质数 131071 是个常用的选择。用质数是为了让哈希值对桶数取模时分布更均匀，避免某些规律性输入（比如手机号尾号连续）全部挤到少数几个桶里。

桶数组本身是存储指针的，64 位下每个桶 8 字节，131071 个桶约占 1MB，可以忽略。每条联系人的结构体我按字段长度算了一下：姓名 32 字节、手机号 16、分组 24、单位 48、备注 128，加上时间戳和三个指针，结构体大约 280 字节，再算上内存分配器的头部开销，实际每条接近 300 字节。十万条就是 30MB 左右，加上桶数组总共 31MB，普通机器完全扛得住。

这个估算过程的价值在于，它让你在写代码之前就知道"能不能撑住"。如果算出来是 3GB，那就得换思路，比如备注字段改成变长存储、或者把不常用的字段放到磁盘上按需加载。很多课程设计之所以一导入大数据就崩，根本原因就是从头到尾没算过这笔账，结构体里随手开了几个 1024 字节的缓冲区，一万条就爆了。

3. 数据模型与核心代码实现

3.1 联系人结构体的字段设计

结构体是所有后续代码的地基，字段设计错了，后面怎么改都别扭。我的版本大概是这样：

typedef struct Contact { char name[32]; // 姓名，UTF-8 下约 10 个汉字 char phone[16]; // 手机号，11 位加结束符 char group[24]; // 分组，如"同事""家人" char company[48]; // 单位 char note[128]; // 备注 long long created; // 创建时间戳 struct Contact *prev, *next; // 双向链表 struct Contact *hnext; // 哈希桶冲突链 } Contact;

几个字段的选择理由值得说清楚。手机号用char[16]而不是整数，是因为手机号天然是"标识符"而不是"数值"——你永远不会对手机号做加减乘除，但会需要保留前导零、需要按字符串比较、需要处理带区号或分隔符的变体。更要命的是，11 位手机号早就超过了 32 位有符号整数的上限（约 21 亿），如果偷懒用int存，存进去就是溢出后的垃圾值。这个坑我见过不止一次。

姓名字段开 32 字节是权衡的结果。UTF-8 下一个汉字占 3 字节，32 字节约能放 10 个汉字，覆盖绝大多数中文姓名，少数民族姓名或外文名可能不够。如果确实要支持长名字，可以改成定长前缀加变长存储，但这会显著增加代码复杂度，课程设计阶段没必要。

3.2 增删改查四个操作的实现细节

哈希函数我用的是 BKDR 变体，实现只有三行，分布效果足够好：

static unsigned int bkdr_hash(const char *s) { unsigned int h = 0; while (*s) h = h * 131u + (unsigned char)(*s++); return h; }

乘数取 131 是经验值，对短字符串（手机号 11 位、姓名十来个字节）的雪崩效应不错，相邻号码能被打散到不同桶里。这里有个细节：必须把字符转成unsigned char再参与运算，否则遇到中文这种高位为 1 的字节，会带符号扩展成负数，哈希结果直接失控。

插入函数要做两件事，先挂哈希桶，再挂链表尾，最后计数加一：

void contacts_insert(Book *b, Contact *c) { unsigned int idx = bkdr_hash(c->phone) % b->bucket_cnt; c->hnext = b->buckets[idx]; b->buckets[idx] = c; // 头插进冲突链 c->prev = b->tail; // 尾插进双向链表 c->next = NULL; if (b->tail) b->tail->next = c; else b->head = c; b->tail = c; b->size++; }

查找就是算哈希、定位桶、顺着冲突链逐个比手机号，平均一两次比较就命中。删除要更小心，先从哈希桶里摘，再从链表里摘，两个步骤的顺序无所谓，但都必须做：

void contacts_remove(Book *b, Contact *c) { unsigned int idx = bkdr_hash(c->phone) % b->bucket_cnt; Contact **pp = &b->buckets[idx]; while (*pp && *pp != c) pp = &(*pp)->hnext; if (*pp) *pp = c->hnext; // 从哈希桶摘除 if (c->prev) c->prev->next = c->next; else b->head = c->next; if (c->next) c->next->prev = c->prev; else b->tail = c->prev; b->size--; free(c); }

用二级指针摘链是 C 里比较地道的写法，能省掉"前驱为空"的特殊判断。修改操作本质上是"先删后插"，因为手机号是主键，主键一改哈希位置就变了，不能原地改。

3.3 排序：中文姓名排序的坑比想象中大

排序这块我踩过一个很典型的坑。一开始想当然地写了个strcmp比较姓名，结果发现排序结果是乱的——因为 UTF-8 编码里，汉字的字节序是按 Unicode 码点排的，不等于拼音序。比如"张"和"李"，按码点排出来的顺序跟拼音完全对不上，用户一看就知道不对。

解决办法是给每条联系人预生成一个排序键。简单版是取姓名首字的拼音首字母，在导入时查表生成，一个汉字对应一个字母，存到结构体的额外字段里；讲究一点的可以用完整的拼音串。生成一次存起来，之后排序只比这个键，速度快且结果稳定。

排序本身我用的是链表归并排序。数组快排需要随机访问，链表用快排不仅访问慢，还容易写错；归并排序天生适合链表，只需要改指针，时间复杂度 O(n log n)，还顺手是稳定的——这一点很重要，同名的联系人排序后应该保持原有的相对顺序，否则每次刷新列表顺序都在跳，用户会疯。

Contact *merge_sort(Contact *h) { if (!h || !h->next) return h; Contact *slow = h, *fast = h->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } Contact *mid = slow->next; slow->next = NULL; return merge(merge_sort(h), merge_sort(mid)); }

快慢指针找中点这个技巧，建议练到闭着眼睛能写出来，链表相关的题里出现频率极高。

4. 通讯录合并与去重：最容易翻车的一步

4.1 合并规则必须在写代码前定死

两份通讯录合并，最麻烦的地方不是技术，是规则。"同一个人在两份数据里都有，但一份有单位没有备注，另一份有备注没有单位，合完应该是啥样？"不同的人能给出完全不同的答案。如果规则没在动手前定清楚，代码写到一半改规则，前面的逻辑全部推倒重来。

我最后定的规则是四条：手机号相同即认为是同一个人；合并时字段逐个处理，目标为空而来源非空则补全；两边都非空且不一致时保留目标值，同时把来源值追加到备注，用特定分隔符隔开，方便人工复核；手机号不同的一律视为不同人，直接插入。这套规则的好处是绝不丢信息，代价是备注会变长，所以备注字段要预留足够空间，或者干脆做成变长。

还有一种边界情况得提前想好：空手机号。现实数据里总有那么几条联系人，只有名字没有号码。这类记录没法用主键匹配，我的处理是降级比对"姓名 + 单位"的组合，两个字段完全相同才算重复。这个降级规则一定要在文档或者注释里写明白，否则将来别人接手会以为是 bug。

4.2 合并的算法实现与复杂度

规则定好之后，算法其实非常短。假设 A 是目标通讯录（已经在内存里建好了哈希索引），B 是来源数据（从文件读进来的一批记录），流程就是遍历 B，每条拿去 A 里查，命中走字段合并，未命中走插入：

void contacts_merge(Book *dst, const Book *src) { for (Contact *p = src->head; p; p = p->next) { Contact *hit = contacts_find(dst, p->phone); if (hit) merge_fields(hit, p); // 字段级补全 else contacts_insert(dst, clone(p)); // 深拷贝后插入 } }

复杂度是 O(m)，m 是来源记录数，每条只查一次哈希，跟目标表多大完全无关。这个性质很重要：合并十万条和合并十条的速度差异只体现在来源规模上，不会因为目标表变大而变慢。相比之下，如果当初选了顺序表，每条都要在目标表里线性扫一遍，十万乘十万就是灾难。

这里有个隐藏的坑：clone必须是深拷贝。如果直接把来源节点的指针插到目标表里，来源表释放时目标表里的节点就全变成野指针了。C 语言里这种错误不会当场报错，而是在程序退出前随机崩溃，排查起来极其痛苦。

提示：合并之前先把目标表备份一份到文件。合并逻辑再怎么测都可能有意想不到的边界，有备份就能回滚，没备份就只能对着被污染的数据发愁。这个习惯我从第一次写数据迁移脚本之后就再没丢过。

5. 完整实操流程：从空文件到能跑的程序

5.1 工程结构与编译方式

整个项目我拆成三个文件，逻辑分层清楚，将来换存储方式只改一处：contact.h放结构体定义和函数声明，contact.c放哈希、链表、增删改查、排序、合并的实现，main.c放菜单交互和文件读写。编译就一行：

gcc -O2 -Wall -Wextra -g -o contacts main.c contact.c

-Wall -Wextra一定要加，它能帮你抓出大量隐式类型转换、未使用变量、可疑的赋值。-g留着方便调试，真出问题时能直接看到行号。开发阶段我强烈建议再配一个-fsanitize=address，内存越界和泄漏会当场报出来，比事后猜快一百倍：

gcc -g -fsanitize=address,undefined -o contacts_dbg main.c contact.c

这个开关救过我很多次。链表代码里少写一个next、删除后忘了置空，这类错误在普通编译下往往表现成"程序跑着跑着结果不对"，而在 sanitizer 下会直接指出是第几行访问了已释放的内存。

5.2 文件格式与持久化实现

存储格式我选了带分隔符的纯文本，一行一条记录，字段之间用制表符隔开。理由很实在：纯文本用任何编辑器都能打开，出了问题肉眼可见，用表格软件也能直接导入导出，方便和别的数据源对接。二进制格式虽然省空间、读写快，但一旦字段布局改了就没法兼容，调试时也看不出内容。

写入的时候有几个细节必须处理。第一，字段内容里如果本身含有制表符或换行，会破坏格式，要么转义要么直接过滤掉，我选择在录入阶段就禁止这两个字符。第二，文件末尾最好加一个换行，很多工具读最后一行没换行的文件会出问题。第三，写完一定要fclose，缓冲区里的数据才会真正落盘，中途崩溃就白写了。稳妥一点可以先写临时文件，写完再原子性地重命名覆盖，避免写到一半断电把原数据毁了。

读取的时候坑更多。Windows 下生成的文本文件行尾是\r\n，Unix 下是\n，如果按\n切分，每行末尾会多出一个\r，粘在最后一个字段上，导致手机号比对永远不相等——这个 bug 极其隐蔽，因为打印出来肉眼看不出区别。解决办法是读入后统一把\r剔除。另外，UTF-8 文件开头可能带 BOM，前三个字节是隐藏的标记，不处理的话第一条记录的姓名字段会带上一段乱码。

5.3 压测记录与性能观察

数据我生成了三档：一千条、一万条、十万条，分别测全量导入、一千次随机查找、一千次随机删除、一次全量排序。一千条的时候所有操作都是瞬间完成，感觉不出差异。一万条时顺序表的删除开始能感觉到轻微停顿，十万条时差距彻底拉开：哈希方案的全量导入在两秒以内，随机查找基本是微秒级；而对照组的顺序表实现，一千次随机删除花了十几秒，因为每次都要搬移后面几万个元素。

排序这一项倒是有点出乎意料，十万条链表归并排序比我预期的慢一些，主要原因是指针跳转导致缓存命中率低。如果排序是高频操作，可以考虑先把链表节点指针收进一个数组，对数组做快排，再按结果重连链表，能快出一截。这也是个通用思路：链表适合频繁增删，数组适合频繁访问，什么时候该转换形态，取决于当前操作的类型。

6. 常见问题与排查实录

6.1 高频问题速查表

下面这张表是我和身边人实际遇到过的问题汇总，基本覆盖了这个项目八成的坑：

表里每一条我都建议亲手复现一遍，知道错误长什么样比知道正确写法更有价值。尤其是手机号溢出和中文字节序这两条，属于那种"不看不知道，一看忘不掉"的类型。

6.2 几条只有踩过才知道的心得

第一条心得是关于测试数据的。很多人写完功能，用三五条手输的数据测一遍就交差，结果真实数据一导入全是问题。我的做法是专门写个小脚本，随机生成带各种脏数据的数据集：空字段、超长字段、重复号码、缺号码、含特殊字符的名字、行尾带回车。让程序先在脏数据上跑通，再谈功能完善。这一步花的时间，远比后面手动找 bug 省得多。

第二条是关于内存分配的。频繁malloc/free小对象会造成内存碎片，十万条数据反复增删之后，程序占用会虚高。如果场景是高频增删，可以预先分配一批节点做对象池，删除时只是标记为空闲而不是归还给系统，下次插入直接复用。这个优化在课程设计里不必须，但知道有这么个东西，将来写真正的服务端代码时会想起来。

第三条是关于接口设计的。contacts_find这个函数，一开始我写的是"找到就返回指针，找不到返回 NULL"，用起来很别扭，每个调用点都要判空。后来改成"返回指针加一个状态码"，再后来干脆提供两层接口：一层原始查找，一层"找不到就创建"的 upsert。接口顺手了，业务代码能短一半。数据结构课设最容易忽略的就是接口设计，大家把注意力全放在算法上，写完发现主函数里全是重复的判空和错误处理，那才是真正的维护成本。

最后一条是心态上的。通讯录整理这种题目，功能列表看起来十分钟能写完，实际做下来会发现真正的功夫全在边界条件上：空表怎么删、重复怎么合、文件坏了怎么恢复、中文怎么排。把边界条件一个个列出来打勾，比追求功能数量有意义得多。我自己那份代码前前后后改了七八版，每一版都是被一个具体的脏数据逼出来的，这些修改记录本身就是最好的学习材料。