数据结构课程设计哈希表设计

1、题目学院专业班级姓名指导教师哈希表设计计算机科学与技术计算机科学与技术目录TOC o 1-5 h z HYPERLINK l bookmark2 o Current Document 1问题描述3 HYPERLINK l bookmark4 o Current Document 问题描述3 HYPERLINK l bookmark6 o Current Document 大体要求3 HYPERLINK l bookmark8 o Current Document 测试数据3 HYPERLINK l bookmark10 o Current Document 实现分析3 HYPERLINK l

2、bookmark12 o Current Document 3程序设计4存储结构设计4函数模块7程序流程图7 HYPERLINK l bookmark14 o Current Document 调试报告9 HYPERLINK l bookmark16 o Current Document 调试中的问题9 HYPERLINK l bookmark18 o Current Document 对设计和编码的讨论和分析9 HYPERLINK l bookmark20 o Current Document 程序运行结果10 HYPERLINK l bookmark22 o Current Documen

3、t 体会和体会11感受和体会11 HYPERLINK l bookmark24 o Current Document 对算法改良的方式13 HYPERLINK l bookmark26 o Current Document 哈希表和源程序13 HYPERLINK l bookmark28 o Current Document 哈希表13 HYPERLINK l bookmark30 o Current Document 源程序15课程设计任务书学生姓名：专业班级：班指导教师：工作单位：运算机科学系题目:哈希表设计初始条件：针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找

4、长度不超过R,完成相应的建表和查表程序。假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处置冲突。测试用例见题集p166。要求完成的要紧任务:（包括课程设计工作量及其技术要求，和说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包括如下内容：一、问题描述简述题目要解决的问题是什么。2、设计存储结构设计、要紧算法设计（用类C语言或用框图描述）、测试用例设计；3、调试报告调试进程中碰到的问题是如何解决的；对设计和编码的讨论和分析。4、体会和体会（包括对算法改良的假想）5、附源程序清单和

5、运行结果。源程序要加注释。若是题目规定了测试数据，那么运行结果要包括这些测试数据和运行输出，6、设计报告、程序不得彼此剽窃和拷贝；假设有类似，那么所有类似者成绩均为0分。时刻安排：一、第19周完成。二、7月1日14：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。指导教师签名：年月日系主任（或责任教师）签名：年月日课程设计报告书1问题描述问题描述针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R,完成相应的建表和查表程序。大体要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪

6、随机探测再散列发处置冲突。测试数据取自己班级成员的名字作为测试数据，成立一个相关哈希表，并计算平均查找长度，完成查询。2.实现分析（1）针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的成立和查表程序。（2）人名为汉语拼音形式，最长不超过19个字符（如：庄双双zhuangshuangshuang）。（3）假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用伪随机探测在散列法处置冲突。（4）若是随机函数自行构造，那么应第一调整好随机函数，使其散布均匀。字符的取码方式可直接利用C语言中的toascii函数，并可对太长人名先进行折叠处置。（5）查找

7、成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度。3程序设计存储结构设计依照哈希函数可唯一确信一个记录的地址，在理想情形下，记录就能够够依照那个存储地址进行存储。因此哈希表的存储结构能够是链表和线性表，但一样情形下选择线性表进行存储。本次课程设计用到的存储结构如下：typedefstructchar*name;ame=fanxu;NameL=jiangyong;NameL=guyuze;NameL=liuzhenhai;NameL=chenang;NameL=caoyandong;NameLi

8、=yangchenchen;NameL=shenjin;NameL=puping;NameL=luhaibo;NameL=renchao;NameL=wangshichuang;NameL=guoqihui;NameL=chengkang;NameL=wangyuesong;NameL=liangfangping;NameL=wangxufeng;NameL=heji

9、e;NameL=yangyiming;NameL=wushengping;NameL=yangchaoqin;NameL=wulinfeng;NameL=xiehongwei;NameL=liushuo;NameL=yijiabin;NameL=xuhaiyang;NameL=yangwenjuan;NameL=chenjunyan；NameL=wangjiaxin;NameL

