数据结构实验9哈希查找

,.1、 实验目的（1)复习顺序查找、二分查找、分块查找的基本算法及适用场合；谢谢阅读（2)掌握哈希查找的基本方法及适用场合，并能在解决实际问题时灵活应用；感谢阅读（3)巩固在散列查找时解决冲突的方法及特点。2、 实验内容（1)哈希表查找的实现（用线性探测法解决冲突）；（2)能对哈希表进行插入和查找。3、 实验要求（1)分析算法思想，利用C（C++）语言完成程序设计。精品文档放心下载（2)上机调试通过实验程序。（3)输入数据，进行哈希插入和查找。（4)给出具体的算法分析，包括时间复杂度和空间复杂度等。精品文档放心下载（5)撰写实验报告。4、 实验步骤与源程序⑴实验步骤本程序共设计了五个函数来实现建表，显示，查找，插入，删除这几个主要功能，然后设计主感谢阅读函数，串接程序，并进行调试，测试实验结果。⑵源代码#include<dos.h>#include<conio.h>#include<math.h>#include<stdio.h>,.#include<stdlib.h>#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; //声明哈希表Hcharch,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<n;k++){ printf("请输入第%3d个整数:",k+1);精品文档放心下载scanf("%d",&R.keynum); //输入要插入的记录感谢阅读temp=InsertHash(H,R);};break;case'2':if(H.count) //哈希表不空谢谢阅读PrintHash(H);elseprintf("\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);精品文档放心下载elseprintf("\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");elseprintf("\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");elseprintf("\n删除元素不在散列表中!\n");谢谢阅读break;default:j='n';}}printf("\n\t欢迎再次使用本程序，再见!\n");精品文档放心下载},.voidInitialHash(HashTable&H)谢谢阅读{

//哈希表初始化inti;H.count=0;for(i=0;i<MAXSIZE;i++)H.elemflag[i]=NULLKEY;}voidPrintHash(HashTableH)谢谢阅读{置

//显示哈希表所有元素及其所在位inti;for(i=0;i<MAXSIZE;i++)

//显示哈希表中记录所在位置printf("%-4d",i);printf("\n");for(i=0;i<MAXSIZE;i++)

//显示哈希表中记录值if(H.elemflag[i]==HAVEKEY)感谢阅读printf("%-4d",H.elem[i]);,.elseprintf("%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;elsereturnFalse; //查找不成功}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、