哈希表的设计与实现，含源代码

《哈希表的设计与实现，含源代码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、课程设计题目:（哈希表的设计与实现的问题）设计哈希表实现建立,查找,插入和删除.于是制作电话号码查询系统完成上述功能。分别以电话号码和用户名为关键字建立哈希表，并实现查找功能。由于结点的个数无法确认，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”的问题。所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，使用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。首先，解决的是定义链表结点，在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是

2、由四个域组成.name[8]、num[11]和address[20]都是char浮点型，输入输出都只能是浮点型的。采用链地址法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链表的第一个结点。这些表头结点组成一个一维数组，即哈希表。数组元素的下标对应由散列函数求出的散列地址。拉链法处理冲突的散列表结构：3、主程序分析本题目最主要的要求是设计散列函数，本程序需要设计两个散列函数才能解决问题，程序需要分别为以电话号码和用户名为关键字建立哈希表。所以要分别以用户名、号码为关键字建立两个散列函数，具体思路为：对于以号码为关键字的散列函数，是将十一个数字全部

3、相加，然后对20求余。得到的数作为地址。对于以用户名为关键字的散列函数，是将所有字母的ASCLL码值相加，然后对20求余。要添加用户信息，即要有实现添加结点的功能的函数，所以要设计一个必须包括一个输入结点信息、添加结点的函数；要实现查找函数，则必须包括一个查找结点的函数；另外还有一个必不可少的就是运行之后要有一个主菜单，即要设计一个主函数（main()）。4、测试数据的选择最后，程序完成后要对程序进行编译调试，执行后要选择数据进行测试，这里选择的测试数据为：1、姓名：张三电话号码：13805690141地址：合肥2、姓名：Jack电话号码：1350040889

4、9地址：Shanghai三、概要设计和数据结构选择本设计涉及到的数据结构为：哈希表。要求输入电话号码、用户名、地址三个信息，并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进行哈希查找。在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地址法结点结构如图：name[8]num[11]address[20]next其中name[8]和num[11]是分别为以电话号码和用户名为关键字域，存放关键字（key）；address[20](data

5、)为结点的数据域，用来存储用户的地址。Next指针是用来指向下一个结点的地址。主要算法的流程图如下：以号码为关键字的Hash()函数流程图取整型num[2]赋给key结束Key=key%20Key=key+(int)num[i]i++i从3开始取num[i]!=0开始以姓名为关键字的Hash()函数流程图取整型name[0]赋给key2结束Key2=key%20Key2+=name[i]i++i从0开始取name[i]不为空开始添加结点信息流程图:利用用户名为关键字插入拉链法处理冲突调用hash()函数调用hash()函数Newname指向newphoneNe

6、wphone=input()结束申请新的结点newphone,newname即新的号码和名字开始申请专利开始按姓名查找流程图:q不为空结束输出无记录输出相应记录q=q->nextq不为空调用hash()函数中新结点q指向phone[key]->next开始按号码查找流程图:开始调用hash2()函数中新结点q指向phone[key]->nextq不为空q=q->nextq不为空输出无记录输出相应记录结束主程序流程图开始Main()初始化散列链表（1）并为其动态分配内存空间初始化散列链表（2）并为其动态分配内存空间Menu（）主菜单输入选择选择1选６选7查找号码

7、find()查找用户find2()输出结果输出结果选择2选择0选择3选择4选择5进行姓名散列list2()姓名散列结果添加记录apend()退出系统return0进行号码散列list()清空creat();creat2()列表已清空号码散列结果结束四、详细设计和编码首先定义结点结构体类型，在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地址法结点结构如图：name[8]num[11]address[20]next其中name[8]和num[11]是分别为以电话号

8、码和用户名为关键字域（key），存放关