课程设计试验报告-哈希表的设计与实现

1、数据结构课程设计题目哈希表的设计与实现作者院系信息工程学院专业信息管理与信息系统学号1514210117扌旨导老师张慧答辩时间 2016 年12月18日目录数据结构课程设计01系统需求分析21.1用户需求分析31.2功能需求分析 31.3数据需求分析 31.4小结42系统设计42.1设计内容及要求42.2总体设计思路42.3程序详细设计流程图52.31以姓名为关键字的Hash()函数流程图 52.32添加结点信息流程图: 72.33按姓名查找流程图: 82.34按号码查找流程图92.35 主程序流程图 92.4详细设计编码 112.41建立节点112.42对哈希函数的定义112.43哈希查找1

2、22.44主函数123系统测试133.1上机调试133.2调试结果与分析1418184总结 5附录1系统需求分析在信息化时代的今天，计算机技术已经是发展到一个很可观的地步了，特别是 面向窗口的操作系统的出现，使得程序设计更加的容易了。在过去计算机内存容量 小，CPU计算速度慢，关于程序设计中的数据结构也因此提出来很多的关于解决这 方面的问题。哈希表就是其中之一，哈希表是一个由关键字与值组成的特殊的一种 数据结构。它的出现主要是为了解决在结构中查找记录时需要进行一系列和关键字 的比较,这一类查找方法是建立在“比较”的基础上的，在顺序等的查找中，查找的 效率是依赖于查找过程中所比较的次数。理想的情

3、况是希望不经过任何的比较一次存取便能得到所查记录，那就必须在 记录的存储位置和它的关键字之间建立一个确定的对应关系，使得每个关键字和结 构中一个唯一的存储位置相对应。因而在查找时只要根据这个对应关系找到给定的 值的像。若结构中存在关键字和该值相等的记录，则所要查找的数就必定就是这个 所查找到的记录。哈希函数是建立哈希表的一个重要的成员，它的构造方法分为以下几种：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。本程序中主要用的是除余取留法，除留取余法主要是取关键字被某个不大于哈 希表表长m的数p出后所得余数为哈希地址即：H(key)=key MOtp, p<=m这是一种

4、最简单，也是一种最常用的构造函数的方法，它不仅可以对关键字直接取模，也可 在折叠、平方中等运算之后取模。在哈希表的建立中，很容易出现同义词，这些同义词的出现也导致了建立哈希 表时冲突的出现，如果不解决这些冲突那么建立好的哈希表与预料的哈希表不同。 关于处理冲突的方法主要有：开放定址法、再哈希法、链地址法。本程序中主要用 的就是链地址法莱解决冲突的。1.1用户需求分析设计一个程序能够使用哈希表实现电话号码查询系统。该系统能够从键盘输入 各记录，分别以电话号码和用户名为关键字建立哈希表，能够从输入记录中查找并 显示给定用户的记录，最后并且能够进行清除记录和退出功能。1.2功能需求分析(1) 设计一

5、个结点使该结点包括电话号码、用户名、地址。(2) 利用用户名和电话号码为关键字建立哈希表，哈希函数用除留余数法构照(3) 禾I用链表法处理冲突问题。(4) 查找并显示给定用户名，地址，电话号码的记录。(5) 显示哈希表中的给定用户的记录。(6) 当完成操作后，可以退出系统。1.3数据需求分析由问题分析知，本设计主要要求分别以电话号码和用户名为关键字建立哈希表， 并实现查找功能。所以本设计的核心问题是如何解决散列的问题，亦即设计一个良 好的哈希表。由于结点的个数无法确认，并且如果采用线性探测法散列算法，删除 结点会引起“信息丢失”的问题。所以采用链地址法散列算法。采用链地址法，当 出现同义词冲突