10、=chenwan;for(i=0;ivNAMENO;i+)sO=O;f=NameL;for(r=0;*(f+r)!=0;r+)/*哈希地址方法：将字符串的各个字符所对应的ASCII码相加，所得的整数作为哈希表的关键字*/s0=*(f+r)+s0;NameListi.k=sO;成立哈希表用除留余数法构建哈希函数用伪随机探测再散列法处置冲突构建哈希函数voidCreateHashList()的实现：voidCreateHashList()inti;for(i=0;ivHASH_LENGTH;i+)HashListi.py=;HashListi.k=0;Hash

11、Listi.si=0;for(i=O;ivHASH_LENGTH;i+)intsum=0;intadr=(NameListi.k)%M;i=0)=NameListi.k;HashListadr.py=NameListi.py;HashListadr.si=1;else%10+1)%M;!=0);HashListd.k=NameListi.k;HashListd.py=NameListi.py;HashListd.si=sum+1;查找哈希表假设查找成功，那么输出姓名、关键字和查找长度；查找失败，那么返回相应的失败信息。查找函数voidFindList()的实现：voidFindList()=s

12、0)y,s0);else讦(HashListadr.k=0)printf(无此记录!)；elseintg=0；dod=(d+s0%10+l)%M;=0)printf(无此记录！)；g=1；if(HashListd.k=s0)printf(n姓名:%s关键字:%d查找长度为:d,HashListd.py,s0,sum);g=1;while(g=0);3)显示哈希表显示哈希表的的格式：n地址t关键字tt搜索长度tH(key)t姓名n显示哈希表的函数voidDisplay()的：voidDisplay。;printf(tt%d,HashListi.si);printf(tt%d,HashListi.

13、k%M);printf(t%s,HashListi.py);printf(n);for(i=0;ivHASH_LENGTH;i+)average+=HashListi.si;average/=NAME_NO;printf(n平均查找长度：ASL(%d)=%fn,NAME_NO,average);(4)主函数设计voidmain()charch1;InitNameList();CreateHashList();doprintf(D.显示哈希表nF.查找nQ.退出n请选择：“)；cin&ch1;switch(ch1)caseD:Display();coutvvendl;break;caseF:Fi

14、ndList();coutvvendl;break;caseQ:exit(O);coutvvcomeon!(y/n):;cinwhile(chl!=n);函数模块模块挪用关系主函数模块输出模块查找模块哈希表模块姓名初始化模程序流程图本次程序流程图如下Q调试报告调试中的问题通过对哈希表的研究后，即进行程序的设计和编码；将原程序编好后，通过编译，有如下几个问题：在声明了结构体NAME后，最开始结构体内的charname20用来寄存姓名拼音，最长为20位；经分析，name表示所存姓名拼音的首地址，无需再申明具体的数组长度来寄存姓名拼音，如此增加了系统的开销，最后改成char*name，对寄存姓名拼音

15、时直接对name赋值，系统直接依照字符数组来寄存姓名拼音，而寄存长度没有固定。成立哈希表的函数：voidCreateHashList()中，若是碰到冲突后，在dowhile()；语句中，利用伪随机探测再散列法处置冲突，没执行一次就要将记录查找长度的sum增加一次，在那个循环执行完后，即找到一个不冲突的地址来寄存姓名拼音，通过自习分析，现在的查找长度需要加1，即将原先的语句HashListd.si=sum;改成HashListd.si=sum+1;现在的HashListd.si才是正确的查找长度。main函数中的dowhile()语句中，最开始while()语句是：while(a!=Nlla!=

16、n)通过度析，在用户需要退出时，不论输入a=N仍是a=n，都将继续循环；通过自习试探，最终将while()语句改成：while(a=Ylla=y)，如此就实现了用户的选择。对设计和编码的讨论和分析算法采纳结构体和数组来存储数据，利用除留余数法取得哈希地址，利用为随机序列法来处置冲突，姓名拼音的关键字为字符串的各个字符所对应的ASCII码相加，所得的整数。求哈希地址时模为51，哈希表的总长度为50，而实际名字只有30个，因此有20个地址空间被空闲着，这浪费了必然的内存。算法的时刻复杂度为：O(n)。平均查找长度为：装填因子为：30/50=程序运行结果通过对程序错误的修改后，程序执行，通过度析，程

