哈希表查找的设计Word文件下载.docx
《哈希表查找的设计Word文件下载.docx》由会员分享，可在线阅读，更多相关《哈希表查找的设计Word文件下载.docx（13页珍藏版）》请在冰点文库上搜索。
数据关系：
R1={<
ai-1,ai>
|ai-1∈D,i=1,2,...n}
基本操作：
Initiate（&
h）
操作结果：
构造一个空的哈希表h。
SearchHash（h,x,p）
初始条件：
哈希表h已存在；
p为除留余数法中除数，由用户指定。
查找表中元素与指定数据x比较。
元素已存在时返回其所在位置的负数下标、不存在时返回其位置的正数下标、遍历哈希表后未查找到时返回表长。
Insert（&
h,x,p）
哈希表h已存在。
查找操作后插入元素x至哈希表。
若元素已存在或哈希表已满时插入操作失败，返回值为0。
Delete（&
查找操作后从哈希表中删除元素x。
若元素不在表中时删除操作失败，返回值为0。
Print（h）
显示哈希表中元素及存储状态。
Clear（&
清空哈希表。
}ADTHashTable
2.程序模块：
Hash.h——头文件，包含哈希表抽象数据类型。
Hash.cpp——主程序，为哈希表操作面板。
5．程序代码：
——————Hash.h文件——————
#include<
malloc.h>
iostream.h>
iomanip.h>
process.h>
ctype.h>
#defineTableSize20//哈希表长20
#defineSUCCESS1
#defineUNSUCCESS0
typedefintStatus;
typedefstruct
{//定义元素关键字类型
intkey;
}Elemtype;
{//定义哈希表中基本单元,包含数据与标志两部分
Elemtypeelem;
//数据部分,存放关键字
inttag;
//标志部分,tag=0表示表单元为空,
//tag=1表示表单元已存放数据元素,
//tag=-1表示表单元中存放的数据已被删除
}HashItem;
{//定义哈希表,包含表单元数组与当前存储量
HashItemtable[TableSize];
intcurrentSize;
//当前哈希表存储量
}HashTable;
StatusInitiate（HashTable*h）
{//初始化操作
inti;
for（i=0;
i<
TableSize;
i++）
{
（*h）.table[i].tag=0;
//tag标志置为0
（*h）.table[i].elem.key=NULL;
//空单元默认值设为NULL
}
（*h）.currentSize=0;
returnSUCCESS;
intSearchHash（HashTableh,Elemtypex,intp）
{//查找元素操作
inti=x.key%p;
//除留余数法定哈希地址,主程序中定义一不大于表长的素数p
intj=i;
while（h.table[j].tag==1&
&
h.table[j].elem.key!
=x.key）
{//冲突时
j=（j+1）%TableSize;
//开放定址法,线性探测再散列,求出新位置j
if（j==i）
{
cout<
<
"
哈希表中未查找到"
x.key<
endl;
returnTableSize;
//全表遍历后未搜索到所给元素,返回表长
}
if（h.table[j].tag==1）//元素已存在时返回其位置的负数下标
{cout<
该元素在哈希表的第"
j<
位"
return-j;
}
else//元素不存在时返回其位置的下标
returnj;
StatusInsert（HashTable*h,Elemtypex,intp）
{//插入元素操作
inti=SearchHash（*h,x,p）;
//先调用查找操作
if（i<
0）//元素已存在时,插入失败
元素已存在,无法再录入,操作失败！
endl<
returnUNSUCCESS;
else
if（i!
=TableSize&
（*h）.table[i].tag!
=1）//哈希表有剩余空间时,进行插入操作
{
（*h）.table[i].elem.key=x.key;
//插入元素
（*h）.table[i].tag=1;
//tag标志置为1
（*h）.currentSize++;
//表存储量加1
录入成功！
returnSUCCESS;
else
if（i==TableSize）//哈希表已满时,插入失败
{cout<
哈希表已满,无法再插入"
，操作失败！
returnUNSUCCESS;
StatusDelete（HashTable*h,Elemtypex,intp）
{//删除元素操作
=0）//查找成功,元素存在时,进行删除操作
（*h）.table[-i].elem.key=NULL;
//单元值设为NULL
（*h）.table[-i].tag=-1;
//tag标志置为-1
（*h）.currentSize--;
//表存储量减1
cout<
删除成功！
returnSUCCESS;
删除失败！
returnUNSUCCESS;
StatusPrint（HashTableh）
{//打印表操作
cout<
哈希表序数存储情况存储元素"
for（inti=0;
i<
i++）
setw（4）<
setw（10）<
h.table[i].tag<
h.table[i].elem.key<
表中非空元素个数：
h.currentSize<
StatusClear（HashTable*h）
{//置空表操作
{（*h）.table[i].tag=0;
（*h）.table[i].elem.key=NULL;
（*h）.currentSize=NULL;
哈希表已全部置空！
——————Hash.cpp文件——————
intmain（）
********HashTableTestFile********"
HashTableh;
Initiate（&
h）;
intprime;
请输入一个小于20的质数：
;
cin>
>
prime;
charchoice;
while
（1）
————————————————————————"
按a输出哈希表"
按b查找指定元素在表中的位置"
按c录入元素"
按d删除元素"
按e清空哈希表"
按其他键退出"
请选择：
cin>
choice;
switch（choice）
case'
a'
:
{Print（h）;
break;
b'
{cout<
请输入需要查找的元素的值：
Elemtypea;
cin>
a.key;
SearchHash（h,a,prime）;
break;
c'
请输入需要输入的元素个数（1~20）：
intn,i;
n;
Elemtype*pi=0;
pi=（Elemtype*）malloc（n*sizeof（Elemtype））;
cout<
请依次输入"
n<
个元素的值：
for（i=0;
{cin>
pi[i].key;
Insert（&
h,pi[i],prime）;
d'
请输入需要删除的元素的值：
Elemtypec;
c.key;
Delete（&
h,c,prime）;
e'
{Clear（&
default:
{return0;
6．运行结果：
程序运行，先按要求输入一小于20的质数作为除留余数法的除数因子。
现取7。
显示主面板，选择录入数据。
先输入本次需要录入数据的个数，现取5。
再依次录入数据，现输入{326,547,233,145,985}。
选择输出哈希表，并显示当前表中存储元素个数。
默认未存储的单元“存储元素”为0，可以从“存储情况”一栏判断存储元素为“0”还是为“空”。
选择查找指定元素在表中的位置。
输入已存在的元素“233”与不存在的元素“14”，显示如下：
再次选择录入数据。
分别输入已存在的元素“233”与不存在的元素“14”，显示如下：
选择删除数据。
分别删除已存在的元素“985”与不存在的元素“211”，显示如下：
再次选择输出哈希表。
经过上述操作后，哈希表现存储状态如下：
其中新增元素14存储在哈希表第0位，删除元素985原所在的第6位“存储情况”标志显示为-1。
7．小结：
哈希表作为一种存储与查找的优化方式，通过把关键码值映射到数表中一个位置来访问数据，以加快查找速度。
在日常生活中，哈希函数的应用也是随处可见。
当今十分流行的P2P数据传输技术中一系列的压缩、打包以及积分标准都应用到了hash算法设置。
可见利用哈希函数用途之广。
本次程序设计中利用“除留余数法”构造哈希函数，并用“开放定址法”中的“线性探测再散列”方式处理冲突，选取较为简单的整型数字作为存储数据。
通过此次实验，我对哈希表抽象数据类型的定义以及构造方法有了初步的认识和了解，也为今后编写更复杂的应用程序提供了新的思想方法与实现基础。
升级会员 