6、时，使用链表结构把同义词链接在一起，即同义词的存储地址不是 散列表中其他的空地址。首先，解决的是定义链表结点，在链地址法中，每个结点对应一个链表结点， 它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表， 所以该链表结点它是由四个域组成.name8 、num11和address20都是char浮 点型，输入输出都只能是浮点型的。采用链地址法，其中的所有同义词构成一个单链表，再由一个表头结点指向这 个单链表的第一个结点。这些表头结点组成一个一维数组，即哈希表。数组元素的 下标对应由散列函数求出的散列地址。1.4小结通过以上需求分析，知道了设计一个哈希表的目的和能够 “实现什

7、么功能”，为 接下来的操作明确方向，罗列了需要运用到的知识，自己应该在接下来的程序设计 和实现应该怎么做。2系统设计2.1设计内容及要求本设计主要要求分别以电话号码和用户名为关键字建立哈希表，并实现查找功 能。本程序的要求是设计散列函数，亦即设计一个良好的哈希表。本程序需要设计 两个散列函数才能解决问题，程序需要分别为以电话号码和用户名为关键字建立哈 希表。所以要分别以用户名、号码为关键字建立两个散列函数，要添加用户信息， 即要有实现添加结点的功能的函数，所以要设计一个必须包括一个输入结点信息、 添加结点的函数；要实现查找函数，则必须包括一个查找结点的函数；另外还有一个必不可少的就是运行之后要

8、有一个主菜单，即要设计一个主函数 (main()。2.2总体设计思路本设计涉及到的数据结构为：哈希表。要求输入电话号码、用户名、地址三个 信息，并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个 哈希函数，进行哈希查找。在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需 要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组 成，链地址法结点结构如图：n ame8nu m11address20n ext其中name8和num11是分别为以电话号码和用户名为关键字域, (key); address20(data) 为结点的数据域，用来存储用户

9、的地址。用来指向下一个结点的地址。存放关键字Next指针是2.3程序详细设计流程图2.31以姓名为关键字的Hash()函数流程图结束1-1姓名为关键字的 Hash()函数流程图2.32添加结点信息流程图1-2添加结点信息流程图2.33按姓名查找流程图2.34按号码查找流程图2.35主程序流程图初始化散列链表(2)并为其动态分配内存空间Menu ()主 菜单1输入选择选6选择1选7选择2进行姓名散列Iist2()选择* 添加记录 apend()0.进行号码散列list()选择3> 清空 creat();creat2()选择4查找号码fin d()输出 结果查找用户find2()号码散列 结

10、果输岀结姓名散列结果.列表已清, 空选择5. 退出系统return 02.4详细设计编码2.41建立节点struct node / 建节点char name8,address20;节点中要包含用户名，用户地址，电话号码以及指向下一个结点的指针char nu m11;node * n ext;；typedef node* pnode; /typedef可以为一个已有的数据类型声明多个别名，这里为该类型声明了两个指针typedef no de* min gzi;node *ph one;node *n am;node *a;2.42对哈希函数的定义void hash(char num11) /以电

11、话号码为关键字建立哈希函数key=(i nt) nu m2;while( nu mi!=NULL)key+=(i nt) nu mi;i+;key=key%20;b)void hash2(char n ame8)以用户名为关键字建立哈希函数int i = 1;key2=(i nt) name0;while( namei!=NULL)key2+=(i nt)n amei;i+;key2=key2%20;2.43哈希查找void find(char num11) /在以电话号码为关键字的哈希表中查找用户信息hash( nu m);node *q=pho nekey->n ext;while(

12、q!= NULL)if(strcmp( nu m,q->num)=0)break;q=q->n ext;if(q)prin tf("%s_%s_%sn",q->n ame,q->address,q->nu m);else printf("无此记录 n");b)、void find2(char name8) /在以用户名为关键字的哈希表中查找用户信息hash2( name);node *q=n amkey2->n ext;while(q!= NULL)if(strcmp( name,q->n ame)=0)brea

13、k;q=q->n ext;if(q)prin tf("%s_%s_%sn",q->n ame,q->address,q->nu m);else printf("无此记录 n");2.44主函数主函数本程序需要创建一个主菜单和一个主函数，主菜单便于用户的使用，主函数中，包 括所有功能对应的数值，使之和主菜单相对应。*主函数界面设计如下*0添加记录1查找记录2姓名散列3号码散列4清空记录5退出系统void menu（） /菜单 system（"color 2d"）;printf（"*n"）pri

