哈希表的设计与实现优质资料(可以直接使用，可编辑优质资料，欢迎下载）令胆嗲院计算机科嗲b练水系课程设计报告20072021学年第2学期课程数据结构与算法课程设计名称哈希表的设计与实现学生姓名学号0604011026专业班级06计科（1)指导教师2021年9月课程设计题目：（哈希表的设计与实现的问题〉设计哈希表实现号码查询系统。设计程序完成以下要求：(1）设每个记录有下列数据项：号码、用户名、地址：（2）从键盘输入各记录，分别以号码和用户名为关键字建立晗希表；(3）采用再哈希法解决冲突；（4）查找并显示给定号码的记录：（5）查找并显示给定用户的记录。一、问题分析和任务定义1、问题分析要完成如下要求：设计晗希表实现号码查询系统。实现本程序需要解决以下几个问题：(1)如何设计一个结点使该结点包括号码、用户名、地址。(2)如何分别以号码和用户名为关键字建立哈希表。(3)如何利用再晗希法解决冲突。(4)如何实现用晗希法查找并显示给定号码的记录。(5)如何查找并显示给定用户的记录。2、任务定义由问题分析知，本设计主要要求分别以号码和用户名为关键字建立晗希表，并实现查找功能。所以本设计的核心问题是如何解决散列的问题，亦即设计一个良好的哈希表。由于结点的个数无法确认，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”的问题。所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，使用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。首先，解决的是定义链表结点，在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用号码和用户名为关键字建立晗希表，所以该链表结点它是由四个域组成.name[8］、num[ll］和address[20］都是char浮点型，输入输出都只能是浮点型的。采用链地址法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链表的第一个结点。这些表头结点组成一个一维数组，即哈希表。数组元素的下标对应由散列函数求出的散列地址。拉链法处理冲突的散列表结构：｜｜｜｜｜3、主程序分析本题目最主要的要求是设计散列函数，本程序需要设计两个散列函数才能解决问题，程序需要分别为以号码和用户名为关键字建立哈希表。所以要分别以用户名、号码为关键字建立两个散列画数，具体思路为：对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对20求余。得到的数作为地址。对于以用户名为关键字的散列函数，是将所有字母的ASCLL码值相加，然后对20求余。要添加用户信息，即要有实现添加结点的功能的函数，所以要设计一个必须包括一个输入结点信息、添加结点的函数：要实现查找函数，则必须包括一个查找结点的函数；另外还有一个必不可少的就是运行之后要有一个主菜单，即要设计一个主函数(main（））。4、测试数据的选择最后，程序完成后要对程序进行编译调试，执行后要选择数据进行测试，这里选择的测试数据为：l、姓名：张三号码：地址：合肥2、姓名：Jack号码：地址：Shanghai三、概要设计和数据结构选择本设计涉及到的数据结构为：哈希表。要求输入号码、用户名、地址三个信息，并要求分别以号码和用户名为关键字进行查找，所以本问题要用到两个晗希函数，进行哈希查找。在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地址法结点结构如图：｜阳e[8]I川［口Jla抽出s[20]Inext其中name[8］和num[ll］是分别为以号码和用户名为关键字域，存放关键字（key);address[20](data）为结点的数据域，用来存储用户的地址。Next指针是用来指向下一个结点的地址。主要算法的流程图如下：以号码为关键字的Hash（）函数流程图开始取整型num[2］赋给keyi从3开始取Key=key+(int)num[i]i++Key=key%20结束以姓名为关键字的HashO函数流程图／开始取整型name[O］赋给key2i从0开始取Key2+=name[i]i++Key2:::key%20结束添加结点信息流程图：开始申请新的结点newphone,newname即新的号码和名字Newphone=input()Newname指向newphone调用hash（）函数调用hash（）函数拉链法处理冲突利用用户名为关键字插入