《数据结构实验答案 数据结构课程设计--哈希表设计.docx》由会员分享，可在线阅读，更多相关《数据结构实验答案 数据结构课程设计--哈希表设计.docx（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、课程设计课程名称数据结构题目名称 哈希表设计学生学院计算机学院专业班级级网络工程 班学 号 3207007022学生姓名 刘晓慧指导教师杨劲涛2022年6月28日七.测试结果输入 “chenliang”输出“姓名：chenliang 关键字：937 查找长度为：1”输入 “chenyuanhao”输出“姓名：chenyuanhao关键字：1171 查找长度为：1”输入 “chengwenliang”输出“姓名：chengwenliang关键字：1370查找长度为：甘输入 “dinglei输出“姓名：dinglei关键字：732查找长度为：1”输入 “fenghanzao”输出“姓名：fengh
2、anzao 关键字：1057 查找长度为：1”输入 “fuzongkai”输出“姓名：fuzongkai关键字：974 查找长度为：1”输入 “hujingbin”输出“姓名：hujingbin关键字：958查找长度为：1”输入 “huangjianwiT输出“姓名：huangjianwu 关键字：1185 查找长度为：1”输入 “lailaifa”输出“姓名：lailaifa 关键字：819 查找长度为：1”输入 “lijiahao”输出“姓名：lijiahao 关键字：833查找长度为：2”输入 “liangxiaocong”输出“姓名：liangxiaocong 关键字：1379 查找长
3、度为：1”输入 Tinchunhua”输出“姓名：linchunhua 关键字：1071 查找长度为：1”输入 “liujianhui”输出“姓名：liujianhui关键字：1074查找长度为：1”输入 “luzhijian”输出“姓名：luzhijian 关键字：974 查找长度为：2”输入 “luonan”输出“姓名：luonan 关键字：653 查找长度为：1”输入 “quegaoxiang”输出“姓名：quegaoxiang 关键字：1177 查找长度为：1”输入 “sugan”输出“姓名：sugan关键字：542 查找长度为：1”输入 “suzhiqiang”输出“姓名：suzhi
4、qiang关键字：1091查找长度为：2”输入 “taojiayang”输出“姓名：taojiayang关键字：1063 查找长度为：1”输入 “wiijiawen”输出“姓名：wujiawen 关键字：874 查找长度为：V输入 “xiaozhuoming”输出“姓名：xiaozhuoming 关键字：1314 查找长度为：1”输入 “xujinfeng”输出“姓名：xujinfeng 关键字：974查找长度为：7”输入 “yanghaichun”输出“姓名：yanghaichun关键字：1167查找长度为：2”输入 “yeweixiong”输出“姓名：yeweixiong 关键字：1096
5、 查找长度为：1”输入 “zengwei”输出“姓名：zengwei关键字：761 查找长度为：1”输入 “zhengyongbin”输出“姓名：zhengyongbin 关键字：1298 查找长度为：7”输入 “zhongminghua”输出“姓名：zhongminghua 关键字：1295 查找长度为：1” 输入 “chenliyan”输出“姓名：chenliyan 关键字：955 查找长度为：2”输入 “liuxiaohui”输出“姓名：liuxiaohui关键字：1089 查找长度为：1”输入 “panjinmei”输出“姓名：panjinmei关键字：955 查找长度为：4”A.附录
6、源文件Hash.cpp 运行文件Hash.exe一 .问题描述1问题描述针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表，使得平 均查找长度不超过R,完成相应的建表和查表程序。2.基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个， 取平均查找长度的上限为2o哈希函数用除留余数法构造，用伪随机探测再散列 发处理冲突。二.需求分析(1)针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R, 完成相应的建立和查表程序。(2)人名为汉语拼音形式，最长不超过19个字符(如：庄双双 zhuangshuangshuang)。(3)假设待填入哈希表的人名有30个，平均
7、查找长度的上限为2。哈希 表用除留余数法构造，用伪随机探测在散列法处理冲突。(4)在输入人名过程中能自动识别非法输入，并给与非法输入的反馈信息 要求重新输入。(5)查找成功时，显示姓名及关键字，并计算和输出查找成功的平均查找长度三.程序设计1 .存储结构设计typedef struct char *py; 名字的拼音nt k;拼音所对应的整数NAME;typedef struct哈希表 char *py; 名字的拼音int k;/拼音所对应的整数int si;查找长度HASH;2 .主要算法设计(1) 姓名(结构体数组)初始化名字以拼音的形式够成字符串，将字符串的各个字符所对应的ASCII码相
8、加， 所得的整数做为哈希表的关键字。void InitNameListO char *f;int r,sO,i;陈亮陈元浩程文亮丁磊冯汉枣付宗楷胡劲斌黄建武赖来发李嘉豪梁晓聪林春华刘建辉卢志健罗楠阙高翔苏浅苏志强陶嘉阳吴嘉文肖卓明许金峰杨海春叶维雄曾经玮郑雍斌钟明华陈利燕刘晓慧潘金梅for(i=0;iNAME_NO;i+) s0=0;f=NameListi.py;*/将字符串的各个字符所对应的ASCII码相加，所 得的整数做为哈希表的关键字*/sO=*(f+r)+sO;NameListi.k=sO; )(2)建立哈希表(1)用除留余数法构建哈希函数(2)用伪随机探测再散列法处理冲突void C
9、reateHashList() int i;forgO; ivHASH_LENGTH;i+) (HashListi.k=O;HashListi.si=O;)for(占0;ivHASH_LENGTH;i+) int sum=0;int adr=(NameListi.k)%M; 哈希函数 int d=adr;if(HashListadr.si=O) 如果不冲突 HashListadr.k=NameListi.k;HashListadr.py=NameListi.py;HashListadr.si=1;)else 冲突 do d=(d+NameListi.k%10+1 )%M; 伪随机探测再散列法处
10、理冲突 sum=sum+1;查找次数加1while (HashListd.k!=O);HashListd.k=NameListi.k;HashListd.py=NameListi.py;HashListd.si=sum+1; ) (3)查找哈希表在哈希表中进行查找，输出查找的结果和关键字，并计算和输出查找成功的平均查找长度void FindList()查找 char name20=0;int sO=O,r,sum=1,adr,d;请输入姓名的拼音for(r=0;r20;r+)求出姓名的拼音所对应的整数(关键字)sO+=namer;adr=sO%M;/使用哈希函数d=adr;if(HashLis
11、tadr.k=sO)分 3 种情况进行判断姓名:s关键字:d查找长度为else if (HashListadr.k=O) 无此记录else int g=0; do d=(d+s0%10+1 )%M;伪随机探测再散列法处理冲突sum=sum+1;if(HashListd.k=O)无此记录g=i; if(HashListd.k=sO) 姓名:s关键字:d查找长度为g=i; )while(g=0);)(4)显示哈希表显示哈希表的的格式：地址关键字 搜索长度H(key) 姓名void Display() int i;float average=0;地址关键字 搜索长度H(key) 姓名显示的格式for
12、(i=0; i50; i+)for(i=0;iHASH_LENGTH;i+)average+=HashListi.si;average/=NAME_NO; 平均查找长度：)主函数设计void main() charch1;InitNameListO;CreateHashList ();do显示哈希表F.查找Q.退出cin&ch1; switch (ch 1) (case D:Display(); coutendl;break;case F:FindList();coutvvendl;break; case Q*:exit(0);)cin&ch1;while(ch1 !=n);四.编程环境：VC
13、+6.0请选择:五.调试报告及体味1.测试用例程序运行结果程序运行后显示如下:哈希哈希表设计DebugVksh. exeII 显小哈希表F.直找退出 请选择:(1)选择D查找，显示哈希表和平均查找长度，其中平均查找长度小于2,符合题目要求：F.查找Q.退出请选择:D地址关键字搜索长度01167210221177130040050060071370181089197611101185111001210912130014001510961161379117974718958119002081912195522200231057124002554212612951277321288741291063
14、130003100320033955434974135003612987371071138833239974240107414100426531431171144937145131414600470048004900平均查找长度：ASL=1.733333cone on ? :102quegaoxiang7chengwenliang8liuxiaohuiH9zengwei10huangjianwu10suzhiqiang115yevieixiong16liangxiaocong34xujinfengH18hujingbinH20lailaifa15chenlian23fenghanzao25su
15、gan26zhongninghua27dingleiH28wujiawen29tao jiai/ang115panjinnei34fuzongkaiH0 *I29zheng/ongbin37linchunhuaH34lijiahaoH34luzhijianH40liujianhuiH42luonan43chenuanhao44chenliang45xiaozhuoming(2)选择F查找， 输入要查找的人的姓名，若存在则显示名字和对应的关键 字以及查找长度；若不存在则显示无此记录：D.显不啥希表P-意找Q.退出请遒探i F请输入姓名的拼音:liuxiaohui姓名：liuxiaohui 关键字
16、：1089查找长度为：1-显小啥希表.查茗.退出itcone on ? ：y请选择.Fi青输入姓名的拼音:xadssd 无曲记录？cone on ? ：(3)选择Q退出，如要继续可按任意键:come on ? ：y0.显不哈希表F.直找Q.退出请选* Qress any key to continue2 .时间复杂度O(n)3 .经验和体味经过这次课程设计的学习，让我明白了编写程序的思路是很重要的。在你编 写一个程序之前，如果你的脑袋里面没有思路，根本就不可能编出好的程序。就 算能编出程序来，相信编出的程序的逻辑性也不会很强，因为你是想到什么就编 什么，不系统。因此在我们编程序之前一定要做好充
17、分的准备，首先要理清自己 的思路，然后再将思路分划成几个模块，一块一块的编写，最后再将所有的模块 联系起来，组成一个完整的程序。在上机实验之前，最好将程序编写好在草稿纸 上，这样在编译的时候也比较有效率。其实在这次课程设计的过程中，我也遇到了不少难题。在种种的艰难中，我 明白了耐心在编写程序时的重要性。如果你没有耐心就肯定编不出好的程序，特 别是在调试的过程中。我们初次写的程序在电脑上调试的时候也许会出项几百个 错误，这时候我们应该耐心的检查出错的地方和原因，并予以改正，而不是抱怨 自己写的程序太烂错误太多，就此抛却。相信再强的人也不可能一次就能编译成 功，总会有一些问题浮现。其实只要有耐心，
18、你就会发现，在你修改了一个错误 之后，其它有的错误也会跟着消失，所以在编译的时候一定要有耐心。这段时间的课程设计，我也认识到数据结构是一门比较难的课程，需要花很 多的时间去练习和实践。要想把这门课程学好学精不是一件容易的事，但是相信 事在人为，只要肯下功夫就一定能学好。总的来说，这次程序设计让我获益匪浅， 相信在以后的学习生活中我也能从中获得启示。六.用户使用说明详细视图请参考调试才艮告程序运行初显示如下：从中选择需要做的操作，输入对应的操作D、F、Q,并按回车，输入错误时, 会显示“无此记录！ ” ；正确时，显示姓名，关键字以及查找长度。D.显小哈希表F.宜找Q.退出请选择！ F请输入姓名的拼音:liuxiaohui姓名：liuxiaohui关键字：1089查找长度为：1cone on ? ：yD.显不喑希表F-意找Q.退出请选择：F请辆入姓名的拼音:xadssd无曲记录？come on ? ：显示“comeon! vy/n”时，选择y继续回到初始菜单，选择n退出程序。