数据结构-哈希表（散列表）-查找方法-开放地址法

常量，KC 关键码的个数

//常量
#define KC 14     //关键码的个数
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
#define NULLKEY 0
#define EQ(a, b) ((a)-(b))
#define LT(a, b) ((a)<(b))
#define LQ(a, b) ((a)<=(b))

哈希表容量递增表，一个合适的素数序列，m是哈希表表长，全局变量

//哈希表容量递增表，一个合适的素数序列，m是哈希表表长，全局变量
int hashsize[]={13,19,29,37};          
int m=0;

别名，用于理解

//元素类型，关键字类型            
typedef int ElemType;
typedef int KeyType;
typedef int Status;

开放定址哈希表的存储结构

//定义开放定址哈希表的存储结构
struct HashTable
{
	ElemType *elem;    //数据元素存储基址，动态分配数组
	int count;         //当前数据元素个数
	int sizeindex;     //hashsize[sizeindex]为当前容量
}; 

哈希表的初始化

//哈希表的初始化
Status lnitHashTable(HashTable *H)
{
	int i;
	m=hashsize[0];//hashsize[0]=13
	(*H).count=0; //当前元素个数为0	
	(*H).sizeindex=m; //初始存储容量
	(*H).elem=(ElemType*) malloc(m*sizeof(ElemType));//给哈希表申请空间地址
	if(!(*H).elem)//存储分配失败
	{
		printf("哈希表建立失败\n");
		exit(UNSUCCESS); 
	}
	for(i=0; i<m; i++)
	{
		(*H).elem[i]=NULLKEY; //未填记录的标志
	}
	
		return SUCCESS;
}

哈希表的销毁

//哈希表的销毁
void DestroyHashTable(HashTable *H)//初始条件：哈希表H存在
{	
	free((*H).elem);
	(*H).elem=NULL;
	(*H).count=0;
	(*H).sizeindex=0;
}

哈希函数和冲突解决办法：开放地址法

//哈希函数
unsigned int Hash(KeyType K)
{
	printf("\n关键码： %d  哈希函数 %d \n", K, K%m);
	return K%m;
}

//冲突解决方法(线性探测再散列)
void collision(int *p, int d)
{
	//开放定址法处理冲突
	*p=(*p+d)%m;
	printf("处理冲突后哈希地址 %d ",*p);
}

在开放定址哈希表H中查找关键码为K的元素

//查找(若该数据元素不在表中,则插入)
Status SearchHash(HashTable H, KeyType K, int *p, int *c)
{
	//在开放定址哈希表H中查找关键码为K的元素，若查找成功，以P指示待查数据元素在表中位置，并返回SUCCESS;
	//否则，以P指示插入位置，并返回 UNSUCCESS
	//c用以计冲突次数，其初值置零，供建表插入时参考。
	*p=Hash(K);//通过哈希函数求得哈希地址
	printf("哈希地址: %d ",*p);
	printf("此位置是否已有关键码: %d \n",H.elem[*p] != NULLKEY);
	while( H.elem[*p] != NULLKEY && EQ(K, H.elem[*p]) )    
		//位置中填有记录,并且关键字不相等
	{
			(*c)++;
			if(*c<m)
				collision(p,*c); //求得下一探查地址P
			else
				break;
			printf("处理冲突后的位置是否已有关键码: %d \n",H.elem[*p] != NULLKEY);
	}
	if (!EQ(K, H.elem[*p]))
	{
		return SUCCESS; //查找成功，P返回待查数据元素位置
	}
	else
		return UNSUCCESS; 
	//查找不成功Helem[*p]==NULLKEY,P返回的是插入位置
}

哈希表的重建

//哈希表的重建
Status lnsertHash(HashTable *H, ElemType);//lnsertHash函数的声明

