数据结构实验9哈希查找.docx
《数据结构实验9哈希查找.docx》由会员分享，可在线阅读，更多相关《数据结构实验9哈希查找.docx（9页珍藏版）》请在冰点文库上搜索。
数据结构实验9哈希查找
1、实验目的
（1）复习顺序查找、二分查找、分块查找的基本算法及适用场合；
（2）掌握哈希查找的基本方法及适用场合，并能在解决实际问题时灵活应用；
（3）巩固在散列查找时解决冲突的方法及特点。
2、实验内容
（1）哈希表查找的实现（用线性探测法解决冲突）；
（2）能对哈希表进行插入和查找。
3、实验要求
（1）分析算法思想，利用C（C++）语言完成程序设计。
（2）上机调试通过实验程序。
（3）输入数据，进行哈希插入和查找。
（4）给出具体的算法分析，包括时间复杂度和空间复杂度等。
（5）撰写实验报告。
4、实验步骤与源程序
实验步骤
本程序共设计了五个函数来实现建表，显示，查找，插入，删除这几个主要功能，然后设计主函数，串接程序，并进行调试，测试实验结果。
源代码
#include
#include
#include
#include
#include
#defineMAXSIZE12//哈希表的最大容量，与所采用的哈希函数有关
enumBOOL{False,True};
enumHAVEORNOT{NULLKEY,HAVEKEY,DELKEY};//哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除
typedefstruct//定义哈希表的结构
{intelem[MAXSIZE];//数据元素体
HAVEORNOTelemflag[MAXSIZE];//元素状态标志，没有记录、有记录、有过记录但已被删除
intcount;//哈希表中当前元素的个数
}HashTable;
typedefstruct
{intkeynum;//记录的数据域，只有关键字一项
}Record;
voidInitialHash（HashTable&）;//初始化哈希表
voidPrintHash（HashTable）;//显示哈希表中的所有元素
BOOLSearchHash（HashTable,int,int&）;//在哈希表中查找元素
BOOLInsertHash（HashTable&,Record）;//在哈希表中插入元素
BOOLDeleteHash（HashTable&,Record）;//在哈希表中删除元素
intHash（int）;//哈希函数
voidmain（）
{HashTableH;//声明哈希表H
charch,j='y';
intposition,n,k;
RecordR;
BOOLtemp;
InitialHash（H）;
while（j!
='n'）
{
printf（"\n\t哈希查找"）;
printf（"\n\t**************************************"）;
printf（"\n\t*1-----建表*"）;
printf（"\n\t*2-----显示*"）;
printf（"\n\t*3-----查找*"）;
printf（"\n\t*4-----插入*"）;
printf（"\n\t*5-----删除*"）;
printf（"\n\t*0-----退出*"）;
printf（"\n\t**************************************"）;
printf（"\n\n\t请输入菜单号：
"）;
scanf（"%c",&ch）;//输入操作选项
switch（ch）
{
case'1':
printf（"\n请输入元素个数（<10）:
"）;
scanf（"%d",&n）;
printf（"\n"）;
for（k=0;k{printf（"请输入第%3d个整数:
",k+1）;
scanf（"%d",&R.keynum）;//输入要插入的记录
temp=InsertHash（H,R）;
};
break;
case'2':
if（H.count）//哈希表不空
PrintHash（H）;
else
printf（"\n散列表为空表!
\n"）;
break;
case'3':
if（!
H.count）
printf（"\n散列表为空表!
\n"）;//哈希表空
else
{printf（"\n请你输入要查找元素（int）:
"）;
scanf（"%d",&R.keynum）;//输入待查记录的关键字
temp=SearchHash（H,R.keynum,position）;
//temp=True:
记录查找成功；temp=False:
没有找到待查记录
if（temp）
printf（"\n查找成功该元素位置是%d\n",position）;
else
printf（"\n本散列表没有该元素!
\n"）;
}
break;
case'4':
if（H.count==MAXSIZE）//哈希表已满
{printf（"\n散列表已经满!
\n"）;
break;}
printf（"\n请输入要插入元素（int）:
"）;
scanf（"%d",&R.keynum）;//输入要插入的记录
temp=InsertHash（H,R）;
//temp=True:
记录插入成功；temp=False:
已存在关键字相同的记录
if（temp）
printf（"\n元素插入成功!
\n"）;
else
printf（"\n元素插入失败，相同元素本散列表已经存在!
\n"）;
break;
case'5':
printf（"\n请你输入要删除元素（int）:
"）;
scanf（"%d",&R.keynum）;//输入要删除记录的关键字
temp=DeleteHash（H,R）;
//temp=True:
记录删除成功；temp=False:
待删记录不存在
if（temp）
printf（"\n删除成功!
\n"）;
else
printf（"\n删除元素不在散列表中!
\n"）;
break;
default:
j='n';
}
}
printf（"\n\t欢迎再次使用本程序，再见!
\n"）;
}
voidInitialHash（HashTable&H）
{//哈希表初始化
inti;
H.count=0;
for（i=0;iH.elemflag[i]=NULLKEY;
}
voidPrintHash（HashTableH）
{//显示哈希表所有元素及其所在位置
inti;
for（i=0;iprintf（"%-4d",i）;
printf（"\n"）;
for（i=0;iif（H.elemflag[i]==HAVEKEY）
printf（"%-4d",H.elem[i]）;
else
printf（"%4c",''）;
printf（"\ncount:
%d\n",H.count）;//显示哈希表当前记录数
}
BOOLSearchHash（HashTableH,intk,int&p）
{//在开放定址哈希表H中查找关键字为k的数据元素，若查找成功，以p指示
//待查数据元素在表中的位置，并返回True；否则，以p指示插入位置，并返回False
intp1;
p1=p=Hash（k）;//求得哈希地址
while（H.elemflag[p]==HAVEKEY&&k!
=H.elem[p]）//该位置中填有记录并且关键字不相等
{p++;//冲突处理方法：
线性探测再散列
if（p>=MAXSIZE）
p=p%MAXSIZE;//循环搜索
if（p==p1）
returnFalse;//整个表已搜索完，没有找到待查元素
}
if（k==H.elem[p]&&H.elemflag[p]==HAVEKEY）//查找成功，p指示待查元素位置
returnTrue;
else
returnFalse;//查找不成功
}
BOOLInsertHash（HashTable&H,Recorde）
{//查找不成功时插入元素e到开放定址哈希表H中，并返回True，否则返回False
intp;
if（SearchHash（H,e.keynum,p））//表中已有与e有相同关键字的元素
returnFalse;
else
{H.elemflag[p]=HAVEKEY;//设置标志为HAVEKEY，表示该位置已有记录
H.elem[p]=e.keynum;//插入记录
H.count++;//哈希表当前长度加一
returnTrue;
}
}
BOOLDeleteHash（HashTable&H,Recorde）
{//在查找成功时删除待删元素e，并返回True，否则返回False
intp;
if（!
SearchHash（H,e.keynum,p））//表中不存在待删元素
returnFalse;
else
{H.elemflag[p]=DELKEY;//设置标志为DELKEY，表明该元素已被删除
H.count--;//哈希表当前长度减一
returnTrue;
}
}
intHash（intkn）
{return（kn%11）;}//哈希函数：
H（key）=keyMOD11
5、测试数据与实验结果（可以抓图粘贴）
（1）菜单：
（2）建表
（3）显示
（4）查找
（5）插入
（6）删除
6、结果分析与实验体会
本次实验是参考了范例程序，经过自己的改写，从而实现要求。
先做简单的输出，一步步的再做其它格式的设置。
这次的实验我们要做的是哈希查找，要求我们复习顺序查找，二分查找，分块查找等基本算法，进一步巩固散列查找时解决冲突的方法和特点，在调试程序的过程中，遇到很多问题，但还是都得以解决。
升级会员 