数据结构试验答案数据结构课程设计--哈希表设计

1、课程设计课程名称数据结构题目名称哈希表设计学生学院计算机学院专业班级07级网络工程2班学号3207007022学生姓名刘晓慧指导教师杨劲涛2009年6月28日一,问题描述1问题描述针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表，使得平均查找长度不超过R,完成相应的建表和查表程序。2.基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。二.需求分析(1)针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R,完成相应的建立和查表程序。(2)人名为汉语拼音形式，最长不超过19个

2、字符(如：庄双双zhuangshuangshuang)。(3)假设待填入哈希表的人名有30个，平均查找长度的上限为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。(4)在输入人名过程中能自动识别非法输入，并给与非法输入的反馈信息要求重新输入。(5)查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度三.程序设计1 .存储结构设计typedefstructchar*py;/名字的拼音intk;/拼音所对应的整数NAME;typedefstruct/哈希表char*py;/名字的拼音intk;/拼音所对应的整数intsi;/查找长度HASH;2 .主要算法设计(1) 姓名(结

3、构体数组)初始化名字以拼音的形式够成字符串，将字符串的各个字符所对应的ASCII码相加,所得的整数做为哈希表的关键字。voidInitNameList()char*f;intr,s0,i;NameList0.py="chenliang"/陈亮NameList1.py="chenyuanhao"/陈元浩NameList2.py="chengwenliang"/程文亮NameList3.py="dinglei"丁磊NameList4.py="fenghanzao"/冯汉枣NameList5.py=&

4、quot;fuzongkai"/付宗楷NameList6.py="hujingbin"/胡劲斌NameList7.py="huangjianwu"/黄建武NameList8.py="lailaifa"/赖来发NameList9.py="lijiahao"李嘉豪NameList10.py="liangxiaocong"/梁晓聪NameList11.py="linchunhua"/林春华NameList12.py="liujianhui"/刘建辉Na

5、meList13.py="luzhijian"卢志健NameList14.py="luonan"/罗楠NameList15.py="quegaoxiang"/阙高翔NameList16.py="sugan"/苏渔NameList17.py="suzhiqiang"苏志强NameList18.py="taojiayang"/陶嘉阳NameList19.py="wujiawen"/吴嘉文NameList20.py="xiaozhuoming"

6、;/肖卓明NameList21.py="xujinfeng"/许金峰NameList22.py="yanghaichun"/杨海春NameList23.py="yeweixiong"叶维雄NameList24.py="zengwei"/曾玮NameList25.py="zhengyongbin"/郑雍斌NameList26.py="zhongminghua"/钟明华NameList27.py="chenliyan"/陈利燕NameList28.py=&qu

7、ot;liuxiaohui"/刘晓慧NameList29.py="panjinmei"/潘金梅for(i=0;i<NAME_NO;i+)s0=0;*/将字符串的各个字符所对应的ASCII码相加，所f=NameListi.py;for(r=0;*(f+r)!=''0'r+)得的整数做为哈希表的关键字*/s0=*(f+r)+s0;NameListi.k=s0;)(2) 建立哈希表(1)用除留余数法构建哈希函数(2)用伪随机探测再散列法处理冲突voidCreateHashList()inti;for(i=0;i<HASH_LENGTH

8、;i+)HashListi.py=""HashListi.k=0;HashListi.si=0;)for(i=0;i<HASH_LENGTH;i+)intsum=0;intadr=(NameListi.k)%M;哈希函数intd=adr;if(HashListadr.si=0)如果不冲突HashListadr.k=NameListi.k;HashListadr.py=NameListi.py;HashListadr.si=1;)else冲突dod=(d+NameListi.k%10+1)%M;伪随机探测再散列法处理冲突sum=sum+1;查找次数加1while(Has

9、hListd.k!=0);HashListd.k=NameListi.k;HashListd.py=NameListi.py;HashListd.si=sum+1;(3) 查找哈希表在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度voidFindList()/查找charname20=0;ints0=0,r,sum=1,adr,d;printf("请输入姓名的拼音：")；scanf("%s",name);for(r=0;r<20;r+)求出姓名的拼音所对应的整数(关键字)s0+=namer;adr=s0%M;/使用哈希

10、函数d=adr;if(HashListadr.k=s0)分3种情况进行判断printf("n姓名:%s关键字:%d查找长度为：1",HashListd.py,s0);elseif(HashListadr.k=0)printf("无此记录!");elseintg=0;dod=(d+s0%10+1)%M;/伪随机探测再散列法处理冲突sum=sum+1;if(HashListd.k=0)printf("无此记录！");g=1;if(HashListd.k=s0)printf("n姓名:%s关键字:%d查找长度为：d",H

11、ashListd.py,s0,sum);g=1;while(g=0);(4)显示哈希表显示哈希表的的格式：n地址t关键字tt搜索长度tH(key)t姓名nvoidDisplay()inti;floataverage=0;printf("n地址t关键字tt搜索长度tH(key)t姓名n");显示的格式for(i=0;i<50;i+)printf("%d",i);printf("t%d",HashListi.k);printf("tt%d",HashListi.si);printf("tt%d"

12、;,HashListi.k%M);printf("t%s",HashListi.py);printf("n");for(i=0;i<HASH_LENGTH;i+)average+=HashListi.si;average/=NAME_NO;printf("n平均查找长度：ASL(%d)=%fn",NAME_NO,average);(5)主函数设计voidmain()charch1;InitNameList();CreateHashList();doprintf("D.显示哈希表nF.查找nQ.退出n请选择："

13、);cin>>&ch1;switch(ch1)case'D':Display();cout<<endl;break;case'F':FindList();cout<<endl;break;case'Q':exit(0);cout<<"comeon!(y/n):"cin>>&ch1;while(ch1!='n');四.编程环境:VC+6.0五.调试报告及体会1 .测试用例程序运行结果程序运行后显示如下：哈希t哈希表设_计5计11於g处.e

