数据结构课程设计之姓名哈希表的建立及查找

武汉理工大学《数据结构》课程设计说明书1课程设计任务书学生姓名：刘颖专业班级：计科1003班指导教师：谭新明工作单位：计算机科学系题目:哈希表的设计与实现初始条件：针对某个集体（比如你所在的班级）中的“人名”设计并实现一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。（1）假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。（2）哈希函数用除留余数法构造（3）用伪随机探测再散列法处理冲突。（4）测试用例见严蔚敏《数据结构习题集(C语言版)》p166。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：1.问题描述简述题目要解决的问题是什么。2.设计存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计；3.调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4.经验和体会（包括对算法改进的设想）5.附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。说明：1.设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。2.凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。时间安排：1、6月15日～6月21日完成。2、6月22日上午和下午在实验中心检查程序、交课程设计报告、源程序（U盘）。指导教师签名：2012年6月14日系主任（或责任教师）签名：年月日武汉理工大学《数据结构》课程设计说明书2目录1问题分析和任务定义...............................................31.1问题描述.......................................................31.2问题分析.......................................................32开发平台.........................................................33数据类型和系统设计...............................................33.1存储结构设计...................................................33.2主要算法设计...................................................43.2.1姓名结构体数组初始化.........................................43.2.2获取关键码...................................................53.2.3哈希表结构体数组初始化.......................................53.2.4构造哈希表...................................................53.2.5打印哈希表...................................................63.2.6在哈希表中查找姓名...........................................64调试结果与运行情况分析...........................................84.1程序运行结果...................................................84.2运行情况分析...................................................94.3算法的时间复杂度...............................................95自我评价与总结...................................................96参考文献........................................................107附：源代码......................................................11武汉理工大学《数据结构》课程设计说明书3哈希表的设计与实现1问题分析和任务定义1.1问题描述设计哈希表，要求用除留余数法构造哈希函数，用伪随机探测再散列法处理冲突，使平均查找长度的上限为2。待填入哈希表的人名共有30个，且为中国人姓名的汉语拼音形式。1.2问题分析（1）待填入哈希表的人名有30个，平均查找长度的上限为2。用除留余数法构造哈希表，用伪随机探测再散列法处理冲突，完成相应的建立和查表程序。（2）人名为汉语拼音形式，最长不超过20个字符。（3）查找成功时，显示姓名、关键字、初散列值、再散列值、哈希表中的位置及查找长度；查找失败时，显示无此记录。（4）可多次查找，继续查找输入1，退退出输入0。2开发平台系统：Windows7开发工具：Visualstudio2008语言：C++3数据类型和系统设计3.1存储结构设计typedefstruct{intkey;char*p;}NAME;武汉理工大学《数据结构》课程设计说明书4typedefstruct{intkey;//关键字inthash;//初始地址intreha;//再散列值char*p;//名字intl;//查找长度}HASH;3.2主要算法设计3.2.1NAME（结构体数组）初始化NAMEa[30];a[0].p=wangjunzhe;a[1].p=mahaiping;a[2].p=luozijian;a[3].p=luoxiangzhou;a[4].p=zhangkai;a[5].p=fengyuyang;a[6].p=wuzhenzhen;a[7].p=haokaiqi;a[8].p=caopu;a[9].p=liuying;a[10].p=cuijuan;a[11].p=hanqianqiqn;a[12].p=lixiaoyu;a[13].p=caoyingnan;a[14].p=jinbaoyu;a[15].p=zhaduo;a[16].p=wenbo;a[17].p=cuichangwei;a[18].p=zhangqiu;a[19].p=luopeng;a[20].p=hudie;a[21].p=xieshanshan;a[22].p=liming;a[23].p=zhangshuai;a[24].p=qiuyajun;a[25].p=yanruibin;a[26].p=jiangwei;a[27].p=fangzhaohua;a[28].p=yujia;武汉理工大学《数据结构》课程设计说明书5a[29].p=liuzhenzhen;3.2.2获取关键码字符串的各个字符所对应的ASCII码相加，所得的整数做为关键字。inti,s,r;for(i=0;i30;i++){s=0;for(r=0;*(a[i].p+r)!='\0';r++){s+=*(a[i].p+r);a[i].key=s;}}3.2.3HASH(结构体数组)初始化HASHh[40];for(i=0;i40;i++){h[i].key=0;h[i].hash=0;h[i].reha=0;h[i].p=;h[i].l=0;}3.2.4构造哈希表for(i=0;i30;i++){intsum=0;inthi=(a[i].key)%37;//哈希函数inthj=(7*a[i].key)%10+1;//再散列函数if(h[hi].l==0)//如果不冲突{h[hi].key=a[i].key;h[hi].hash=(a[i].key)%37;h[hi].reha=(7*a[i].key)%10+1;h[hi].p=a[i].p;武汉理工大学《数据结构》课程设计说明书6h[hi].l=1;}else//冲突{intfinh;//最终地址do{finh=(hi+hj)%40;//伪随机探测再散列法处理冲突hi=finh;sum=sum+1;//查找次数加}while(h[hi].l!=0);h[hi].key=a[i].key;h[hi].hash=(a[i].key)%37;h[hi].reha=(7*a[i].key)%10+1;h[hi].p=a[i].p;h[hi].l=sum+1;}}3.2.5打印哈希表floataverage=0;cout关键码初散列再散列哈希地址查找次数姓名endl;//格式for(i=0;i40;i++){couth[i].key\th[i].hash\th[i].reha\ti\th[i].l\th[i].pendl;}for(i=0;i40;i++)average+=h[i].l;average/=30;cout平均查找长度：ASL=averageendl;3.2.6在哈希表中查找姓名intm;do//m=1,继续查找；m=0,退出查找{char*f=newchar[20];intkey=0,n=0,g,l=1,adr;cout请输入姓名的拼音:endl;cinf;for(g=0;*(f+g)!='\0';g++)//求出姓名的拼音所对应的整数(关键字)武汉理工大学《数据结构》课程设计说明书7{n+=*(f+g);key=n;}adr=key%37;//哈希函数求初散列值if(h[adr].key==key)//分3种情况进行判断{cout关键字:keyendl;cout初散列值为:h[adr].hashendl;cout再散列值为:h[adr].rehaendl;cout表中位置为:adrendl;cout查找长度为:lendl;}elseif(h[adr].key==0)cout无此记录!endl;else{intfinh;//最终地址intsign=0;do{finh=(adr+7*key%10+1)%40;//再散列法处理冲突adr=finh;l=l+1;//查找次数加if(h[adr].key==0){sign=1;cout无此记录!endl;}if(h[adr].key==key){sign=1;cout关键字:keyendl;cout初散列值为:h[adr].hashendl;cout表中位置为:adrendl;cout查找长度为:lendl;}}while(sign==0);}cout继续查询请输入,退出请输入：endl;cinm;}while(m==1);武汉理工大学《数据结构》课程设计说明书84调试结果与运行情况分析4.1程序运行结果武汉理工大学《数据结构》课程设计说明书94.2运行情况分析哈希表的输出与预期相同且正确，并查找了liuying、jiangwei、huangxiao三个姓名，分别代表查找一次、多次后成功及查找不成功的情况，且查找结果正确。4.3算法的时间复杂度O(n)5自我评价与总结经过这次课程设计的学习，让我明白了编写程序的思路是很重要的，不仅检验了我所学习的知识，也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情的方法和技巧。在编写一个程序之前，如果脑袋里面没有思路，根本就不可能编出好的程序。就算能编出程序来，相信编出的程序的逻辑性也不会很强，因为是想到什么就编什么，不系统。因此在我们编程序之前一定要做好充分的准备，首先要理清自己的思路，然后再将思路分划成几个模块，一块