武汉轻工大学 数学与计算机学院
题 目：专 业：班 级：学 号：姓 名：指导老师：
《数据结构》 课程设计说明书
哈希表设计 2014年 12 月 24 日
目录
一、 问题描述
二、 需求分析
1、 基本要求
2、 测试数据
三、 程序流程
四、 详细设计
五、 测试分析
六、 课程设计总结
一、 问题描述
针对班级同学的“名字”设计一个哈希表，使得平均查
找长度不超过R，完成相应的建表和查表程序。
二、 需求分析
基本要求：
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。
测试数据：
取班级同学的30个人的姓名。
三、 程序流程
开始 初始化学生姓名表 输入三十位学生的姓名 根据姓名表生成哈希表 判断所需要的功能 1.显示姓名表 2.显示哈希表 3.查找 4.结束查找 结束 图1.1程序的整体流程
姓名表的创建开始 哈希表的创建开始
表是否溢出 N 表是否 溢出 N Y 对姓名赋值添加到姓名表 将姓名拼音转化为ASCII码并作为 关键字 姓名表的创建开始 图1.2姓名表的创建
Y 对哈希表初始化 表是否溢N 出 Y 用伪随机再探测法解决冲突，对哈希表进行赋值 哈希表的创建开始 图1.3哈希表创建 哈希表的查找开始 char name[20] = { 0 }; int s = 0, sum = 1, adr; scanf_s(\name,20); for (j = 0; j<20; j++) s += toascii(name[j]); adr = s%P;j=0; printf(\姓名:%s 关键字:%d 查找长度为: 1\\n\HashTable[adr].py, s); Y HashTable[adr].m==s&&!strcmp(HashTable[adr].py, name N HashTable[adr].m == 0 while (1){ adr = (adr + d[j++]) % HASH_LEN; sum = sum + 1; if (HashTable[adr].m == 0){ printf(\没有想要查找的人!\\n\if(HashTable[adr].m==s&&!strcmp(HashTable[adr].py, name)){printf(\姓名:%s 关键字:%d 查找长度为:%d\\n\HashTable[adr].py,s, Y 结束
printf(\没有想要查找的人!\\n\sum);break;} 结束 结束 图1.4哈希表的查找