数据结构课程设计之姓名哈希表的建立及查找.doc
《数据结构课程设计之姓名哈希表的建立及查找.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计之姓名哈希表的建立及查找.doc（14页珍藏版）》请在冰点文库上搜索。
武汉理工大学《数据结构》课程设计说明书
课程设计任务书
学生姓名：
刘颖专业班级：
计科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日
系主任（或责任教师）签名：
年月日
目录
1问题分析和任务定义...............................................3
1.1问题描述.......................................................3
1.2问题分析.......................................................3
2开发平台.........................................................3
3数据类型和系统设计...............................................3
3.1存储结构设计...................................................3
3.2主要算法设计...................................................4
3.2.1姓名结构体数组初始化.........................................4
3.2.2获取关键码...................................................5
3.2.3哈希表结构体数组初始化.......................................5
3.2.4构造哈希表...................................................5
3.2.5打印哈希表...................................................6
3.2.6在哈希表中查找姓名...........................................6
4调试结果与运行情况分析...........................................8
4.1程序运行结果...................................................8
4.2运行情况分析...................................................9
4.3算法的时间复杂度...............................................9
5自我评价与总结...................................................9
6参考文献........................................................10
7附：
源代码......................................................11
哈希表的设计与实现
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;
typedefstruct
{
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";
a[29].p="liuzhenzhen";
3.2.2获取关键码
字符串的各个字符所对应的ASCII码相加，所得的整数做为关键字。
inti,s,r;
for（i=0;i<30;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;i<40;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;i<30;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;//伪随机探测再散列法处理冲突
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<<"关键码初散列再散列哈希地址查找次数姓名"<for（i=0;i<40;i++）
{
cout<"\t"<}
for（i=0;i<40;i++）average+=h[i].l;
average/=30;
cout<<"平均查找长度：
ASL="<3.2.6在哈希表中查找姓名
intm;
do//m=1,继续查找；m=0,退出查找
{
char*f=newchar[20];
intkey=0,n=0,g,l=1,adr;
cout<<"请输入姓名的拼音:
"<cin>>f;
for（g=0;*（f+g）!
='\0';g++）//求出姓名的拼音所对应的整数（关键字）
{
n+=*（f+g）;
key=n;
}
adr=key%37;//哈希函数求初散列值
if（h[adr].key==key）//分3种情况进行判断
{
cout<<"关键字:
"< cout<<"初散列值为:
"< cout<<"再散列值为:
"< cout<<"表中位置为:
"<cout<<"查找长度为:
"< }
elseif（h[adr].key==0）cout<<"无此记录!
"< 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<<"无此记录!
"< }
if（h[adr].key==key）
{
sign=1;
cout<<"关键字:
"<cout<<"初散列值为:
"<cout<<"表中位置为:
"<cout<<"查找长度为:
"< }
}while（sign==0）;
}
cout<<"继续查询请输入,退出请输入：
"< cin>>m;
}while（m==1）;
4调试结果与运行情况分析
4.1程序运行结果
4.2运行情况分析
哈希表的输出与预期相同且正确，并查找了"liuying"、"jiangwei"、"huangxiao"三个姓名，分别代表查找一次、多次后成功及查找不成功的情况，且查找结果正确。
4.3算法的时间复杂度
O（n）
5自我评价与总结
经过这次课程设计的学习，让我明白了编写程序的思路是很重要的，不仅检验了我所学习的知识，也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情的方法和技巧。
在编写一个程序之前，如果脑袋里面没有思路，根本就不可能编出好的程序。
就算能编出程序来，相信编出的程序的逻辑性也不会很强，因为是想到什么就编什么，不系统。
因此在我们编程序之前一定要做好充分的准备，首先要理清自己的思路，然后再将思路分划成几个模块，一块一块的编写，最后再将所有的模块联系起来，组成一个完整的程序。
在上机实验之前，最好将程序编写好在草稿纸上，这样在编译的时候也比较有效率。
课程设计是我们专业课程知识综合应用的实践训练，着是我们迈向社会，从事职业工作前一个必不少的过程．“千里之行始于足下”，通过这次课程设计，我深深体会到这句千古名言的真正含义。
今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础。
数据结构，是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
这一门课的内容不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。
通过这次哈希表的设计，我在多方面都有所提高。
在这次课程设计的过程中，我也遇到了很多难题。
在种种的困难中，我明白了耐心在编写程序时的重要性。
如果你没有耐心就肯定编不出好的程序，特别是在调试的过程中。
我们初次写的程序在电脑上调试的时候也许会出项几百个错误，这时候我们应该耐心的检查出错的地方和原因，并予以改正，而不是抱怨自己写的程序太烂错误太多，就此放弃。
相信再强的人也不可能一次就能编译成功，总会有一些问题出现。
其实只要有耐心，就会发现，在修改了一个错误之后，其它有的错误也会跟着消失，所以在编译的时候一定要有耐心。
通过这次课程设计，我认识到了自己动手实践的弱势，特别是在编程方面，知道了计算机的实践操作是很重要的，只有通过上机编程才能充分的了解自己的不足。
而自己完成了这样的课程设计，也是对自己实力的检测，使我对以后的学习也充满了信心和期待。
这次的课程设计，更是让我深刻认识到自己在学习中的不足，同时也找到了克服这些不足的方法，这也是一笔很大的资源。
数据结构是一门比较难的课程，需要花很多的时间去练习和实践。
要想把这门课程学好学精不是一件容易的事，但是相信事在人为，只要肯下功夫就一定能学好。
总的来说，这次程序设计让我获益匪浅，相信在以后的学习生活中我也能从中获得启发。
在以后的时间中，我们应该利用更多的时间去上机实验，加强自学的能力，多编写程序，相信不久后我们的编程能力都会有很大的提高能设计出更多的更有创新的作品。
我认为我的设计优点在于只是用了简单的面向过程编程，而没有用面向对象的类的设计。
类在用于比较大的程序设计时会显露较大的优势，而在此反而会增加不必要的麻烦。
我的设计缺点在于不是面向大众的，即不能由用户在运行时输入姓名，只能通过在代码中的修改达到效果。
这个课题的另一种方法是使用模板类，这样做可以使程序的结构看起来更整洁简明，各种方法的相关函数一览无余；在主函数中直接调用定义在模版类中的函数，使读者可以很快明白主函数做了哪些工作，程序运行后会有哪些输入输出。
6.参考文献
1.《数据结构（用面向对象方法与C++语言描述）》（第2版）清华大学出版社
2.《C++Primer（中文版）》（第4版）人民邮电出版社
7.附：
源代码
#include
usingnamespacestd;
intmain（）
{
typedefstruct
{
intkey;
char*p;
}NAME;
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";
a[29].p="liuzhenzhen";
inti,s,r;
for（i=0;i<30;i++）
{
s=0;
for（r=0;*（a[i].p+r）!
='\0';r++）
{
s+=*（a[i].p+r）;
a[i].key=s;
}
}
typedefstruct
{
intkey;//关键字
inthash;//初始地址
intreha;//再散列值
char*p;//名字
intl;//查找长度
}HASH;
HASHh[40];
for（i=0;i<40;i++）
{
h[i].key=0;
h[i].hash=0;
h[i].reha=0;
h[i].p="";
h[i].l=0;
}
for（i=0;i<30;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;//伪随机探测再散列法处理冲突
hi=finh;
sum=sum+1;//查找次数加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;
}
}
floataverage=0;
cout<<"关键码初散列再散列哈希地址查找次数姓名"<for（i=0;i<40;i++）
{
cout<
升级会员 