14、ntf（"ttt*欢迎使用 *tttn"）； prin tf（"n"）;printf（"tttt 0.添加记录 ttttn"）;printf（"tttt 1.查找记录 ttttn"）;printf（"tttt 2.姓名散列 ttttn"）; printf（"tttt 3.号码散列 ttttn"）; printf（"tttt 4.清空记录 ttttn"）; printf（"tttt 5.退出系统 ttttn"）;3系统测试3.1上机调试1

15、首先键入0,添加结点信息，然后按1进行查找，分别进行号码和姓名查找，最后可在主 菜单中，选择号码散列和姓名散列，由此查看程序运行结果。2语法错误及修改：程序是分块写的，调试时可以使用分步调试的方式进行，以便能查 找看程序是在哪出错了。本算法使用了链表结构和链地址法解决冲突的问题，在以 姓名为关键字的哈希表中要注意涉及ASCLL码的类型转换，要注意输出不能是“d”，否则不能输出结果。编写程序时要多注意程序中各种指针的使用，还有各 类变量的定义，函数的使用。这些问题均可以根据编译器的警告提示，对应的将其 解决。3逻辑问题修改和调整：链表结构方法虽然方便了运行，但是增加了对算法过程的 认识难度。在本

16、程序中每一个函数中都需要涉及到指针的操作。所以需要仔细分析 函数中的指针指向。在插入结点，查找结点时尤为突出。对于主菜单和主函数的对 应，一定要一致，这样才能保证运行时不会出错。4时间，空间性能分析：散列法本质上是一种通过关键字直接计算存储地址的方 法。在理想情况下，散列函数可以把结点均匀地分布到散列表中，不发生冲突，贝U 查找过程无需比较，其时间复杂度 O (n) =1。但在实际使用过程中，为了将范围 广泛的关键字映射到一组连续的存储空间，往往会发生同义词冲突，这时在查找过 程中就需要进行关键字比较。因此散列法的查找性能取决于3个因素：散列函数、冲突处理方法和填充因子。采用链地址法，可以从根

17、本上杜绝“二次聚集”的发生, 从而提高散列表的均匀度，提高查找性能，不过也会“浪费” 一部分散列表的空间。 当散列函数和冲突处理办法固定时，散列法的查找性能就取决于散列表的填充因子。 填充因子a=表中已有的结点数/表的长度。填充因子a标志表的添满程度。很显然， a越小则发生冲突的机会就越小； 反之，a越大冲突的机会就越大，查找的性能也就 越低。哈希表链地址法查找成功的平均查找长度 SNc=1+a/2。链地址法查找不成功的 平均查找长度Un满足：Unc=a+e-a.由以上可以看出，散列表的平均查找长度是填充 因子的函数，和散列表的长度没有关系，因此在实际应用中，我们应该选择一个适 当的填充因子，

18、以便把平均查找长度控制在一个尽量小的范围内。3.2调试结果与分析程序主菜单3UsersAdm in istt atai LieXop Uebu goo.Mce1'KM KWM-MMH M M KM KMMMM KM M M M M M KM M M K M H KM KMMMMM M M M M K-M K H K KM KMB -添扣记录1 .香我记糸氏妊名嵌列証号码欝列乂退岀系貌添加记录:0冃 WMM-MMWXWMKM9 " G Users'llAdmin istrator lAesMop Uebuq ooqxW0详輪人慕谊拥的向容：谨输入姓窑；小明竄入±

19、;n址：rajr輸人氐沿1879152O18BXMX耳X耳XxhxKXXHXHX X”卅耳討耳托X兴X第KXMXkhMX就XHxHHKXXK耳贰制耳KxXkXX料XXHXKXKH科対示录列列录纸 记记談散in系 和U鱼码守H-. 0 12 35小红入:肌址;分别按电话号码和姓名查找B h U WsersI；Adminjsttator L>e£ctop LBebuqoo-eKe'1MM MM M M M MM M K K M M KM KMM;M M;M M M M MMKM M M M M M K M H M M M M KM HMM AM KM M M M M M M

