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

数据结构实验五 哈希表的查找,第1张

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

一、实验目的

(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)
如有任何疑问,评论回复,看到即回,欢迎大家多多交流学习!
★以上实验内容仅供参考。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1294701.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-10
下一篇 2022-06-10

发表评论

登录后才能评论

评论列表(0条)

保存