哈希表的设计

计算机与信息工程系《数据结构课程设计》设计报告学号1308030113《数据结构课程设计》课程设计报告题目：哈希表的设计专业：数字媒体技术班级：13（1）班姓名：金春升指导教师：时慧琨成绩：计算机与信息工程系2014年11月28日2014-2015学年第一学期计算机与信息工程系《数据结构课程设计》设计报告1目录1问题分析和任务定义.....................................21.1问题描述..........................................21.2问题分析..........................................22开发平台...............................................23数据类型和系统设计.....................................23.1、流程图...........................................23.2存储结构设计......................................33.3主要算法设计.......................................44调试结果与运行情况分析.................................84.1程序运行结果.......................................84.2运行情况分析......................................104.3算法的时间复杂度..................................105自我评价与总结........................................11参考文献................................................12附：源代码..............................................13计算机与信息工程系《数据结构课程设计》设计报告2哈希表的设计1问题分析和任务定义1.1问题描述设计哈希表，要求用除留余数法构造哈希函数，用伪随机探测再散列法处理冲突，使平均查找长度的上限为2。待填入哈希表的人名共有30个，且为中国人姓名的汉语拼音形式。1.2问题分析（1）待填入哈希表的人名有30个，平均查找长度的上限为2。用除留余数法构造哈希表，用伪随机探测再散列法处理冲突，完成相应的建立和查表程序。（2）人名为汉语拼音形式，最长不超过20个字符。（3）查找成功时，显示姓名、关键字、初散列值、再散列值、哈希表中的位置及查找长度；查找失败时，显示无此记录。（4）可多次查找，继续查找输入1，退出输入0。2开发平台系统：Windows7开发工具：Visualstudio2008语言：C++3数据类型和系统设计3.1、流程图计算机与信息工程系《数据结构课程设计》设计报告33.2存储结构设计根据哈希函数可唯一确定一个记录的地址，在理想情况下，记录就可以按照这个存储地址进行存储。因此哈希表的存储结构可以是链表和线性表，但一般情况下选择线性表进行存储。本次课程设计用到的存储结构如下：typedefstruct{intkey;//关键字inthash;//初始地址intreha;//再散列值char*p;//名字开始选择操作删除添加记录建立哈希表查找线性姓名平方关键字显示输出结果退出计算机与信息工程系《数据结构课程设计》设计报告4intl;//查找长度}HASH;3.3主要算法设计3.3.1NAME（结构体数组）初始化结构体数组NAMEa[]的实现（以班级30人的人名作为初始值）：NAMEa[30];a[0].p=cailulu;a[1].p=chenhailin;a[2].p=daiping;a[3].p=shanyueming;a[4].p=fanfangfang;a[5].p=fengshuang;a[6].p=gushenglei;a[7].p=haozonghao;a[8].p=hongwei;a[9].p=jiangwangzhi;a[10].p=jinchunsheng;a[11].p=laiyan;a[12].p=lilianxi;a[13].p=liuhuilin;a[14].p=liujing;a[15].p=liupei;a[16].p=liuyawei;a[17].p=luoping;a[18].p=panliangliang;a[19].p=qiwentao;a[20].p=shimin;a[21].p=sunjie;a[22].p=sunyanyan;a[23].p=wanxiankai;a[24].p=wangjiawei;a[25].p=wangping;a[26].p=wangwei;a[27].p=wangyuchun;a[28].p=weiqi;a[29].p=wushuling;计算机与信息工程系《数据结构课程设计》设计报告53.3.2获取关键码在数据结构中关键码指的是数据元素中能起标识作用的数据项，例如，书目信息中的登陆号和书名等。其中能起唯一标识作用的关键码称为“主关键码”，如登陆号；反之称为“次关键码”，如书名，作者名等。通常一个数据元素只有一个主码，但可以有多个次码。在数据库中关键码(key,简称键)由一个或多个属性组成。在实际使用中，有下列几种键。（1）超键（SuperKey）（2）候选键（CandidateKey）（3）主键(PrimaryKey)字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表关键字key。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.3.3构造哈希表1、常用散列函数:（1）平方取中法（2）除余法（3）相乘取整法2、散列表的冲突现象（1）冲突两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。【例】上图中的k2≠k5，但h(k2)=h(k5)，故k2和K5所在的结点的存储地址相同。（2）安全避免冲突的条件最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：计算机与信息工程系《数据结构课程设计》设计报告6①其一是|U|≤m②其二是选择合适的散列函数。这只适用于|U|较小，且关键字均事先已知的情况，此时经过精心设计散列函数h有可能完全避免冲突。（3）冲突不可能完全避免通常情况下，h是一个压缩映像。虽然|K|≤m，但|U|m，故无论怎样设计h，也不可能完全避免冲突。因此，只能在设计h时尽可能使冲突最少。同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到表中。（4）影响冲突的因素冲突的频繁程度除了与h相关外，还与表的填满程度相关。设m和n分别表示表长和表中填人的结点数，则将α=n/m定义为散列表的装填因子(LoadFactor)。α越大，表越满，冲突的机会也越大。通常取α≤1。散列函数的构造方法用除留余数法构建哈希函数，用伪随机探测再散列法处理冲突，构建哈希函数的实现如下：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;h[hi].l=1;}else//冲突{intfinh;//最终地址do{finh=(hi+hj)%40;//伪随机探测再散列法处理冲突3.3.4打印哈希表显示哈希表的格式：\n地址\t关键字\t\t搜索长度\tH(key)\t姓名\n计算机与信息工程系《数据结构课程设计》设计报告7floataverage=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.3.5在哈希表中查找姓名首先，在所列举的我现所在班级30个同学姓名中，查找了自己的姓名“jinchunsheng”若查找成功，则输出姓名、关键字和查找长度；查找失败，则返回相应的失败信息。查找函数的实现：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++)//求出姓名的拼音所对应的整数(关键字){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;}计算机与信息工程系《数据结构课程设计》设计报告8elseif(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继续查询请输入1,退出请输入0：endl;cinm;}while(m==1);4调试结果与运行情况分析4.1程序运行结果在结束了对该课程设计的分析，查阅相关资料，编写合理程序等工作后，就是要对程序进行调试了，只有运行情况与预期相吻合，才能说明设计的完整性和正确性。1所示。计算机与信息工程系《数据结构课程设计》设计报告9测试图1首先，我在所列举的我现所在班级的30个同学姓名中，查找了自己的姓名“jinchunsheng”，操作结果如图2所示测试图2计算机与信息工程系《数据结构课程设计》设计报告10接着，我选择继续查询，所以输入1。我又输入了第二个同学的名字“laiyan”，查找成功。然后又输入一个不在存在范围的姓名，此次查找失败，两次操作结果如图3所示。测试图34.2运行情况分析根据调试结果和运行情况，可得出哈希表的输出与预期相同且正确，并查找了jinchunsheng、laiyan、zhouqianqian三个姓名，分别代表查找一次、多次后成功及查找不成功的情况，且查找结果正确。4.3算法的时间复杂度算法采用结构体和数组来存储数据，利用除留余数法得到哈希地址，利用为随机序列法来处理冲突，姓名拼音的关键字为字符串的各个字符所对应的ASCII码相加，所得的整数