《数据结构》课程设计 之 哈希查找

一． 题目
哈希查找
概述：
哈希表的查找过程与构造哈希表的过程基本一致，即给定关键字key值并根据构造哈希表时设定的哈希函数求得其存储地址。若哈希表的此存储地址中没有记录，则查找失败；否则将该地址中的关键字值与key进行比较，若相等则査找成功；否则根据构造哈希表时设定的解决冲突方法寻找下一个哈希地址，知道查找成功或查找到哈希地址中无记录（既查找失败）为止。
我们约定，对哈希表Hash中未存放记录的数组元素 Hash[i]，其标志是Hash[i]值为-1并且，对冲突的处理采用线性探测法； Hash[i]值为-2表示存放于 Hash[i]的关键字值已被删除，但查找到该项时不应终止查找。下面以长度为11的闭散列（哈希）表为例给出在哈希表上的插入、查找和删除算法。初始时哈希表中的关键字值全部置为-1，表示该哈希表为空。
二． 任务

1. 了解哈希函数和哈希表的有关概念
2. 掌握哈希表的建立与查找方法

三． 实验内容

用除留余数法建立一个哈希表，然后在哈希表中实现查找和删除功能。

四．程序

#include "stdafx.h"
#include<stdio.h>
#define MAXSIZE 11
#define key 11 
void Hash_Insert(int Hash[],int x)
{
	int i=0,t;
	t=x%key;
	while(i<MAXSIZE)
	{
		if(Hash[t]<=-1)
		{
			Hash[t]=x;
			break;
		}
		else
			t=(t+1)%key;
		i++;
	}
	if(i==MAXSIZE)
		printf("Hashlist is full!\n");
}

void Hash_search(int Hash[],int x)
{
	int i=0,t;
	t=x%key;
	while(Hash[t]!=-1&&i<MAXSIZE)
	{
		if(Hash[t]==x)
		{
			printf("Hash position of %d is %d\n",x,t);
			break;
		}
		else
			t=(t+1)%key;
		i++;
	}
	if(Hash[t]==-1||i==MAXSIZE)
		printf("No found!\n");
}

void Hash_Delete(int Hash[],int x)
{
	int i=0,t;
	t=x%key;
	while(Hash[t]!=-1&&i<MAXSIZE)
	{
		if(Hash[t]==x)
		{
			Hash[t]=-2;
			printf("%d in Hashlist is deleteded!\n",x);
			break;
		}
		else
			t=(t+1)%key;
		i++;
	}
	if(i==MAXSIZE)
		printf("Delete fail!\n");
}
void main()
{
	int i,x,Hash[MAXSIZE];
	for(i=0;i<MAXSIZE-1;i++)
		Hash[i]=-1;
	i=0;
	printf("Make Hashlist, Input data(-1 stop):\n");
	scanf("%d",&x);
	while(x!=-1&&i<MAXSIZE)
	{
		Hash_Insert(Hash,x);
		scanf("%d",&x);
	}
	printf("output Hashlist:\n");
	for(i=0;i<MAXSIZE-1;i++)
		printf("%4d",Hash[i]);
	printf("\ninput search data:\n");
	scanf("%d",&x);
	Hash_search(Hash,x);
	printf("\nDelete record in Hashlist ,input key:\n");
	scanf("%d",&x);
	Hash_Delete(Hash,x);
	printf("Output Hashlish after record deleted:\n");
	for(i=0;i<MAXSIZE;i++)
		printf("%4d",Hash[i]);
	printf("\nInsert key of record in Hashlist,:\n");
	scanf("%d",&x);
	Hash_Insert(Hash,x);
	printf("Output Hashlist after record inserted:\n");
	for(i=0;i<MAXSIZE;i++)
		printf("%4d",Hash[i]);
	printf("\n");
}

五． 结果

结果分析：
首先输入 24 20 36 22 48 12 32 38 -1
输出生成哈希表（如下图所示）

地址	0	1	2	3	4	5	6	7	8	9	10
关键字	22	12	24	36	48	38				20	32

然后查找关键字 36
输出关于关键字的信息 Hash position of 36 is 3
删除关键字 48

输出删除后的哈希表 （如下图所示）

地址	0	1	2	3	4	5	6	7	8	9	10
关键字	22	12	24	36	-2	38				20	32

再插入关键字 56
输出插入记录后的哈希表（如下图所示）

地址	0	1	2	3	4	5	6	7	8	9	10
关键字	22	12	24	36	56	38				20	32