void RecreateHashTable(HashTable *H, ElemType e)//重建哈希表
{
	int i;
	int count=(*H).count;
	ElemType *elem;
	ElemType *p=(ElemType*) malloc(count*sizeof(ElemType));
	printf("原先的的哈希表：\n");
	for(i=0; i<m; i++)//保存原有的数据到p中
	{
		if(((*H).elem[i]) != NULLKEY)   //该单元有数据
		{
			p[i]=(*H).elem[i];
			printf("(%d,%d) ",i,p[i]);
		}
		else 
		{
			p[i]=NULLKEY;
			printf("(%d,%d) ",i,p[i]);
		}
	}
	printf("\n");
	(*H).count=0;
	(*H).sizeindex++;//增大存储容量
	m=(*H).sizeindex;
	printf("增加哈希表的存储容量到%d \n新建哈希表:",m);
	elem=(ElemType*) realloc( (*H).elem, m*sizeof(ElemType));
	if(!elem) exit(0); //存储分配失败
	(*H).elem=elem;
	for(i=0; i<m; i++)	(*H).elem[i]=NULLKEY; //未填记录的标志(初始化)
	for(i=0; i<m-1; i++)	
	{
		lnsertHash(H,p[i]);//将原有的数据按照新的表长插入到重建的哈希表中		
	}
	lnsertHash(H,e);//最后一个数据
}

在哈希表中插入数据元素

//在哈希表中插入数据元素
Status lnsertHash(HashTable *H, ElemType e)
{
	//查找不成功时插入数据元素e到开放定址哈希表H中，并返回0K;
	//若冲突次数过大,则重建哈希表
	int c,p;
	c=0;
	if(SearchHash(*H,e,&p,&c))     //表中已有与e有相同关键字的元素
	{
		printf("表中已有相同关键字的元素:%d\n", e);
		return DUPLICATE;
	}
	else 
		if( c < 12)		
		{	
			printf("冲突次数%d未达到上限\n", c );			
			(*H).elem[p]=e;//插入e
			(*H).count++;
			return SUCCESS;
		}
		else
		{
			printf("此时关键码为%d \n",e);
			RecreateHashTable(H,e); //重建哈希表
		}
		return UNSUCCESS;
}

哈希表的遍历

//哈希表的遍历
void TraverseHash(HashTable H)
{
	//按哈希地址的顺序遍历哈希表
	int i;
	printf("哈希地址0~%d\n", m-1);
	for(i=0; i<m; i++)
		if(H.elem[i]!=NULLKEY) //有数据
			printf("(%d, %d)  ",i,H.elem[i]);
		printf("\n");
		return;
}

在开放定址哈希表H中查找关键码为K的元素

//在开放定址哈希表H中查找关键码为K的元素，若查找成功,以p指示待查 数据元素在表中位置，并返回SUCCESS;否则返回UNSUCCESS
Status Find(HashTable H, KeyType K, int*p)
{
	int c = 0;
	*p=Hash(K); //求得哈希地址
	while(H . elem[*p]!=NULLKEY && !EQ(K,H.elem[*p]))
	{
		//该位置中填有记录.并且关键字不相等
		c++;
		if (c<m)
			collision(p, c); //求得下一探查地址p
		else
			return UNSUCCESS; //查找不成功(H . elem[p] . key=二NUU_KEY)
	}
	if EQ(K,H . elem[*p])
		return SUCCESS; //查找成功，P返回待查数据元素位置
	return UNSUCCESS; //查找不成功(H.elem[p].key==NULLKEY)
}

主函数用于测试，数组数量在13之前无重建，13之后有重建。是否重建还与数组元素有关。

void main()
{
	KeyType key[]={19,01,23,14,55,20,84,27,68,11,10,77,63,45,24};
	HashTable H;
	ElemType e;
	lnitHashTable(&H);    //构建了一个空的哈希表
	for(int i=0; i<KC; i++)
	{
		e=key[i];
		lnsertHash(&H, e);
	}
	TraverseHash(H);
}