简介基于C/C语言散列表实现的通讯录系统课程设计资料包面向需要完成课程设计、大作业或初学散列表的计算机专业学生。项目以电话号码和用户名为关键字分别建立散列表实现记录录入、冲突处理、按号码或姓名快速查找与显示并进一步比较不同散列函数与冲突处理方法的平均查找长度变化完整展示了散列表从设计到测试的过程。包内共有十二个文件包含三个源文件、三个头文件、一份课程设计报告、一个可执行程序、构建脚本及说明文档整体约一点一五兆字节目录结构清晰便于对照代码与报告理解实现细节。已有四百一十七人学习下载对于希望掌握散列表工程应用或快速搭建通讯录课程设计框架的读者而言这套资料能提供完整参考借助其中的报告和可调试源码还可进一步改造为电话簿、名片管理等扩展项目。1. 用 C/C 写散列表通讯录先解决“关键字”问题用 C/C 实现基于散列表的通讯录系统很多人第一反应是“用数组加链表就能交差”但真正动手做课程设计时最容易被低估的是关键字的选择。电话号码和用户名都能作为散列的输入但两者的散列函数、冲突概率和查找成本完全不同。这套资源给出了完整可编译的两套实现Hash.cpp 采用链地址法ArrayHash.cpp 采用开放定址法并附带 Makefile、课程设计报告和 records.txt 示例数据。适合正在做数据结构课程设计、需要对比不同冲突处理方法、或者想补上哈希表工程细节的开发者。这里不再复述题目要求直接拆开核心代码讲清楚散列函数设计、冲突处理实现和实验数据统计。2. 散列表结构设计记录模型、散列函数和冲突阈值的取舍2.1 记录的数据项电话号码和用户名谁做主键从数据模型出发。题目要求每条记录包含电话号码、用户名、地址三个数据项。散列表的关键字可以取电话号码也可以取用户名。电话是数字串能用字符指针直接遍历散列函数计算时只需处理数字字符用户名是字符串可能包含字母、数字甚至中文处理不当会出现散列分布严重倾斜。下面的结构体设计参考了项目里的 AddList.h但把地址宽度从固定 32 扩展到 64因为真实通讯录数据里地址往往超过 32 字节。电话用 16 字节而不是整数类型是为了保留前导 0 和区号字符。typedef struct { char phone[16]; char name[32]; char addr[64]; } Record; // 电话关键字散列只取数字位忽略空格和连字符 int hashPhone(const char *phone, int tableSize) { unsigned long h 0; for (int i 0; phone[i] ! \0; i) { if (phone[i] 0 phone[i] 9) { h h * 10 (phone[i] - 0); } } return (int)(h % tableSize); }这里把电话当作十进制数逐位转进h再用h % tableSize落桶。电话号可能是 13 位手机号也可能带010-12345678这种区号因此h用unsigned long避免 int 溢出。你如果要用atoi(phone)简化遇到带连字符的字符串会得到一个被截断的数所以不推荐。2.2 除留余数法与字符串加权散列课程设计里最常见的散列函数是除留余数法。它的核心是key % mm 是表长。对用户名字符串需要先把每个字符映射成一个整数常见做法是 BKDR 变体每次累加乘以一个近似 31 的乘子。2.2.1 用户名散列BKDR 实现int hashName(const char *name, int tableSize) { unsigned long h 0; while (*name) { h h * 31 (unsigned char)(*name); } return (int)(h % tableSize); }乘 31 相当于(h 5) - h编译器会自动优化成移位和减法计算成本很低。对英文字母和数字这个散列函数通常能均匀分散到各个桶。但对中文用户名一个汉字在 GBK 下占用两个字节两个汉字在不同编码下组合方式不同直接按字节遍历会受编码影响。所以 2.1 的 Record 里建议你把名字统一转成 UTF-8 再散列。2.2.2 表长为什么取质数除留余数的模数如果不取质数比如 100那么电话号码尾号xx00这样的记录会集中落到 0 号桶。而取 101 时尾号 00、01、02 会被均匀分散到 0、1、2。为了在实验中得到好看的冲突率曲线我一般把表长序列设成 101、211、307、503避免与电话尾号的十进制进位规律重叠。资源里的 Hash.cpp 的表长如果写死成了 100往后的对比实验要记得改成质数表长。2.3 装载因子先算好能承受多大的 α装载因子 α 已存记录数 / 表长。课程设计要求的记录数没有明说但实验部分要求考察“平均查找长度的变化”所以我们必须控制 α 在 0.5 到 1.2 之间变化才有实验意义。如果记录数是 100表长取 100 时 α1开放定址法的查找成本已经接近最坏情况表长取 200 时 α0.5链地址法每个桶平均半条记录查找接近一次命中。你需要准备 4 组不同表长分别跑同一批 records.txt记录冲突次数和 ASL 变化。2.4 加载 records.txt避免键盘输入的低效代码里通常在主函数从文件读取记录。用fscanf(fp, %s %s %s, name, phone, addr)读取时注意%s遇到空格就分段如果地址包含空格要用%[^\n]读取剩余行。这也是资源模板里可能没处理的地方。典型读取代码FILE *fp fopen(records.txt, r); while (fscanf(fp, %s %s, rec.name, rec.phone) 2) { fgets(rec.addr, sizeof(rec.addr), fp); // 去掉末尾换行符 rec.addr[strcspn(rec.addr, \n)] \0; insertChain(table, rec); }fgets会读入整行地址strcspn把换行符替换成空字符。如果文件里地址没有空格也可以用fscanf(fp, %s %s %s, ...)但一旦地址里出现空格读到的内容会错位。批量导入不仅能加快测试速度还能保证每次实验用同一份数据让冲突率对比有可信度。3. 双实现链地址法 Hash.cpp 与开放定址法 ArrayHash.cpp 对比3.1 链地址法哈希桶加链表头插法避免遍历3.1.1 节点设计与插入函数Hash.cpp 里把冲突元素挂到同一个桶的链表上。头节点数组大小为 tableSize每个节点存一条完整记录和 next 指针。typedef struct HashNode { Record record; struct HashNode *next; } HashNode; typedef struct { HashNode **slots; int tableSize; int keyType; // 0: phone, 1: name long compareCnt; // 查找时累计比较次数 } ChainTable; void chainInsert(ChainTable *ht, Record rec) { int idx (ht-keyType 0) ? hashPhone(rec.phone, ht-tableSize) : hashName(rec.name, ht-tableSize); HashNode *node (HashNode*)malloc(sizeof(HashNode)); node-record rec; node-next ht-slots[idx]; ht-slots[idx] node; }插入采用头插法。因为每个节点都是新建的新记录会被放在链表开头查找新插入记录时只需一次比较。如果你后插入的记录通常也会被马上查找这种策略在短哈希链上能刷低 ASL。keyType决定散列字段是电话还是用户名同一个表不能混用关键字否则会出现“用电话散列的位置去查找用户名”的逻辑错乱。查找函数必须同时支持“按电话查”和“按用户名查”int chainSearch(ChainTable *ht, const char *key, int keyType) { int idx (keyType 0) ? hashPhone(key, ht-tableSize) : hashName(key, ht-tableSize); HashNode *p ht-slots[idx]; int cmp 0; while (p ! NULL) { cmp; if (keyType 0) { if (strcmp(p-record.phone, key) 0) break; } else { if (strcmp(p-record.name, key) 0) break; } p p-next; } ht-compareCnt cmp; return (p ! NULL) ? cmp : -cmp; // 符号表示是否找到 }返回值的符号既能告诉外部是否找到又能带回比较次数。如果你写报告按照理论公式计算 ASL这里统计的 cmp 就是公式里的比较次数注意要从查找入口处清零ht-compareCnt避免多轮调用累加混乱。3.1.2 内存释放与隐患链地址法最容易忘的是释放链表。课程设计里跑一次就退出的程序可能看不到问题但如果你把它做成交互系统反复建表析构会内存泄漏。释放每个桶前要先把下一个节点指针暂存然后 free 当前节点。3.1.3 Makefile 与编译运行资源提供 Makefile两个核心源文件 Hash.cpp 和 ArrayHash.cpp 各自依赖独立的头文件。默认目标是把 Main AddList.cpp 与 Hash.cpp 编译成 Main.exe。Makefile 里常见片段CC g CFLAGS -Wall -O2 -stdc11 OBJS Main.o Hash.o AddList.o Main.exe: $(OBJS) $(CC) -o Main.exe $(OBJS) Main.o: Main.cpp Hash.h AddList.h Hash.o: Hash.cpp Hash.h AddList.h用make clean make重新编译。如果只想编译某个模块可以单独g -c Hash.cpp生成 Hash.o再和 Main.o 链接。注意 Windows 下 Main.exe 不能直接跨机运行缺少对应的 Visual C 运行库时常报“已检测到匹配的 Visual C Redistributable”这类提示解决办法是删除 .exe 在本机重新编译。3.2 开放定址法线性探测和它带来的聚集效应ArrayHash.cpp 用连续数组存放记录。冲突时线性向后探测空位。实现稍微简单但存在两个需要特别注意的坑。3.2.1 线性探测插入typedef struct { Record *records; int *state; // 0 empty, 1 occupied, 2 deleted int tableSize; int count; } OpenTable; void openInsert(OpenTable *ot, Record rec) { int idx hashPhone(rec.phone, ot-tableSize); int start idx; while (ot-state[idx] 1) { idx (idx 1) % ot-tableSize; if (idx start) { printf(表已满\n); return; } } ot-records[idx] rec; ot-state[idx] 1; ot-count; }注意终止条件如果探测一圈回到起点表必满。这里先把起点存成start避免循环里反复调用哈希函数浪费性能。循环条件中遇到 state 为 2 的位置可以占用这样删除过的槽能被重新利用。线性探测的缺点是容易产生“聚集”——一旦某个区域连续被占新记录要探测很远的距离才能找到空位。3.2.2 查找和删除的状态机查找时如果遇到 state2 必须继续探测不能立即停止int openSearch(OpenTable *ot, const char *phone, int *position) { int idx hashPhone(phone, ot-tableSize); int start idx; int cmp 0; while (ot-state[idx] ! 0) { if (ot-state[idx] 1 strcmp(ot-records[idx].phone, phone) 0) { *position idx; return cmp 1; } cmp; idx (idx 1) % ot-tableSize; if (idx start) break; } return -1; }删除时只把 state 置 2不清空记录。开放定址法在 α 超过 0.7 后冲突链会连成大片区域查找不存在的记录时要探测很多空槽才停下。所以实验对比中线性探测的查找失败 ASL 会非常难看。注意链地址法插入时同样需要先查重。如果题目不允许重复电话insert 前要先 search否则同一个电话会散列到同一个链表产生两条相同记录。3.3 两条路线的取舍什么时候用链地址法维度链地址法开放定址法实现复杂度多一套链表操作数组操作简单内存利用率每个节点额外 8 字节指针无指针但需要 state 标记α0.8 时查找仍稳定在 O(1α/2)严重退化接近顺序查找删除直接链表摘除需要墓碑标记检索变慢遍历输出需要遍历所有桶和链表直接遍历数组课程设计里我建议两个都实现但报告主推链地址法。因为你能直观画出一个桶里有几条记录解释什么是“冲突”开放定址法的聚集过程需要很多图才能讲清楚。如果只想交付一个满足题目的系统链地址法也更容易应对“查找并显示给定用户名记录”的要求因为可以同时维护两张表一张按电话散列一张按用户名散列互不干扰。4. 实验数据说话冲突率与平均查找长度 ASL 的统计方法4.1 提前在代码里埋好计数器统计平均查找长度不能靠感觉。我通常给两个哈希表都加上unsigned long long totalCmp和int searchCount每次执行查找函数就累加返回的比较次数并递增 searchCount。void resetStat(ChainTable *ht) { ht-totalCmp 0; ht-searchCount 0; }在查找函数的最后加上ht-totalCmp cmp; ht-searchCount;这样每次测试完成后用totalCmp / searchCount就能得到平均查找长度。注意查找失败同样要计入因为题目要求的是“查找并显示给定电话号码的记录”和“查找并显示给定用户名的记录”失败情况在真实系统里很常见。4.2 成功查找和失败查找分开统计不需要在代码里做复杂分支。先随机打乱测试关键字对存在的记录查找 N 次得到成功平均长度再构造 N 个不存在的关键字得到失败平均长度。一个简单的测试函数void simulate(ChainTable *ht, Record *recs, int recNum, const char **absentKeys, int absentNum) { for (int i 0; i recNum; i) { int k i % recNum; char key[32]; if (ht-keyType 0) { strcpy(key, recs[k].phone); } else { strcpy(key, recs[k].name); } chainSearch(ht, key, ht-keyType); } printf(成功ASL: %.4f\n, (double)ht-totalCmp / ht-searchCount); resetStat(ht); for (int i 0; i absentNum; i) { chainSearch(ht, absentKeys[i], ht-keyType); } printf(失败ASL: %.4f\n, (double)ht-totalCmp / ht-searchCount); }absentKeys 可以取类似19900000000这种肯定不在表里的或者对现有电话修改最后一位。注意 keyType 必须和表初始化时一致否则散列到不同的桶统计结果直接失效。4.3 用 records.txt 批量造数据手工输入 200 条记录不现实。资源里的 records.txt 可以直接用但如果要对比不同表长我推荐用脚本生成四组不同分布的数据。例如制造电话尾号规律性强的数据awk BEGIN{srand(); for(i1;i200;i){ printf user%03d %011d 地址%d\n, i, (i%50)*10000000 int(rand()*9999999), i; }} records_tail.txt(i%50)*10000000让大部分记录的散列关键值落在少数区间能人为制造高冲突。生成后把散列表长分别设为 101 和 211跑同一数据文件冲突次数差异会非常明显。这样写报告时曲线不是一条直线有对比价值。4.4 记录一张可复现的实验对比表你至少需要以下五列表长、α、冲突率、ASL成功、ASL失败。冲突率定义可以用“发生冲突的记录数 / 总记录数”。我在自己的实现里统计的是“插入时发现目标桶非空则冲突1”。多跑几组后填入下面这样的表格表长α冲突率链地址ASL成功链地址ASL失败线性探测ASL成功1011.980.712.235.778.562110.950.481.352.513.975030.400.291.111.421.83数据不用追求完美但必须保证每次实验的散列函数、表长、关键字字段、数据文件都记录下来。答辩老师一定会盯着这张表问“为什么 α1.98 时冲突率反而只有 0.71”你回答“因为链地址法允许一个桶挂多条记录冲突率反映的是桶冲突不是比较次数”能加不少分。4.5 平方取中散列函数的比较题目里提到“设计不同的散列函数比较冲突率”。平方取中对整数值的关键字效果较好先平方再取中间几位。比如电话号码 3456789平方后约 11 位取第 3-5 位int hashSquareMid(const char *phone, int tableSize) { unsigned long num 0; for (int i 0; phone[i]; i) if (isdigit(phone[i])) num num * 10 (phone[i] - 0); unsigned long sq num * num; // 取中间10位再按表长取模 sq (sq / 1000) % 10000000000UL; return (int)(sq % tableSize); }这个函数比除留余数多两次大数运算但能打散电话尾号集中分布的数据。你可以在 main 里通过函数指针切换当前用的散列函数比如int (*hashFunc)(const char*, int) hashSquareMid;然后所有插入和查找处都调用这个指针只需改一行赋值就能换散列函数。相比每个查找函数复制粘贴一套逻辑用函数指针维护更省事也便于答辩时演示“切换散列函数不影响上层逻辑”。5. 实战收尾从 HashArrayHash 到一份能过答辩的课程设计5.1 让程序支持从键盘输入和文件批量导入原始项目要求从键盘输入记录但答辩演示时手动输几十条太费时间。我在 main 里加了一个命令行参数Main -f records.txt批量导入。做法是用 fscanf 按行读取注意处理换行符和中文编码。导入后给用户一个菜单选项1 按电话查、2 按用户名查、3 打印全部记录。打印全部记录时要遍历所有桶和链表这也能直观展示冲突分布。5.2 边界与坑中文用户名、相同电话号码、二次散列中文用户名在 Windows 控制台和 Linux 下的编码不一致导致用同一个字串散列结果不同。解决方案是强制在程序内部使用 UTF-8或直接只支持字母数字。相同电话号码不允许出现否则散列后查找会返回第一条记录需要在插入前先查重。想做亮点可以增加二次散列双散列法冲突时用第二个散列函数计算步长而不是固定 1。代码上改核心就一行int step 1 (idx 10 ? 1 : idx % (ht-tableSize - 1)); idx (idx step) % ht-tableSize;这个步长必须与表长互质否则会漏探测一些位置。5.3 在 VSCode 里配置 C/C 环境跑通 Makefile这个项目提供 Makefile如果你用 VSCode 打开需要先安装 C/C 扩展和 MinGWWindows或 gLinux。在 VSCode 终端执行make clean make ./Main.exe # Windows 下如果报“已检测到匹配的 Visual C Redistributable”错误说明你用的 exe 是从别的机器拷过来的需要在本机重新编译。配置 c_cpp_properties.json 时将 compilerPath 指向本机 g 路径includePath 加上项目根目录。如果 make 命令找不到检查环境变量是否添加了 MinGW 的 bin 目录。5.4 报告写作把冲突率对比和 ASL 变化写进设计报告课程设计报告不必重写系统所有代码重点展示数据流图输入→散列→冲突处理→查找、两种冲突处理的核心函数、实验结果对比表和 ASL 变化折线图。折线图可以用 Excel 画横轴是装载因子 α纵轴是 ASL。答辩老师最常问三件事为什么用散列表冲突怎么处理ASL 是怎么算的掌握第 4 章的统计方案后可以现场拿数据演示。写报告时把对比表放在结论前独立讨论每行数据变化原因比贴大段代码有说服力。本文还有配套的精品资源点击获取