数据结构优秀课程设计之姓名哈希表的建立及查找.doc

课程设计任务书

学生姓名： 刘颖 专业班级： 计科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盘）。
指导老师署名： 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开发平台
系统：Windows 7
开发工具：Visual studio
语言：C++
3数据类型和系统设计
3.1 存放结构设计
typedef struct
{
int key;
char *p;
}NAME;

typedef struct
{
int key;//关键字
int hash;//初始地址
int reha;//再散列值
char *p;//名字
int l;//查找长度
}HASH;
3.2关键算法设计
3.2.1 NAME（结构体数组）初始化
NAME a[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码相加，所得整数做为关键字。
int i,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.3 HASH(结构体数组)初始化
HASH h[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++)
{
int sum=0;
int hi=(a[i].key)%37;//哈希函数
int hj=(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 //冲突
{
int finh;//最终地址
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打印哈希表
float average=0;
cout<<"关键码 初散列 再散列 哈希地址 查找次数 姓名"<<endl;//格式
for(i=0; i<40; i++)
{
cout<<h[i].key<<"\t"<<h[i].hash<<"\t"<<h[i].reha<<"\t"<<i<<
"\t"<<h[i].l<<"\t"<<h[i].p<<endl;
}

for(i=0;i<40;i++) average+=h[i].l;
average/=30;
cout<<"平均查找长度：ASL="<<average<<endl;
3.2.6在哈希表中查找姓名
int m;
do //m=1,继续查找；m=0,退出查找
{
char *f=new char[20];
int key=0,n=0,g,l=1,adr;
cout<<"请输入姓名拼音:"<<endl;
cin>>f;
for(g=0;*(f+g)!='\0';g++) //求出姓名拼音所对应整数(关键字)
{
n+=*(f+g);
key=n;
}

adr=key%37; //哈希函数求初散列值

if(h[adr].key==key)//分3种情况进行判定
{
cout<<"关键字:"<<key<<endl;
cout<<"初散列值为:"<<h[adr].hash<<endl;
cout<<"再散列值为:"<<h[adr].reha<<endl;
cout<<"表中位置为:"<<adr<<endl;
cout<<"查找长度为: "<<l<<endl;
}
else if (h[adr].key==0) cout<<"无此统计!"<<endl;
else
{
int finh;//最终地址
int sign=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<<"关键字:"<<key<<endl;
cout<<"初散列值为:"<<h[adr].hash<<endl;
cout<<"表中位置为:"<<adr<<endl;
cout<<"查找长度为: "<<l<<endl;
}
}while(sign==0);
}
cout<<"继续查询请输入,退出请输入："<<endl;
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 <iostream>
using namespace std;
int main()
{
typedef struct
{
int key;
char *p;
}NAME;
NAME a[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";
int i,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;
}

}

typedef struct
{
int key;//关键字
int hash;//初始地址
int reha;//再散列值
char *p;//名字
int l;//查找长度
}HASH;
HASH h[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++)
{
int sum=0;
int hi=(a[i].key)%37;//哈希函数
int hj=(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 //冲突
{
int finh;//最终地址
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;
}
}

float average=0;
cout<<"关键码初散列再散列哈希地址查找次数姓名"<<endl; //显示格式
for(i=0; i<40; i++)
{
cout<<h[i].key<<"\t"<<h[i].hash<<"\t"<<h[i].reha<<"\t"<<i
<<"\t"<<h[i].l<<"\t"<<h[i].p<<endl;
}

for(i=0;i<40;i++) average+=h[i].l;
average/=30;
cout<<"平均查找长度：ASL="<<average<<endl;
int m;
do
{
char *f=new char[20];
int key=0,n=0,g,l=1,adr;
cout<<"请输入姓名拼音:"<<endl;
cin>>f;
for(g=0;*(f+g)!='\0';g++) //求出姓名拼音所对应整数(关键字)
{
n+=*(f+g);
key=n;
}
adr=key%37; //哈希函数求初散列值
if(h[adr].key==key)//分3种情况进行判定
{
cout<<"关键字:"<<key<<endl;
cout<<"初散列值为:"<<h[adr].hash<<endl;
cout<<"再散列值为:"<<h[adr].reha<<endl;
cout<<"表中位置为:"<<adr<<endl;
cout<<"查找长度为: "<<l<<endl;
}
else if(h[adr].key==0) cout<<"无此统计!"<<endl;
else
{
int finh;//最终地址
int sign=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<<"关键字:"<<key<<endl;
cout<<"初散列值为:"<<h[adr].hash<<endl;
cout<<"表中位置为:"<<adr<<endl;
cout<<"查找长度为: "<<l<<endl;
}
}while(sign==0);
}
cout<<"继续查询请输入,退出请输入："<<endl;
cin>>m;
}while(m==1);
return 0;
}