17、序运行结果正确，知足题目要求！运行结果要紧截图如下：程序开始后，初始界面为:84700011910736777081093408106497S10G272408755171383974107501072107301010011101111141131682626180121816G131110H0请选择:yijiabinFzCDocumentsandSettingsAdministrato”莫面S据结构谍设呛希表潘眄DebugHash,79446i00321040175402i关键字0搜索长度1姓名uang.itaxinltuzhenhaichenJunyanxuhaiyanguangshic

18、huangheJieguaqihuichenangfwangxufmnmuulinfeng1ymngyiminmchengkangguyuneliushuorenchaoi/anuenjuanluhaibochenuanxtehonguei000039264748邨350B0003437结果显示，平均查找长度为，符合题设要求！选择Y继续后选择F查找查找成功结果为：继色毛乩退岀次g-显下哈希表P-杳找Q-退出请迭择；F.请输入姓名的拼音:pupring姓:pupinq关悻字=69杳栈长度为：1Y继妹乩退出：.查找失败结果为：V音-拼出丈口F名t-N.押姓录续鲂择A记续绷显选输此继体会和体会感受和

19、体会数据结构这门课程是运算机专业一门基础性学科，重要性可见一斑，学好这门课程对以后人一辈子的进展具有深远的阻碍。而数据结构的课程设计即是对学习成效的查验。数据结构课程设计不仅能够锻炼咱们独立试探问题、解决问题的能力，而且能够培育咱们的整体性思维的能力；通过课程设计，使我了解了很多数据结构的经典问题和经典算法，加深了对数据结构的再熟悉，巩固了数据结构的基础性知识，比如：存储结构、数据查找、哈希表的设计和查找、算法分析等。哈希表是依照关键码值而直接进行访问的数据结构，它把关键码值通过哈希函数映射到表中一个地址来存储记录，以加速查找的速度。哈希函数的构造方式有：直接寻址法、数字分析法、平方取中法、折

20、叠法、随机数法、除留余数法等；关于地址冲突要进行解决，要紧解决冲突的的方式有：开放寻址法（线性探测再散列、二次探测再散列、伪随机探测再散列）、再散列法、链地址法、成立一个公共溢出区等。查找进程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，阻碍产生冲突多少的因素，也确实是阻碍查找效率的因素。阻碍产生冲突多少有以下三个因素：散列函数是不是均匀、处置冲突的方式、散列表的装填因子。通过查找相关资料还了解了闻名的hash算法：MD4、MD五、SHA-1及其他。哈希表的要紧用途为：文件校验、数字签名、鉴权协议等。这也是关于以后继续研究数据结构所必

21、需了解的知识。这次课程设计，我明白了关于编写程序，解题的思路尤其重要。在编写程序之前，若是没有比较清楚的思路，全然不可能编出好的程序。就算马马虎虎的编出来，程序的逻辑性、健壮性、完善性、合理性也可不能很强。在编程之前，咱们应反复研究题目要求，对题目涉及的情形进行比较充分的分析，以便编写出加倍符合题意的程序；第二要充分考虑各类临界情形，对一些错误的输入进行处置。因此在咱们编程序之前必然要做好充分的预备，第一要理清自己的思路，然后再将思路分划成几个模块，逐块的写好算法，最后再将所有的模块有机的联系起来，组成一个完整的程序。在成功通过编译的情形下，对程序运行的结果进行系统的分析，查验其正确性，若是有