20、 M K M K M MM.K KK M H M KM MX录录爲录绒 ip,记堂散记系 相检窑码空出 価信息馬曲腿 0 12 351&号再香询.T妗卑百询诣輸入电话号码：13S92S303MG轴岀音炭的信息：小紆湖南.1399263G8H®XlrfXMKHHWHMXWHHXHX XX KXXXWWWMMWWJfVXNXXWMX KHXyWHMWMKMKWXWXWMWWXWXXVXMXHX »<X XHXXX：WF材齋建葺抵普%欠i里彳尹WKkfM tf H tf KF V bf W氛移加记录1 .畫找注8姓名散列氛号码載列叭滑宇记录3+很出系誌岳号码査询，了

21、姓名査询?请输入姓名：/卜明竄出胥找鬧信見；小明四_1«7152918«MKM KM MH M M H MM HMM KM KMMKM » M ME-HE M-He H KM MMMMM MM MMM KM M H M M N KMtMM M K M M H MKM M M KMMMMKMKMXHxhmXMKMV I®f? RhxKXMmmXhKX录最列列录统 IP,记核貳话乘 如U.?;匡空出 诉青炉号请迟 -R44I- 0 12 35分别输出按姓名和号码散列的结果B " C:诃 sersl Adm initiator besfctop Ue

22、buqoo!Ke"玮尹 玮*处*芹里 f 总冃 MMHMKHKMHKM氛添加记录 记录 孔対名锻列 氛号码鰹列 耳猜空记录5 退岀系统2莊名能列椿卑：汁紅-細甬3926305 H8小SL酊 _iar«i52ei88MMHMM KHMM HMMMMlri KM KMMMMMEHMM HMXKMMMM HMMMMMMKM MMHH NKMMMMMM MMMK 9N MMKMHMHMH录录列列录统 ip.记核懺记亲 如找忆码空出 质芒芒P用迟 0 12 35.rz 二二； Cl *峠尹齐*x *熬i里使冃玮託* * 尹0.押加记录 1査找记录2 姓宓毓冽 趺号码骸列 叭清宁记录5

23、.退圧索統倉码昶列洁果：厂红 _.139326308*»® 小 9I_Qjn_1t 791529188 小明 _QJfLl«152018SKM KM HM M H H M34 MM HMM KM KMMMM MFM MEM H-He HHM W>ti MMM KM M M M N KMMM M M H M K% MKM H M KMM-MMMHKMXHxhmXMKMV I®f? RhxKXMmmXhKX录最列列录统 IP,记核貳话乘 如U.?;匡空出 诉青炉号请迟 -R44I- 0 12 35清空记录:9 " C: Users Adm i

24、n strator beslctop lllebuqooQe"KM KM M M K K M M M M KMMM H H M M M K M H H H M M KM H MM * MM M M M K M K * K K K KM H M M MMKXXrtKAMKXXXy'|£f HXMXMMKMhKX9.沛卅亍朋1 脊栈记录 g沽散列 g,号码散列 U诵空记录 5”迟出杀踏H枫表已清空:MMH KM MHMM HMM KM KKMMM MEH M M H MMMMM MM MMM WM M H H H N KM KMMMM MM M 94 M M MM M

25、KMkOfMMH耳討耳HxhxX孰KX孜j也彳已冃HXX高XhmHhX”录录列列录统 忻记核散记亲 如U.?;码空出 0 12 35半：4总结经过为期两周的课程设计，此次课程设计时间虽然比较短暂，但是我通过这次实践 学到了很多知识，也了解了自己的很多的不足之处。我是一名信息工程学院的学生， 数据结构对于我来说就显得尤为重要，这也是我必须认真学懂的一门课程。在课程 设计之前，我们已经学习C语言这门课程已经一个学期，对其有了一定的了解，但 是更多的还是停留在学习了解的范围，对里面的好多东西还是很陌生，并不是很熟 练，有着许多欠缺，更多的在运用起来的时候还是感到很不好动手。C语言课堂上许多关于C语言

