《哈希表实验报告》由会员分享，可在线阅读，更多相关《哈希表实验报告（12页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计报告哈希表问题姓 名 : 郑 健专 业 : 信息管理与信息系统班 级 : 083221学 号 : 08322126指导老师 : 刘自强目 录一，摘 要-1二，设计要求与分析2.1 课程设计要求-22.2 程序分析-2三，数据结构选择与概要设计3.1 数据结构选择-33.2 Hash 函数流程图-49四，设计算法4.1 建立节点-104.2 哈希函数的定义-104.3 哈希查找-114.4 程序测试-11五，使用说明与测试结果5.1 使用说明-115.2 主菜单截图-125.3 添加记录截图-125.4 查找截图-135.5 散列结果截图-135.6 清空记录截图-14摘 要本设
2、计主要要求分别以电话号码和用户名为关键字建立哈希表，并实现查找功能。所以本设计的核心问题是如何解决散列的问题，由于结点的个数无法确认，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”的问题。所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，使用链表结构把同义词链接在一起。首先，解决的是定义链表结点，在链接地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成.name8 、num11和address20都是 char 浮点型采用链地址法，其中的所有同义词构成一个单链表，再由一个表头结点指向
3、这个单链表的第一个结点。这些表头结点组成一个一维数组，即哈希表。二，设计要求与分析2.1 课程设计要求设计哈希表实现电话号码查询系统。设计程序完成以下要求：（1）设每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（3）采用再哈希法解决冲突；（4）查找并显示给定电话号码的记录；（5）查找并显示给定用户的记录。2.2 程序分析具体思路为：（1）对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对 20 求余。得到的数作为地址。对于以用户名为关键字的散列函数，是将所有字母的 ASCLL 码值相加，然后对 20 求余。（2）要添加
4、用户信息，即要有实现添加结点的功能的函数，所以要设计一个必须包括一个输入结点信息、添加结点的函数；（3）要实现查找函数，则必须包括一个查找结点的函数；另外还有一个必不可少的就是运行之后要有一个主菜单，即要设计一个主函数（main()） 。（4）测试数据的选择最后，程序完成后要对程序进行编译调试，执行后要选择数据进行测试，这里选择的测试数据为：1.姓名：郑健；电话：1234567；地址：江西九江；2.姓名：吴任；电话：2345678；地址：江西南昌；3.姓名：黄鑫；电话：3456789；地址：江西上饶；三，数据结构选择与概要设计3.1 数据结构选择本设计涉及到的数据结构为：哈希表。要求输入电话号
5、码、用户名、地址三个信息，并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进行哈希查找。在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链接地址法结点结构如图：name8 num11 address20 next其中 name8和 num11是分别为以电话号码和用户名为关键字域，存放关键字（key） ；address20(data)为结点的数据域，用来存储用户的地址。Next 指针是用来指向下一个结点的地址。四，设计算法4.1 建立节点struct node char
6、name8,address20; char num11; node * next; ; typedef node* pnode; /可以为一个已有的数据类型声明多个别名，这里为该类型声明了两个指针typedef node* mingzi; node *phone; node *nam; node *a;4.2 哈希函数的定义本程序要设计两个 hash（）函数，分别对应电话号码和用户名。对关键字进行模运算，将运算结果所得的余数作为关键字（或结点）的存储地址，方法如下：以电话号码为关键字建立哈希函数 hash(char num11)。以用户名为关键字建立哈希函数 hash2(char name8)
7、。利用强制类型转换，将用户名的每一个字母的 ASCLL 码值相加并且除以 20 后的余数。将计算出来的数作为该结点的地址赋给 key2。void hash(char num11); /以电话号码为关键字建立哈希函数/哈希函数的主旨是将电话号码的十一位数字全部加起来 int i = 3; key=(int)num2; while(numi!=NULL) key+=(int)numi; i+; key=key%20; /利用强制类型转换，将用户名的每一个字母的 ASCLL 码值相加并且除以 20 后的余数 void hash2(char name8); /哈希函数 以用户名为关键字建立哈希函数 i
8、nt i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%20; 4.3 哈希查找想要实现查找功能，同样需要两个查找函数，无论以用户名还是以电话号码为关键字，首先，都需要利用 hash 函数来计算出地址。再通过比对，如果是以电话号码为关键字，比较其电话号码是否相同，如果相同则输出该结点的所有信息，如果以用户名为关键字，则比较用户名是否相同，如果相同则输出该结点的所有信息。如果找不到与之对应相同的，则输出“无此记录” 。void find(char num11) ; /在以电话号码为关键字的哈希表中
9、查找用户信息 hash(num); node *q=phonekey-next; while(q!= NULL) if(strcmp(num,q-num)=0) break; q=q-next; if(q) printf(%s_%s_%sn,q-name,q-address,q-num);else printf(无此记录n); void find2(char name8) ;/ 在以用户名为关键字的哈希表中查找用户信息 hash2(name); node *q=namkey2-next; while(q!= NULL) if(strcmp(name,q-name)=0) break; q=q-
10、next; 4.4 程序测试首先键入 0,添加结点信息,然后按 1 进行查找,分别进行号码和姓名查找,最后可在主菜中，选择号码散列和姓名散列,由此查看程序运行结果。至此，就解决了哈希表的设计与实现算法可能出现的各种问题，那么根据以上思路以及对问题的分析和对出现情况的解决则可以写出源程序。五，使用说明与测试结果5.1 使用说明由于 address20、name8 和 num11可以看出地址可输入的最大字符数是 20，姓名可输入的最大字符数是 8，电话号码都为 11 位。5.2 主菜单截图5.3 添加记录截图5.4 查找截图5.5 散列结果截图5.6 清空记录截图六，程序源代码及实验心得6.1 源
11、代码#include#include #define NULL 0 unsigned int key; unsigned int key2; int *p; struct node char name8,address20; char num11; node * next; ; typedef node* pnode; typedef node* mingzi; node *phone; node *nam; node *a; void hash(char num11) int i = 3; key=(int)num2; while(numi!=NULL) key+=(int)numi; i+
12、; key=key%20; void hash2(char name8) int i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%20; node* input() node *temp; temp = new node; temp-next=NULL; printf(请输入姓名:n);scanf(%s,temp-name);printf(输入地址： n);scanf(%s,temp-address);printf(输入电话：n);scanf(%s,temp-num);return temp; int apend() node *newphone; node *newname; newphone=input(); newname=newphone; newphone-next=NULL; newname-next=NULL; hash(newphone-num); hash2(newname-name); newphone-next = phonekey-next; phonekey-next=newphone; newname-next = namkey2-next; namkey2-
