哈希表的设计与实现课程设计报告

一:需求分析.................................................................................................................................2三:详细设计（含代码分析）.......................................................................................................41.程序描述:.....................................................................................................................42具体步骤................................................................................................................................4四调试分析和测试结果.................................................................................................................7五，总结...........................................................................................................................................9六.参考文献;..................................................................................................................................10七.致谢...........................................................................................................................................10八.附录............................................................................................................................................11一:需求分析问题描述：设计哈希表实现电话号码查询系统。基本要求1、设每个记录有下列数据项：电话号码、用户名、地址2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；3、采用再哈希法解决冲突；4、查找并显示给定电话号码的记录；5、查找并显示给定用户名的记录。6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变化。二:概要设计进入主函数,用户输入1或者2,进入分支选择结构:选1:以链式方法建立哈希表,选2:以再哈希的方法建立哈希表,然后用户输入用户信息,分别以上述确定的方法分别以用户名为检索以及以以电话号码为检索将用户信息添加到哈希表,.当添加一定量的用户信息后,用户接着输入用户名或者电话号码分别以用户名或者电话号码的方式从以用户名或电话号码为检索的哈希表查找用户信息.程序用链表的方式存储信息以及构造哈希表。具体流程图如下所示:主函数输入1输入2链式法构造哈希表表再哈希法构造哈希表输入用户信息输入用户信息分别以电话和姓名为检索将信息存储到哈希表分别以电话和姓名为检索将信息存储到哈希表输入1输入2输入1输入2以电话为索引查找用户信息输入电话输入姓名输入电话输入姓名以姓名为索引查找用户信息以电话为索引查找用户信息以姓名为索引查找用户信息程序结束三:详细设计（含代码分析）1.程序描述:本程序以要求使用哈希表为工具快速快速查询学生信息，学生信息包括电话号码、用户名、地址；用结构体存储structnode{stringphone;//电话号码stringname;//姓名stringaddress;//地址node*next;//链接下一个地址的指针};2具体步骤1.要求主要用在哈希法解决冲突，并且至少尝试用两种方法解决冲突，定义两个指针数组存储信息node*infor_phone[MAX];node*infor_name[MAX];前者以电话号码为关键字检索哈希表中的信息，后者以姓名为关键字检索哈希表中的信息用链式法和再哈希法解决冲突：inthash(stringkey)//以姓名或者电话号码的前四位运算结果作为哈{//希码intresult=1,cur=0,i;if(key.size()=4)i=key.size()-1;elsei=4;for(;i=0;i--){cur=key[i]-'0';result=result*9+cur;}result%=(MOD);returnresult;}2.得到输入信息的哈希码以后，将相应的信息插入对应的地址，若产生冲突，则循环到这个地址的最后一个节点，然后再将节点插入到这个位置，这样就避免了冲突,在查找的时候便可直接找到这个地址然后快速的查找到信息:voidadd_infor_phone(stringphone,stringname,stringaddress){intvalue=hash(phone);node*infor=build_infor(phone,name,address);if(infor_phone[value]==NULL)infor_phone[value]=infor;else{node*cur=infor_phone[value];while(cur-next)cur=cur-next;cur-next=infor;}}3.再哈希法也是解决冲突的常见方法，当同义词产生地址冲突时计算另一个哈希函数地址，知道冲突不再发生，这种方法不易产生聚义，但是增加了计算时间：inthash_agin(intnumble,intkey)//将关键字的前四位数经过计算的结果{//模上一个定义的数然后返回的数字为returnnumble%key;//哈希码}intcreate(stringkey){intresult=1,cur=0,i;if(key.size()=4)i=key.size()-1;elsei=4;for(;i=0;i--){cur=key[i]-'0';result=result*9+cur;}returnresult;}4.同样用链表为储存信息的数据结构，当产生冲突时，将模数减去一然后再寻找地址直到不再产生冲突：voidadd_infors(stringphone,stringname,stringaddress){intnumble_phone=create(phone),key=MOD,pos_phone,pos_name;while(infor_phone[pos_phone=hash_agin(numble_phone,key)]!=NULL)key--;key=MOD;intnumble_name=create(name);while(infor_name[pos_name=hash_agin(numble_name,key)]!=NULL)key--;node*inforphone=newnode;node*inforname=newnode;inforphone-name=inforname-name=name;inforphone-phone=inforname-phone=phone;inforphone-address=inforname-address=address;inforphone-next=inforname-next=NULL;infor_phone[pos_phone]=inforphone;infor_name[pos_name]=inforname;}5.帮主函数boolusersayyes()，返回一个bool值，要求用户输入一个正确的选项，减少程序因错误输入而出现的问题:boolusersayyes(){stringsig;boolcontinu=true;cout请输入(N/n)或(Y/y),(N/n)代表退出,(Y/y)代表继续:;while(cinsig&&(sig!=Y&&sig!=y)&&(sig!=N&&sig!=n))cout输入错误,请重新输入!endl;returnsig==Y||sig==y;}四调试分析和测试结果1.用链式法将用户信息添加到哈希表：2.以姓名为关键字检索用户信息:3.当哈希表中不存在此项记录时:4．再哈希法将用户信息添加到哈希表：5．以姓名为检索在哈希表中查找用户信息:6.以电话为检索在哈希表中查询信息:使用哈希表能在较短的时间内查找出数据，程序的结果基本和理论相符合。五，总结通过做这个课程设计，使我们对如何去解决分析一个没有接触过的问题有深刻的认识，我们开始对题目有很多误解，根本没有思路，经过老师的几次讲解和我们自己很多的讨论，最终把问题进行转换，老师的要求是为了一个映射关系，我们找到了一个算法，算法和公式是可以相互转换的，在这个过程我们发现自己的程序有很多问题，经过我们不断对算法进行修改使得我们的程序运行的更快。哈希表的设计与实现这一算法始终围绕怎样解决冲突和怎样快速查找数据为目的，要求用在哈希法和链式法设计和实现哈希表，经过查阅资料请教同学问题渐渐的变得清晰，在分析问题，思考问题和解决问题的过程中，很大程度上培养了我们的动手和动脑的能力，开始选择一个合适的数据结构，然后依据算法编码，调试，最后得出正确结论，整个过程虽然遇到了很多问题，特别是指针的冲突，这样在不知不觉中培养了我的耐性，“数据结构与算法”课程是计算机专业的一门十分重要的核心基础课程。这次的课程设计，，拓广了我解决实际问题的程序设计的思路，也培养了对于问题进行深入探究的习惯。我更加深刻的体会到各种路由算法的特点，以及性能的优劣。为我今后专业课程的学习奠定了坚实的理论基础！六.参考文献;1.数据结构严蔚敏，吴伟明（c语言版）清华大学出版社2.算法导论Thoms.H.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein著潘金贵，顾铁成，李成法译第二版机械工业出版社3.数据结构基础(C语言版)(第2版)EllisHorowitz，SartajSahni，SusanAnderson-Freed著朱仲涛译清华大学出版社4.数据结构与算法分析：C语言描述(英文版.第2版)MarkAllenWeiss著机械工业出版社5.算法之道邹恒明(第2版)机械工业出版社七.致谢在这次课程设计的撰写过程中，我得到了许多人的帮助。首先我要感谢我的老师在课程设计上给予我的指导、提供给我的支持和帮助，这是我能顺利完成这次报告的主要原因，更重要的是老师帮我解决了许多技术上的难题，让我能把系统做得更加完善。在此期间，我不仅学到了许多新的知识，而且也开阔了视野，提高了自己的设计能力。其次，我要感谢帮助过我的同学，他们也为我解决了不少我不太明白的设计商的难题。同时也感谢学院为我提供良好的做毕业设计的环境。最后再一次感谢所有在设计中曾经帮助过我的良师益友和同学八.附录#includeiostream#includestringusingnamespacestd;#defineMAX10000#defineMOD9873s