哈希表的设计.docx
《哈希表的设计.docx》由会员分享，可在线阅读，更多相关《哈希表的设计.docx（11页珍藏版）》请在冰点文库上搜索。
哈希表的设计
课程设计任务书
学生姓名：
专业班级：
指导教师：
工作单位：
计算机科学与技术学院
题目:
哈希表的设计
课程设计要求:
1、熟练掌握基本的数据结构；
2、熟练掌握各种算法；
3、运用高级语言编写质量高、风格好的应用程序。
课程设计任务:
1、系统应具备的功能：
（1）设计哈希函数和哈希表
（2）设计解决冲突的方法
（3）输入一组数据建立哈希表，并实现在哈希表中进行查找
2、数据结构设计；
3、主要算法设计；
4、编程及上机实现；
5、撰写课程设计报告，包括：
（1）设计题目；
（2）摘要和关键字；
（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会等；
（4）结束语；
（5）参考文献。
时间安排：
2010年7月5日－9日（第19周）
7月5日查阅资料
7月6日系统设计，数据结构设计，算法设计
7月7日-8日编程并上机调试
7月9日撰写报告
7月10日验收程序，提交设计报告书。
指导教师签名：
2010年7月4日
系主任（或责任教师）签名：
2010年7月4日
哈希表的设计
摘要：
该程序主要实现了哈希表的设计和哈希函数的设计，并用伪随即探测法解决哈
希表设计过程中的冲突问题。
利用次程序可以完整显示设计好的哈希表并可以查找每个学
生姓名以及该学生在哈希表中的关键字，搜索长度。
关键字：
哈希表，哈希函数，冲突，伪随即探测法，关键字，哈希值
引言：
哈希表最大的优点就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。
然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。
另外，编码比较容易也是它的特点之一。
需求分析：
1、针对某个集体（比如你所在的班级）中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序；
2、人名为中国人姓名的汉语拼音，人名有30个，平均查找长度的上限为2；
3、用伪随机探测再散列法处理冲突；
4、输入为所要查询的人姓名（拼音）；输出为该关键字的查找信息；
5、测试数据：
；
输入：
liugang
输出：
姓名：
liugang关键字：
743查找长度：
1
输入：
wangyan
输出：
姓名：
liuxiangdong关键字：
1289查找长度：
1
输入：
D
输出：
显示哈希表
数据结构设计
typedefstruct//哈希表
{char*py;//名字的拼音
intk;//拼音所对应的整数
intsi;//查找长度
}HASH;
HASHHashList[HASH_LENGTH];//全局变量HASH
typedefstruct
{char*py;//名字的拼音
intk;//拼音所对应的整数
}NAME;
NAMENameList[HASH_LENGTH];//全局变量NAME
算法设计
初始化姓名
voidInitNameList（）//姓名（结构体数组）初始化
{char*f;
intr,s0,i;
NameList[0].py="zhouhailun";
NameList[1].py="dengminzhong";
NameList[2].py="tankaxiang";
NameList[3].py="liujiaqi";
NameList[4].py="liyanlin";
NameList[5].py="xiezhihua";
NameList[6].py="kongxiangzhen";
NameList[7].py="liuxiangdong";
NameList[8].py="wangxinyu";
NameList[9].py="liugang";
NameList[10].py="panhongshuang";
NameList[11].py="zengqiang";
NameList[12].py="zhuling";
NameList[13].py="xumengxing";
NameList[14].py="wuchunan";
NameList[15].py="shiwei";
NameList[16].py="cuizhanhao";
NameList[17].py="wangjingyi";
NameList[18].py="fangjingwei";
NameList[19].py="chenlong";
NameList[20].py="zhandazhi";
NameList[21].py="lizhibing";
NameList[22].py="huangchang";
NameList[23].py="weixiao";
NameList[24].py="tangwentao";
NameList[25].py="xiaqingfeng";
NameList[26].py="liuweibo";
NameList[27].py="zhousanjun";
NameList[28].py="wangyelei";
NameList[29].py="longshangyin";
for（i=0;i{s0=0;
f=NameList[i].py;
for（r=0;*（f+r）!
='\0';r++）
/*方法：
将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字*/
s0=*（f+r）+s0;
NameList[i].k=s0;
}
}
哈希表的建立
voidCreateHashList（）//建立哈希表
{inti;
for（i=0;i{HashList[i].py="";
HashList[i].k=0;
HashList[i].si=0;
}
for（i=0;i{intsum=0;
intadr=（NameList[i].k）%M;//哈希函数
intd=adr;
if（HashList[adr].si==0）//如果不冲突
{HashList[adr].k=NameList[i].k;
HashList[adr].py=NameList[i].py;
HashList[adr].si=1;
}
else//冲突
{do
{d=（d+NameList[i].k%10+1）%M;//伪随机探测再散列法处理冲突
sum=sum+1;//查找次数加1
}while（HashList[d].k!
=0）;
HashList[d].k=NameList[i].k;
HashList[d].py=NameList[i].py;
HashList[d].si=sum+1;
}
}
}
在哈希表中进行查找
voidFindList（）//查找
{charname[20]={0};
ints0=0,r,sum=1,adr,d;
printf（"请输入姓名的拼音:
"）;
scanf（"%s",name）;
for（r=0;r<20;r++）//求出姓名的拼音所对应的整数（关键字）
s0+=name[r];
adr=s0%M;//使用哈希函数
d=adr;
if（HashList[adr].k==s0）//分3种情况进行判断
printf（"\n姓名:
%s关键字:
%d查找长度为:
1",HashList[d].py,s0）;
elseif（HashList[adr].k==0）
printf（"无此记录!
"）;
else
{intg=0;
do
{d=（d+s0%10+1）%M;//伪随机探测再散列法处理冲突
sum=sum+1;
if（HashList[d].k==0）
{printf（"无此记录!
"）;
g=1;
}
if（HashList[d].k==s0）
{printf（"\n姓名:
%s关键字:
%d查找长度为:
%d",HashList[d].py,s0,sum）;
g=1;
}
}while（g==0）;
}
}
显示完整的设计好的哈希表
voidDisplay（）//显示哈希表
{inti;
floataverage=0;
printf（"\n地址\t关键字\t\t搜索长度\tH（key）\t姓名\n"）;//显示的格式
for（i=0;i<50;i++）
{printf（"%d",i）;
printf（"\t%d",HashList[i].k）;
printf（"\t\t%d",HashList[i].si）;
printf（"\t\t%d",HashList[i].k%M）;
printf（"\t%s",HashList[i].py）;
printf（"\n"）;
}
for（i=0;iaverage+=HashList[i].si;
average/=NAME_NO;
printf（"\n平均查找长度：
ASL（%d）=%f\n",NAME_NO,average）;
}
程序运行结果
主界面
显示完整哈希表
进行查找
输入学生姓名的拼音可以查找出该学生在哈希表中的关键字
有关技术的讨论
该程序主要在设计哈希表时用学生姓名的拼音字母的ASCII码和做为哈希表的关键字，用除留余数法来设计哈希函数，对哈希表设计过程中发生的冲突采用伪随即探测的方法来解决哈希表设计中发生的冲突。
整体程序思路比较简单
设计体会
通过做此程序对哈希表的建立方法，哈希表中冲突解决的方法以及原理有了很深的理解，通过此次实验真正体会到了哈希表可以有效减少查找长度，大大提高程序运行的效率。
做此程序也是本阶段学完理论课程之后对自己该方面的能力的一次很好的检验，从开始的算法思路到运行调试后的的可用程序，都是一个很好的学习和锻炼的过程。
使我们巩固了原有的理论知识，培养了我们灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力。
使我们体会到自身知识和能力能在实际中的应用和发挥。
不但可以激发创新意识，还可以开发创造能力、培养沟通能力。
这次课程设计确实使我受益非浅。
通过实习我丰富了计算机操作经验，更加深了对C语言的了解，熟悉了其环境，更增强了对visualstudio的使用技巧。
结束语：
该程序使用visualstudio2008实现的，该程序包含一下功能：
（1）设计哈希函数和哈希表；
（2）设计解决冲突的方法；（3）输入学生姓名数据建立哈希表，并实现在哈希表中进行查找。
该程序也有很多不足例如：
界面不够美观，程序所需数据不能由用户自行决定，程序代码中注释明了等等。
这说明该程序还有待进一步修正。
参考文献：
[1]严蔚敏吴伟民编著《数据结构》清华大学出版社2001年1月
[2]谭浩强主编《C程序设计》清华大学出版社2005年7月
升级会员 