资源描述：
《哈希表的设计与实现 课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一:需求分析2三:详细设计（含代码分析）41.程序描述:42具体步骤4四调试分析和测试结果7五，总结9六.参考文献;10七.致谢10八.附录10一:需求分析问题描述：设计哈希表实现电话号码查询系统。基本要求1、设每个记录有下列数据项：电话号码、用户名、地址2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；3、采用再哈希法解决冲突；4、查找并显示给定电话号码的记录；5、查找并显示给定用户名的记录。6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变化。二:概要设计进入主函数,用户输入1或者2,进入分支选择结构:选1:以链式方
2、法建立哈希表,选2:以再哈希的方法建立哈希表,然后用户输入用户信息,分别以上述确定的方法分别以用户名为检索以及以以电话号码为检索将用户信息添加到哈希表,.当添加一定量的用户信息后,用户接着输入用户名或者电话号码分别以用户名或者电话号码的方式从以用户名或电话号码为检索的哈希表查找用户信息.程序用链表的方式存储信息以及构造哈希表。具体流程图如下所示:主函数输入1输入2链式法构造哈希表表再哈希法构造哈希表输入用户信息输入用户信息分别以电话和姓名为检索将信息存储到哈希表分别以电话和姓名为检索将信息存储到哈希表输入1输入2输入1输入2以电话为索引查找用户信息输入电话输入姓名输入电话输入
3、姓名以姓名为索引查找用户信息以电话为索引查找用户信息以姓名为索引查找用户信息程序结束三:详细设计（含代码分析）1.程序描述:本程序以要求使用哈希表为工具快速快速查询学生信息，学生信息包括电话号码、用户名、地址；用结构体存储structnode{stringphone;//电话号码stringname;//姓名stringaddress;//地址node*next;//链接下一个地址的指针};2具体步骤1.要求主要用在哈希法解决冲突，并且至少尝试用两种方法解决冲突，定义两个指针数组存储信息node*infor_phone[MAX];node*infor_name[MAX];前者
4、以电话号码为关键字检索哈希表中的信息，后者以姓名为关键字检索哈希表中的信息用链式法和再哈希法解决冲突：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.得到输入信息的哈希码以后，将相应的信息插入对应的地址，若产生冲突，则循环到这个地址的最后一个节点，然后再将节
5、点插入到这个位置，这样就避免了冲突,在查找的时候便可直接找到这个地址然后快速的查找到信息: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->nex
6、t=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=re
7、sult*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--;ke
