数据结构实验9哈希查找.doc

《数据结构实验9哈希查找.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法设计与分析》实验报告-8-1、实验目的（1)复习顺序查找、二分查找、分块查找的基本算法及适用场合；（2)掌握哈希查找的基本方法及适用场合，并能在解决实际问题时灵活应用；（3)巩固在散列查找时解决冲突的方法及特点。2、实验内容（1)哈希表查找的实现（用线性探测法解决冲突）；（2)能对哈希表进行插入和查找。3、实验要求（1)分析算法思想，利用C（C++）语言完成程序设计。（2)上机调试通过实验程序。（3)输入数据，进行哈希插入和查找。（4)给出具体的算法分析，包括时间复杂度和空间复杂度等。（5)撰写实验报告。4、实验步骤与源程序⑴实验步骤本程序共设计了五个函数来实现建表，显示，查找，插

2、入，删除这几个主要功能，然后设计主函数，串接程序，并进行调试，测试实验结果。⑵源代码#include#include#include#include#include#defineMAXSIZE12//哈希表的最大容量，与所采用的哈希函数有关enumBOOL{False,True};enumHAVEORNOT{NULLKEY,HAVEKEY,DELKEY};//哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除typedefstruct//定义哈希表的结构{intelem[MAXSIZE];//数

3、据元素体HAVEORNOTelemflag[MAXSIZE];//元素状态标志，没有记录、有记录、有过记录但已被删除intcount;//哈希表中当前元素的个数}HashTable;typedefstruct{intkeynum;//记录的数据域，只有关键字一项《算法设计与分析》实验报告-8-}Record;voidInitialHash(HashTable&);//初始化哈希表voidPrintHash(HashTable);//显示哈希表中的所有元素BOOLSearchHash(HashTable,int,int&);//在哈希表中查找元素BOOLInsertHash(HashTab

4、le&,Record);//在哈希表中插入元素BOOLDeleteHash(HashTable&,Record);//在哈希表中删除元素intHash(int);//哈希函数voidmain(){HashTableH;//声明哈希表Hcharch,j='y';intposition,n,k;RecordR;BOOLtemp;InitialHash(H);while(j!='n'){printf("t哈希查找");printf("t**************************************");printf("t*1-----建表*");printf("

5、t*2-----显示*");printf("t*3-----查找*");printf("t*4-----插入*");printf("t*5-----删除*");printf("t*0-----退出*");printf("t**************************************");printf("t请输入菜单号：");scanf("%c",&ch);//输入操作选项switch(ch){case'1':printf("请输入元素个数(<10):");scanf("%d",&n);《算法设计与分析》实验报告-8-pri

6、ntf("");for(k=0;k

7、关键字temp=SearchHash(H,R.keynum,position);//temp=True:记录查找成功；temp=False:没有找到待查记录if(temp)printf("查找成功该元素位置是%d",position);elseprintf("本散列表没有该元素!");}break;case'4':if(H.count==MAXSIZE)//哈希表已满{printf("散列表已经满!");br