14、xe,显示哈希表-查找选择;(1)选择D查找，显示哈希表和平均查找长度，其中平均查找长度小于2,符合题目要求：Q"F：'哈希1哈希表设计Xlhbw'HaBli.金力h.退出懵选择;址t012345678901234FO6787012345&78?0123456789批IS1Z34J67871111111111222222222233333333334444444444关键字搜索长度116720211771Htkey>姓名37yliunZquesaoxian873000011089761118B17108109613799749588819955g1057

15、054212?57328741W63Q0095597401298107183397410740£53117171339100037chensrwenliantr8lluxiAohui9z&n9wci18huanfjianwii0IBsuHhiqianH心015岁Eu电±xzLnng18liangxiaoconff34xujinFeng18hujinbin020lallaifft15chenlxvan023fenffhAhzao025sun26zhongmijnsfliua27dinglei28uujiftuen29taojiayans(00ISpanjinnei34

16、Fuzonsfkai029zhefigyonsfhin37linehuahua34lijifthao34lushijian40liujianliui42luonan49chenipufinliao44chen1-ian945xiaozhuoiDins000平均查找长度：ASL<30>=1omenn，4/n=(2)选才?F查找，输入要查找的人的姓名，若存在则显示名字和对应的关键字以及查找长度；若不存在则显示无此记录：D.显小哈希表F.4-退出请选择：F请输入姓名的拼音：Uuxiaohui姓名二liicciaoluii关键字:1晚查找长度为：1cotiteonf<y/n>：

17、yBl显小哈希表F.查卓Q1退出请选*F请输入姓名的拼音:xadssd无巡记录，comeon*<y/n>：(3)选择Q退出，如要继续可按任意键:corfon，y/r»>：yD.显小哈希表F.查找Q.退出请选南Qrressanykeytocontinue2 .时间复杂度O(n)3 .经验和体会经过这次课程设计的学习，让我明白了编写程序的思路是很重要的。在你编写一个程序之前，如果你的脑袋里面没有思路，根本就不可能编出好的程序。就算能编出程序来，相信编出的程序的逻辑性也不会很强，因为你是想到什么就编什么，不系统。因此在我们编程序之前一定要做好充分的准备，首先要理清自己的思

18、路，然后再将思路分划成几个模块，一块一块的编写，最后再将所有的模块联系起来，组成一个完整的程序。在上机实验之前，最好将程序编写好在草稿纸上，这样在编译的时候也比较有效率。其实在这次课程设计的过程中，我也遇到了很多难题。在种种的困难中，我明白了耐心在编写程序时的重要性。如果你没有耐心就肯定编不出好的程序，特别是在调试的过程中。我们初次写的程序在电脑上调试的时候也许会出项几百个错误，这时候我们应该耐心的检查出错的地方和原因，并予以改正，而不是抱怨自己写的程序太烂错误太多，就此放弃。相信再强的人也不可能一次就能编译成功，总会有一些问题出现。其实只要有耐心，你就会发现，在你修改了一个错误之后，其它有的

19、错误也会跟着消失，所以在编译的时候一定要有耐心。这段时间的课程设计，我也认识到数据结构是一门比较难的课程，需要花很多的时间去练习和实践。要想把这门课程学好学精不是一件容易的事，但是相信事在人为，只要肯下功夫就一定能学好。总的来说，这次程序设计让我获益匪浅，相信在以后的学习生活中我也能从中获得启发。六.用户使用说明详细视图请参考调试报告程序运行初显示如下通选画F请输入姓名的拼音门iuxiaohui姓名:liuxianhui关键字二108y查找长度为二1从中选择需要做的操作，输入对应的操作D、F、Q,并按回车，输入错误时,会显示“无此记录！”；正确时，显示姓名，关键字以及查找长度。0-显不哈希表F

20、.宜找9-退出coneonffyZn>：y口.显示哈希表P.查找请选择，F请祠人姓名的拼音无此记录，U-退出coneon!<y/n>：显示“comeon!<y/n>"时，选择y继续回到初始菜单，选择n退出程序七.测试结果输入“chenliang”输出姓名：chenliang关键字：937查找长度为：1”输入“chenyuanhao”输出姓名：chenyuanhao关键字：1171查找长度为：1”输入“chengwenliang”输出姓名：chengwenliang关键字：1370查找长度为：1输入“dinglei输出姓名：dinglei关键字：732查找

21、长度为：1”输入“fenghanzao”输出姓名：fenghanzao关键字：1057查找长度为：1”输入“fuzongkai”输出姓名：fuzongkai关键字：974查找长度为：1”输入“hujingbin”输出姓名：hujingbin关键字：958查找长度为：1”输入“huangjianwu”输出姓名：huangjianwu关键字：1185查找长度为：1”输入"lailaifa”输出姓名：lailaifa关键字：819查找长度为：1”输入“lijiahao”输出姓名：lijiahao关键字：833查找长度为：2”输入“liangxiaocong”输出姓名：liangxiaocong关键字：1379查找长度为：1"输入“linchunhua”输出姓名：linchunhua关键字：1071查找长度为：1”输入“liujianhui”输出姓名：liujianhui关键字：1074查找长度为：1”输入“luzhijian”输出姓名：luzhijian关键字：974查找长度为：2”输入“luon