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

实验目的 复习顺序查找、二分查找、分块查找的基本算法及适用场合； 掌握哈希查找的基本方法及适用场合，并能在解决实际问题时灵活应用； 巩固在散列查找时解决冲突的方法及特点。 实验内容 哈希表查找的实现（用线性探测法解决冲突）； 能对哈希表进行插入和查找。 实验要求 分析算法思想，利用C（C++）语言完成程序设计。 上机调试通过实验程序。 输入数据，进行哈希插入和查找。 给出具体的算法分析，包括时间复杂度和空间复杂度等。 撰写实验报告。 实验步骤与源程序 ⑴ 实验步骤 本程序共设计了五个函数来实现建表，显示，查找，插入，删除这几个主要功能，然后设计主函数，串接程序，并进行调试，测试实验结果。 ⑵ 源代码 #include dos.h #include conio.h #include math.h #include stdio.h #include stdlib.h #define MAXSIZE 12 //哈希表的最大容量，与所采用的哈希函数有关 enum BOOL{False,True}; enum HAVEORNOT{NULLKEY,HAVEKEY,DELKEY}; //哈希表元素的三种状态，没有记录、有记录、有过记录但已被删除 typedef struct //定义哈希表的结构 { int elem[MAXSIZE]; //数据元素体 HAVEORNOT elemflag[MAXSIZE]; // 元素状态标志，没有记录、有记录、有过记录但已被删除 int count; // 哈希表中当前元素的个数 }HashTable; typedef struct { int keynum; // 记录的数据域，只有关键字一项 }Record; void InitialHash(HashTable); // 初始化哈希表 void PrintHash(HashTable); // 显示哈希表中的所有元素 BOOL SearchHash(HashTable,int,int); // 在哈希表中查找元素 BOOL InsertHash(HashTable,Record); // 在哈希表中插入元素 BOOL DeleteHash(HashTable,Record); // 在哈希表中删除元素 int Hash(int); // 哈希函数 void main() { HashTable H; // 声明哈希表H char ch,j=y; int position,n,k; Record R; BOOL temp; 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): ); sc