22、错误，应当即去分析源程序的逻辑错误，直到取得正确的结果。在这次课程设计的进程中，我也碰到了很多难题。在各类的困难中，我明白了在编写程序时要有耐心。若是你没有耐心，即便再好的算法思路也可不能取得专门好的表达，专门是在调试的进程中，关于各类各样的错误，要专门的有耐心去自习分析缘故，专门是一些大体的语法错误，不能一看到错误很多就乱了阵脚，更不能轻易的舍弃，半途而废。比如在调试中没有概念某些变量的错误、大体的输入输犯错误、数据选取不合理的错误、变量名前后不一的错误、函数返回值的错误等等。其实只要有耐心，你就会发觉，在你修改了一个错误以后，其它有的错误也会随着消失，因此在编译的时候必然要有耐心。数据结构

23、是一门比较难的课程，需要花很多的时刻去不断地练习和实践。要想把这门课程学勤学精并非一件容易的事，专门是一些经典算法，是几十年前人聪慧的结晶，关于初学者的明白得和应用有必然的难度；可是事在人为，只要肯下功夫，便必然能够学好。总的来讲，这次程序设计让我获益匪浅，相信在以后的学习生活中我也能从中取得启发。对算法改良的方式本次哈希表的设计采纳的存储结构为顺序存储，如此的存储结构简单易操作，可是必需实现给定存储大小，如此无益于动态操作，在题目许诺的情形下，能够采纳链式存储结构，从而实现动态存储；对关键字的选取还能够依照各个姓名的字母表的顺序等方式，哈希地址的除留余数法的模还能够是其他的接近表长的素数，解

24、决冲突的伪随机序列取余的模长也能够是其他的接近表长的素数；本次哈希表的总长度为50，而实际只用到了30个，还余下20个空闲地址被白白浪费了，能够在知足题目要求的情形下适当的选取小一点的总表长。哈希表和源程序哈希表通过度析，最后取得的哈希表如下：搜索长度地址存储内容关键字H(key)10(null)0011wangjiaxin1072112liuzhenhai1073243(null)0014chenjunyan1075415xuhaiyang974516wangshichuang1383617hejie517718guoqihui87580900110chenang72410111wangxu

25、feng108211212wulinfeng9756113yangyiming1084130140001500116chengkang9341601700118guyuze6811801900220liushuo7771202100122renchao7362202300424yangwenjuan11911802500126luhaibo74026227chenwan74026328xiehongwei107980290003000131yijiabin847310320003300134wangyuesong120734135yangchenchen125935136fanxu546361

26、37shenjin7513703800139caoyandong1059390400004100042000430004400245liangfangping136539346wushengping119926147puping65947148jiangyong96648249yangchaoqin117048源程序整个程序的源代码为：#includev#includev#include#defineHASH_LENGTH50ame=fanxu;NameL=jiangyong;NameL=guyuze;NameL=liuzhenhai;Na

27、meL=chenang;NameL=caoyandong;NameL=yangchenchen;NameL=shenjin;NameL=puping;NameL=luhaibo;NameL=renchao;NameL=wangshichuang;NameL=guoqihui;NameL=chengkang;NameL=wangyuesong;NameL=liangfan

28、gping;NameL=wangxufeng;NameL=hejie;NameL=yangyiming;NameL=wushengping;NameL=yangchaoqin;NameL=wulinfeng;NameL=xiehongwei;NameL=liushuo;NameL=yijiabin;NameL=xuhaiyang;NameL=yangwenjuan;NameLi

29、=chenjunyan;NameL=wangjiaxin;NameL=chenwan;for(i=0;ivNAME_NO;i+)s0=0;f=NameL;for(r=0;*(f+r)!=0;r+)/*哈希地址方法：将字符串的各个字符所对应的ASCII码相力口，所得的整数做为哈希表的关键字*/sO=*(f+r)+sO;NameListi.k=sO;voidCreateHashList()ame=;HashListi.k=O;HashListi.si=0;for(i=0;ivHASH_LENGTH;i+)intsum=0;intadr=(NameListi.k)%M;i=0)=NameListi.k;HashL=NameL;Hash