26、的语法规则，听起来十分枯燥无味，也不容易记住，死记硬背是不 可取的。然而要使用C语言这个工具解决实际问题，又必须掌握它。通过多次上机 练习，对于语法知识有了感性的认识，加深对它的理解，在理解的基础上就会自然 而然地掌握C语言的语法规定。对于一些内容自己认为在课堂上听懂了，但上机实 践中会发现原来理解的偏差，更加巩固了学过的知识，而且在设计的时候学要系统 的知识，也是一个较大的挑战，某一方面知识的欠缺都将影响到整个程序的设计。 我从原来的对这门课程的不懂，到目前的能够独立完成一个小型程序。这次课程设计，重温了和学习了许多有关 c语言的知识，还掌握了一些现实中编程 的一些小技巧，实际的编程能力也得

27、到了历练，本次课程设计对我帮助很多。5附录*#i nclude<stdio.h> #i nclude<stri ng.h>程序源代码*#defi ne NULL 0un sig ned int key; /定义两个关键字un sig ned int key2;int *p;struct node / 建节点每个结点包括用户姓名、地址、电话号码、以及指向下 个结点的指针char n ame8,address20;char nu m11;node * n ext;；typedef node* pnode; /typedef 可以为一个已有的数据类型声明多个别名，这里 为该类

28、型声明了两个指针typedef no de* min gzi;node *ph one;node *n am;node *a;void hash(char num11) /哈希函数，以电话号码为关键字建立哈希函数/哈希函数的主旨是将电话号码的十一位数字全部加起来int i = 3;key=(i nt) nu m2;while( nu mi!=NULL)key+=(i nt) nu mi;i+;key=key%20;void hash2(char name8) /哈希函数 以用户名为关键字建立哈希函数/利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除以20后的余数int i =

29、1;key2=(i nt) name0;while( namei!=NULL)key2+=(i nt)n amei;i+;key2=key2%20;node* input() /输入节点信息，建立结点，并将结点的 next指针指空node *temp;temp = new node; /new的功能是动态分配内存，语法形式：new类型名T (初值列表temp->n ext=NULL;printf("请输入姓名：n");sea nf("%s",temp->n ame);prin tf("输入地址：n");sea nf(&qu

30、ot;%s",temp->address);prin tf(" 输入电话：n");sea nf("%s",temp->nu m);return temp; /对于指针类型返回的是地址int ape nd() /添加节点node *n ewpho ne;node *newn ame;n ewph one=in put();newn ame=n ewph one;n ewph one->n ext=NULL;newn ame->n ext=NULL;hash( newpho ne-> num); /利用哈希函数计算出对

31、应关键字的存储地址hash2( newn ame->n ame);n ewph one->n ext = phon ekey->n ext; /利用电话号码为关键字插入pho nekey-> next=newpho ne; /是采用链地址法，拉链法处理冲突的散列表结构newn ame-> next = namkey2-> next; /利用用户名为关键字插入n amkey2->n ext=newn ame;return 0;void ereate() /新建节点int i;pho ne=new pn ode20;/ 动态创建对象数组for(i=0;i&

32、lt;20;i+)phon ei=new no de;pho nei-> next=NULL;void create2() / 新建节点int i;nam=new min gzi20;for(i=0;i<20;i+)n ami=new no de;nami-> next=NULL;void list() /显示列表int i;node *p;for(i=0;i<20;i+)p=ph on ei->n ext;while(p)prin tf("%s_%s_%sn",p->n ame,p->address,p->nu m);p=p

33、->n ext;void list2() /显示列表int i;node *p;for(i=0;i<20;i+)p=n ami->n ext;while(p)prin tf("%s_%s_%sn",p->n ame,p->address,p->nu m);p=p->n ext;void fin d(char num11) /在以电话号码为关键字的哈希表中查找用户信息hash( nu m);node *q=pho nekey->n ext;while(q!= NULL)if(strcmp( nu m,q->num)=0)break;q=q->n ext;if(q)prin tf("%s_%s_%sn",q->n ame,q->address,q->nu