哈希表设计.docx
《哈希表设计.docx》由会员分享，可在线阅读，更多相关《哈希表设计.docx（20页珍藏版）》请在冰点文库上搜索。
哈希表设计
学号
数据结构课程设计
设计说明书
哈希表设计
起止日期：
2012年1月2日至2012年1月6日
学生姓名
班级
成绩
指导教师（签字）
电子与信息工程系
2012年1月6日
天津城市建设学院
课程设计任务书
2011—2012学年第1学期
电子与信息工程系专业班级
课程设计名称：
数据结构课程设计
设计题目：
完成期限：
自2012年1月2日至2012年1月6日共1周
设计依据、要求及主要内容（可另加附页）：
一、设计目的
熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。
二、设计要求
（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；
（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。
凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；
（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；
（4）认真编写课程设计报告。
三、设计内容
针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。
假设人名为中国人姓名的汉语拼音形式。
待填入哈希表的人名共有30个，取平均查找长度的上限为2。
哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。
四、参考文献
1．王红梅．数据结构．清华大学出版社
2．王红梅．数据结构学习辅导与实验指导．清华大学出版社
3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社
目录
一、需求分析3
二、总体设计4
三、详细设计6
四、调试与测试9
五、核心源程序清单和执行结果10
六、心得体会14
一、需求分析
（1）程序的功能：
需要通过输入想要查找的人的姓名，通过除留余数法构造的哈希函数在哈希表中查找这个人的姓名是否存在，为了避免余数相同的数据存放在相同的地址产生冲突，程序中采用线性探测散列法或链地址法处理冲突，从而实现更加快速准确的查找。
（2）输入输出的要求：
在弹出的运行框中先输入查找按键，在输入所要查找的人的姓名，如果不输入查找按键则会显示格式不正确，输入查找按键，在输入所要查找的人名，如果表中存在则显示成功，若果不存在则显示查找失败，执行完查找任务后按退出按键退出查找程序。
1.输入的姓名存在显示查找成功2.没有选择查找按键格式不正确，重新选择显示查找成功3.查找执行成功，选择退出程序。
二、总体设计
（1）问题模型：
散列的基本思想示意图
（2）总体流程图：
（3）除留余数法
除留余数法的基本思想是：
选择某个适当的正整数P，以关键码除以P的余数作为散列地址。
公式：
H（key）=keymodp
（4）处理冲突的方法
1.线性探测法
当发生冲突时，线性探测法从冲突位置的下一个位置起，一次寻找空的三列地址，即对于键值key,设H（key）=d，闭散列表的长度为m，则发生冲突时，寻找下一个散列地址的公式为：
Hi=（H（key）+di）%m（di=1,2,…,m-1）
2.链地址法
拉链法的基本思想是：
将所有散列表地址相同的记录，即多有关键码为同义词的记录存储在一个单链表中—称为同义词子表，在散列表中存储的是所有同义词子表的头指针。
设n个记录存储在长度为m的开散列表中，则同义词子表的平均长度为n/m。
链地址法流程图
三、详细设计
（1）建立存储姓名的哈希表，在表中定义所需要的函数公式
#pragmaonce
#include
usingnamespacestd;
//存储姓名的hash表
classNameHash
{
public:
NameHash（void）;
~NameHash（void）;
NameHash（intnameNum,stringname[]）;
boolSearch（stringname）;
voidAdd（stringname）;
unsignedintcount;
private:
intClassicHash（stringname）;//经典的字符串散列函数
intResidueHash（stringname）;//除留余数法构造hash函数
staticconstintmaxnamenum=50;
stringname[maxnamenum];
intnameNum;//存储的姓名数
};
（2）定义一个虚构函数：
NameHash:
:
NameHash（void）
{
this->nameNum=0;
}
NameHash:
:
~NameHash（void）
{
}
（3）定义一个相加求和函数：
NameHash:
:
NameHash（intnameNum,stringname[]）
{
this->nameNum=0;
for（inti=0;i{
this->Add（name[i]）;
}
}
（4）实现查询功能的函数：
boolNameHash:
:
Search（stringname）//查询
{
//intkey=this->ClassicHash（name）;
intkey=this->ResidueHash（name）;
count=key;
for（inti=key;imaxnamenum;++i）
{
if（this->name[i].empty（））
returnfalse;
if（this->name[i%this->maxnamenum]==name）{
returntrue;
}
count=i-count;
}
returnfalse;
}
在表里添加数据
voidNameHash:
:
Add（stringname）
{
//intkey=this->ClassicHash（name）;
intkey=this->ResidueHash（name）;
if（this->Search（name））
return;
if（this->nameNum+1>this->maxnamenum）
{
throw（"溢出"）;
}
++（this->nameNum）;
while（true）
{
if（this->name[key++].empty（））
{
this->name[--key]=name;
return;
}
}
}
intNameHash:
:
ResidueHash（stringname）
{
unsignedlongsum=0;
for（inti=0;i{
sum+=name[i]*i/10;
}
returnsum%this->maxnamenum;
}
（5）执行程序
#include"stdafx.h"
#include"NameHash.h"
#include
#include
usingnamespacestd;
voidRun（）
{
NameHashnameHash;
stringname;
ifstreaminput;
input.open（"G:
//刘琦//HashTable//name.txt"）;//打开文件
if（!
input.is_open（））
{
cout<<"文件读取失败?
<exit
（1）;
}
while（input.good（））
{
input>>name;
nameHash.Add（name）;
}
input.close（）;//关闭文件t
stringchoice;
while（true）
{
cout<<"s:
查找e：
退出i:
插入\n";
cin>>choice;
while（"s"!
=choice&&"e"!
=choice&&"i"!
=choice）
{
cout<<"命令不合法_，请重新输入\n";
cin>>choice;
}
if（"s"==choice）
{
cout<<"请输入你要查找的姓名\n";
cin>>name;
if（nameHash.Search（name））{
cout<<"存在\n";
unsignedinti=nameHash.count;
cout<<"经过y"<}
else
cout<<"不存在\n";
}
elseif（"i"==choice）{
ofstreamoutput;
output.open（"G:
//刘琦//HashTable//name.txt",ios:
:
app）;
cout<<"请输入姓名:
";
cin>>name;
if（nameHash.Search（name）==false）{
nameHash.Add（name）;
output<}
output.close（）;
}
else
exit
（1）;
}
}
int_tmain（intargc,_TCHAR*argv[]）
{
Run（）;
return0;
}
四、调试与测试
1.开始的时候由于选择的函数不合适导致执行查找功能时，比较的次数比较多查找的效率比较低，经过改进的函数进一步提高了查找执行的效率。
五、核心源程序清单和执行结果
NameHash.h
#pragmaonce
#include
#include
usingnamespacestd;
//存储洹_姓名的hash表括_
classNameHash
{
public:
NameHash（void）;
~NameHash（void）;
NameHash（intnameNum,stringname[]）;
boolSearch（stringname）;
voidAdd（stringname）;
unsignedintcount;
private:
intClassicHash（stringname）;//经典的字符串散列函数
intResidueHash（stringname）;//除留余数法构造hash函数
staticconstintmaxnamenum=50;
stringname[maxnamenum];
intnameNum;//存储的姓名数
};
NameHash.cpp
#include"Stdafx.h"
#include"NameHash.h"
NameHash:
:
NameHash（void）
{
this->nameNum=0;
}
NameHash:
:
~NameHash（void）
{
}
NameHash:
:
NameHash（intnameNum,stringname[]）
{
this->nameNum=0;
for（inti=0;i{
this->Add（name[i]）;
}
}
boolNameHash:
:
Search（stringname）//查é询ˉ
{
//intkey=this->ClassicHash（name）;
intkey=this->ResidueHash（name）;
count=key;
for（inti=key;imaxnamenum;++i）
{
if（this->name[i].empty（））
returnfalse;
if（this->name[i%this->maxnamenum]==name）{
returntrue;
}
count=i-count;
}
returnfalse;
}
voidNameHash:
:
Add（stringname）
{
if（Search（name）==false）{
//intkey=this->ClassicHash（name）;
intkey=this->ResidueHash（name）;
if（this->Search（name））
return;
if（this->nameNum+1>this->maxnamenum）
{
throw（"溢?
出?
"）;
}
++（this->nameNum）;
while（true）
{
if（this->name[key++].empty（））
{
this->name[--key]=name;
return;
}
}
}
}
intNameHash:
:
ClassicHash（stringname）
{
unsignedlongh=0;
for（string:
:
size_typei=0;i{
h=（h<<4）+name[i]++;
unsignedlongg=h&0xf0000000L;
if（g）h^=g>>24;
h&=~g;
}
returnh%this->maxnamenum;
}
intNameHash:
:
ResidueHash（stringname）
{
unsignedlongsum=0;
for（string:
:
size_typei=0;i{
sum+=name[i]*i/47;
}
returnsum%this->maxnamenum;
}
HashTable.cpp
//HashTable.cpp:
定义控制台应用程序的入口点。
//
#include"stdafx.h"
#include"NameHash.h"
#include
#include
usingnamespacestd;
voidRun（）
{
NameHashnameHash;
stringname;
ifstreaminput;
input.open（"G:
//刘琦123//HashTable//name.txt"）;//打开文件
if（!
input.is_open（））
{
cout<<"文件读取失败?
<exit
（1）;
}
while（input.good（））
{
input>>name;
nameHash.Add（name）;
}
input.close（）;//关?
闭?
文?
件t
stringchoice;
while（true）
{
cout<<"s:
查找e：
退出i:
插入\n";
cin>>choice;
while（"s"!
=choice&&"e"!
=choice&&"i"!
=choice）
{
cout<<"命令不合法_，请重新输入\n";
cin>>choice;
}
if（"s"==choice）
{
cout<<"请输入你要查找的姓名\n";
cin>>name;
if（nameHash.Search（name））{
cout<<"存在\n";
unsignedinti=nameHash.count;
cout<<"经过y"<}
else
cout<<"不存在\n";
}
elseif（"i"==choice）{
ofstreamoutput;
output.open（"G:
//刘琦//HashTable//name.txt",ios:
:
app）;
cout<<"请输入姓名:
";
cin>>name;
if（nameHash.Search（name）==false）{
nameHash.Add（name）;
output<}
output.close（）;
}
else
exit
（1）;
}
}
int_tmain（intargc,_TCHAR*argv[]）
{
Run（）;
return0;
}
执行结果
（1）输入的姓名存在显示查找成功
（2）没有选择查找按键格式不正确，重新选择显示查找成功
（3）查找执行成功，选择退出程序
（4）显示查找的次数
（5）执行添加功能
六．心得体会
通过这次课程设计的学习，让我明白了编写程序的思路是很重要的。
在编写程序前先要理清自己的思路，然后再将思路分划成几个模块，一块一块的编写，最后再将所有的模块联系起来，组成一个完整的程序。
在编程序时也遇到了很多困难，比如说编写处理冲突的程序时总是会出一些错误，通过这些遇到的这些困难让我明白了在编写程序是一定要细心认真，无论出来多少错误提示都要耐心的修改。
通过这次课设让我也认识到数据结构是一门看起来容易做起来很难得的课程，我们必须花费更多的时间去学习。
这次的课程设计让我学到了很多，对编写程序也有了进一步的掌握。
升级会员 