《哈希表的设计与实现优质资料》由会员分享，可在线阅读，更多相关《哈希表的设计与实现优质资料（65页珍藏版）》请在金锄头文库上搜索。
1、哈希表的设计与实现优质资料(可以直接使用，可编辑 优质资料，欢迎下载）令胆嗲院计算机科嗲b练水系课程设计报告20072021学年第2学期课程数据结构与算法课程设计名称哈希表的设计与实现学生姓名学号0604011026专业班级06计科（1)指导教师2021年9月课程设计题目：（哈希表的设计与实现的问题设计哈希表实现 号码查询系统。设计程序完成以下要求：(1）设每个记录有下列数据项： 号码、用户名、地址：（2）从键盘输入各记录，分别以 号码和用户名为关键字建立晗希表；(3）采用再哈希法解决冲突；（4）查找并显示给定 号码的记录：（5）查找并显示给定用户的记录。一、问题分析和任务定义1、问题分析要完
2、成如下要求：设计晗希表实现 号码查询系统。实现本程序需要解决以下几个问题：(1)如何设计一个结点使该结点包括 号码、用户名、地址。(2)如何分别以 号码和用户名为关键字建立哈希表。(3)如何利用再晗希法解决冲突。(4)如何实现用晗希法查找并显示给定 号码的记录。(5)如何查找并显示给定用户的记录。2、任务定义由问题分析知，本设计主要要求分别以 号码和用户名为关键字建立晗希表，并实现查找功能。所以本设计的核心问题是如何解决散列的问题，亦即设计一个良好的哈希表。由于结点的个数无法确认，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”的问题。所以采用链地址法散列算法。采用链地址法，当出现同
3、义词冲突时，使用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。首先，解决的是定义链表结点，在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用 号码和用户名为关键字建立晗希表，所以该链表结点它是由四个域组成.name8、numll和address20都是char浮点型，输入输出都只能是浮点型的。采用链地址法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链表的第一个结点。这些表头结点组成一个一维数组，即哈希表。数组元素的下标对应由散列函数求出的散列地址。拉链法处理冲突的散列表结构：3、主程序分析本题目最主要的要求是设计散列函数，本
4、程序需要设计两个散列函数才能解决问题，程序需要分别为以 号码和用户名为关键字建立哈希表。所以要分别以用户名、号码为关键字建立两个散列画数，具体思路为：对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对20求余。得到的数作为地址。对于以用户名为关键字的散列函数，是将所有字母的ASCLL码值相加，然后对20求余。要添加用户信息，即要有实现添加结点的功能的函数，所以要设计一个必须包括一个输入结点信息、添加结点的函数：要实现查找函数，则必须包括一个查找结点的函数；另外还有一个必不可少的就是运行之后要有一个主菜单，即要设计一个主函数(main（）。4、测试数据的选择最后，程序完成后要对程序进行
5、编译调试，执行后要选择数据进行测试，这里选择的测试数据为：l、姓名：张三 号码：地址：合肥2、姓名：Jack 号码：地址：Shanghai三、概要设计和数据结构选择本设计涉及到的数据结构为：哈希表。要求输入 号码、用户名、地址三个信息，并要求分别以 号码和用户名为关键字进行查找，所以本问题要用到两个晗希函数，进行哈希查找。在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用 号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地址法结点结构如图：阳e8I川口Jla抽出s20Inext其中name8和numll是分别为以 号码和用户名为关键字域，存放关键字
6、（key); address20(data）为结点的数据域，用来存储用户的地址。Next指针是用来指向下一个结点的地址。主要算法的流程图如下：以号码为关键字的Hash（）函数流程图开始取整型num2赋给keyi从3开始取Key=key+(int)numii+Key=key%20结束以姓名为关键字的HashO函数流程图开始取整型nameO赋给key2i从0开始取Key2+=nameii+Key2:key%20结束添加结点信息流程图：开始申请新的结点newphone,newname即新的号码和名字Newphone=input()Newname指向newphone调用hash（）函数调用hash（）
7、函数拉链法处理冲突利用用户名为关键字插入结束按姓名查找流程图：开始调用hash（）函数中新结点q指向phonekey-nextq=q-next输出无记录q不为空输出相应记录结束按号码查找流程图：开始调用bash2（）函数中新结点q指向pbonekey-nextq=q-next输出无记录q不为空输出相应记录结束初始化散列链表(1）并为其动态分配内存空间初始化散列链表（2）并为其动态分配内存空间主程序流程图Menu （）主菜单进行姓名散1 list2()添加记录 apend()进行号码散列 list()号码散列结果清空 creat();creat2()列表己清空退出系统 return O结束四、详
8、细设计和编码首先定义结点结构体类型，在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用 号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地址法结点结构如图：In棚esI川其中name8和numll是分别为以 号码和用户名为关键字域（key），存放关键字：address20为结点的数据域（data），用来存储用户的地址信息。next指针是用来指向下一个结点的地址。unsignedintkey和unsignedintkey2分别被定义为 号码和用户名关键字。程序的主要模块如下：串程序部分源代码中串串串串串丰1、建立节点structnodeH建节点cha
9、rname8,address20矿节点中要包含用户名，用户地址， 号码以及指向下一个结点的指针charnum(ll;node*next;typedefnode* pnode; /typedef可以为一个己有的数据类型声明多个别名，这里为该类型声明了两个指针typedefnode*mingzi;node *phone;node肺nam; node*a;2、对哈希函数的定义本程序要设计两个hashO函数，分别对应 号码和用户名。本设计中对散列函数选择的是除留余数法，即对关键字进行模运算，将运算结果所得的余数作为关键字（或结点的存储地址，即H(key)=keymodp，本设计中p取20，然后将计算出
10、来的数作为该结点的地址赋给key。具体方法如下：以 号码为关键字建立哈希函数hash(charnum11）。以用户名为关键字建立哈希函数bash2(charname8）。利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除以20后的余数。将计算出来的数作为该结点的地址赋给key2。程序部分源代码牢牢牢牢牢牢牢牢牢牢串串串串串串串串本本中a),oidhash(charnumll)II以 号码为关键字建立哈希函数key=(int)num2;while(numi!=NULL)key+=(int)numi;1+;key=key%20;b)void bash2(char name8)II以用
11、户名为关键字建立晗希函数inti=1;key2=(int)nameO;while(namei!=NULL)key2+=(int)namei;；key2=key2%20;然后，建立结点，并添加结点，利用链地址法解决冲突。建立结点应包括动态申请内存空间。向结点中输入信息。同时将结点中的next指针等于null。添加结点，首先需要利用晗希函数计算出地址即关键字，其次将该结点插入以关键字为地址的链表后，当然由于分别以用户名和 号码为关键字，所以分两种情况，如果以用户名为关键字则调用void hash2(charname8）函数，并且将结点插入对应的散列链表中，如果以 号码为关键字则调用voidhash
12、(charnumll）函数，并且将结点插入对应的散列链表中。并且，需要两个建立散列链表的函数，分别动态申请一定的空间，用于动态申请散列链表。voidcreat（）用来动态创建以 号码为关键字的链表数组，voidcreate2（）用来动态创建以用户名为关键字的链表数组。串串程序部分源代码串串丰void create()II新建号码节点phonei=newnode;phonei-next=NULL;inti;phone=newpnode20;fl动态创建对象数组for(i=O;inext=NULL;nam=newmingzi20; for(i=O;i20;i叫同样，需要两个显示链表的函数，利用for循环和while语句将表中信息按要求输出来。3.哈希查找想要实现查找功能，同样需要两个查找函数，无论以用户名还是以 号码为关键字，首先，都需要利用hash函数来计算出地址。再通过比对，如果是以 号码为关键字，比较其 号码是否相同，如果相同则输出该结点的所有信息，如果以用户名为关键字，则比较用户名是否相同，如果相同则输出该结点的所有信息。如果找不到与之对应相同的，则输出“无此记录，。程序
