数据结构实验五 哈希表的查找

★观前提示：本篇内容为数据结构实验，代码内容经测试没有问题，但是可能会不符合每个人实验的要求，因此以下内容建议仅做思路参考。

一、实验目的

(1)掌握哈希表的构造方法和冲突的解决方法；
(2)掌握哈希结构在实际问题中的应用；
(3)掌握哈希查找算法效率评价方法。

二、实验要求

哈希查找也叫散列查找,整个散列查找过程大概分两步。
(1)在存储时通过散列函数计算记录的散列地址,并按此散列地址存储该记录。
(2)当查找时,一样通过散列函数计算记录的散列地址,然后访问散列地址的记录。

★温馨提示：以下代码均为改正过的代码，皆已经过测试。

三、源码实现

#include     
#include    //定义头文件 
#include 

#define NULLKEY -32768 //定义空键值为-32768 即-(2的15次方)

int number = 0;  //定义number数值为0 
 
//哈希表结构体定义 
typedef struct
{
	int *element; // 数据元素存储地址，动态分配数组 
	int sum; //  当前数据元素个数 
}HashTable; //哈希表 
 

//哈希表初始化函数		  
int Init(HashTable *H,int HashSize)
{
	int i;
 
	number = HashSize;
	H->element = (int *)malloc(number * sizeof(int)); //动态分配内存
	H->sum = number;
	for (i = 0; i<number; i++)
	{
		H->element[i] = NULLKEY;
	}
	return 1;
} 
 
//除留余数法
int Hash(int k)
{
	return k % number;
}
 
//Insert函数实现插入 *** 作 
void Insert(HashTable *H, int k)
{
	int addr = Hash(k); 					 
	while (H->element[addr] != NULLKEY)
	{
		addr = (addr+1) % number;//开放定址法
	}
	H->element[addr] = k;
}
//查找函数 
int Search(HashTable *H, int k)
{
	int address = Hash(k); //求哈希地址
 
							
	while (H->element[address] != k)//开放定址法解决冲突
	{
		address = (address+1) % number;
 
		if (H->element[address] == NULLKEY || address == Hash(k))
			return -1;
	}
	return address;
}
//Result实现散列表元素显示的 *** 作 
void Result(HashTable *H)
{
	int i;
	for (i = 0; i<H->sum; i++)
	{
		printf("%d ", H->element[i]);
	}
	printf("\n");
}
//主函数，完成一些变量的定义，以及函数调用和实现等 
int main()
{ 
	//定义变量i,j完成后续遍历 *** 作，定义address作为位置
	//HashSize作为哈希表长度 
	int i, j, address,HashSize;
	HashTable H;
 	printf("请输入要查找的散列表长度："); 
	scanf("%d",&HashSize);
	int array[HashSize] = { NULL };
	
	Init(&H,HashSize);//调用初始化函数 
	
 	printf("请输入关键字集合:");
	for (i = 0; i<HashSize; i++)
	{
		scanf("%d", &array[i]);
		Insert(&H, array[i]);
	}
	Result(&H);
 
	printf("请输入您要查找的元素：");
	scanf("%d", &j);
	address = Search(&H, j);
	if (address == -1){
		printf("元素查找失败\n");
	}
	else{
		printf("元素%d查找成功！其在表中的位置是:%d\n", j,address);		
	}
}

四、实验总结

① 通过本次实验，了解和掌握了哈希表的构造方法，对哈希表有了更深的认识和了解。
② 通过多次尝试对哈希表的代码实现，理解并掌握了哈希表冲突的解决办法。
③ 明白了哈希表的代码实现逻辑，掌握了哈希表的查找算法效率评价方法。

2022.5.22记录：Code_流苏(CSDN)
如有任何疑问，评论回复，看到即回，欢迎大家多多交流学习！
★以上实验内容仅供参考。