《数据结构》课程设计报告
2.2.2.链地址法
当存储结构是链表时，多采用链地址法。用链地址法处理冲突的办法是：把具有相同散列地址的关键字（同义词）值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表，同时用指针数组T[0...m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到T[i]为指针的单链表中。T中各分量的初值应为空指针。链地址法解决冲突后创建的散列表如图2所示。
用链地址法处理冲突，虽然比开放地址法多占用一些存储空间用做链接指针，但它可以减少在插入和查找过程中同关键字的平均比较次数（平均查找长度）。这是因为，在链地址法中待比较的节点都是同义词节点，而且包含有非同义词结点，往往非同义词结点比同义词结点还要多。
图 2散列表
本程序采用二次探查再散列法解决冲突。
5
《数据结构》课程设计报告
3.详细设计
3.1.涉及的知识点
散列表的建立 散列表的查找 冲突的解决
3.2.详细的设计思路
3.2.1算法的基本思路描述
输入教师信息时会产生冲突，于是我们构建了二次探测函数来解决冲突，再者应把人名进行折叠处理，然后除留取余数法取得哈希模值，才能用于二次探索。建立好哈希表后，就要以人名和电话号码形式查找信息，就要构造两个函数，最后构建一个主函数起调用作用，将各个函数相互组合串联在一起，形成了具有某种功能的一个小系统。 3.2.2 算法的设计 数据结构的设计和说明:
在设计中运用到了两个结构体，Record结构体中主要包含三项，一个是姓名，电话号码和地址，另一个结构体中有数据元素存储地址，当前数据元素的个数和当前容量。在主函数中首先输出菜单界面，显示菜单界面供使用者选择要操作的序号。当操作者选择出序号后在，switch调用相应的函数。使用者只要根据提示进行操作即可。
1-添加教师信息2-读取所有教师信息 3-以姓名建立哈希表 4-以电话号码建立哈希表 5-查找并显示给定教师的记录 6-查找并显示给定电话号码的记录 7-删除教师的信息8-修改教师的信息9-清屏10-退出程序。
6
《数据结构》课程设计报告
3.2.3程序的总流程图
程序开始输入口令显示菜单输入操作码i录入指定输入个数的建立教师通信录i=1i=2显示教师的信息i=3以姓名为关键字来创建哈希函数i=4以电话号码为关键字来创建哈希函数i=5以姓名为关键字来查找教师信息i=6以电话号码为关键字来查找教师信息i=7删除教师的信息i=8修改教师的信息i=9清屏i=10退出程序结束图 3程序总流程图
7
《数据结构》课程设计报告
A：基本信息：
定义节点类型----typedef struct Record
定义哈希表节点类型----typedef struct HashTable 关键字比较----void eq()
人名的折叠处理，将名字转换成一个数值----void fold() 建立哈希函数----void Hash()
建立解决冲突的方法----void collision() B:显示菜单：
按照指定的长度建立通信录 显示通信录内所有教师信息 添、删、修教师信息
查找并显示给定教师姓名的记录 查找并显示给定电话号码的记录 显示信息并退出程序 C：根据选项实际操作
主函数void main()分别调用下面函数并对应输出 录入内存内容----void gein() 显示教师信息----void list() 创建哈希表----void createdHash1()
查找哈希表中的关键字----void Search_name()/Search_phonenumber() 删除教师的记录----void Delete() 修改教师的记录----void Alter()
8
《数据结构》课程设计报告
4.编码
4.1常量的定义
1.MAXSIZE 20：通讯录的大小
2.MAX_SIZE 20 ：通讯录中姓名、电话、地址的最大长度 HASHSIZE 53 ：创建哈希表的容量 SUCCESS 1 ：成功标志位 FAILURE -1 ：失败标志位
LEN sizeof(HashTable)：哈希表的长度
4.2数据结构定义
所用数据结构参考定义如下： （1）定义通信录节点结构体 typedef struct{ //每个教师记录
NA name; NA tel; NA add; }Record;
（2）定义哈希表节点结构体
typedef struct{ //哈希表
Record *elem[HASHSIZE]; //数据元素存储基址 int count; //当前数据元素个数 int size; //当前容量 }HashTable;
9