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