数据结构-哈希表（散列表）-查找方法-开放地址法
常量，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);
}