hash.cpp

一个简单的HASH表的建立与HASH过程演示.

#include <stdio.h>
#include <conio.h>
#include <malloc.h>

#define N 26             //数据元素个数
  
int hashsize[]={27,49};  //哈希表容量递增表,一个合适的素数序列
int m=0;                 //哈希表表长,全局变量  

typedef long KeyType;    //设关键字为长整型

struct ElemType{         //数据元素(记录)类型
  KeyType key;
};

struct HashTable{
  ElemType *elem;        //数据元素基址
  int count;             //当前元素个数
  int sizeindex;         //hashsize[sizeindex]为当前容量
};

int InitHashTable(HashTable &H) 
{ //构造一个空的哈希表
  int i;
  H.count=0;
  H.sizeindex=0; 
  m=hashsize[0];
  H.elem=(ElemType *)malloc(m*sizeof(ElemType));
  if(!H.elem)
	   return -1;
  for(i=0;i<m;i++)
	  H.elem[i].key=0;
   return 1;
}
void DestroyHashTable(HashTable &H)
{ //销毁哈希表
  free(H.elem);
  H.elem=NULL;
  H.count=0;
  H.sizeindex=0;
}

unsigned Hash(KeyType K)
{ //哈希函数
  return K%m;
}
 
void collision(int &p,int d)
{ //开放定址法处理冲突
  p=(p+d)%m;
}
int SearchHash(HashTable &H,KeyType K,int &p,int &c)
{ //在哈希表中查找关键字为K的元素,若查找成功,以p指示待查找数据元素
  //在表中的位置,并返回1;否则,以p指示插入位置,并返回0.
  //c用以计冲突次数.
  p=Hash(K);
  while(H.elem[p].key!=0&&(K!=H.elem[p].key)){
   c++;
   if(c<m)
	   collision(p,c);
   else
	  break;
  }
  if(K==H.elem[p].key)
	  return 1;
  else 
	 return 0;


}
int InsertHash(HashTable &H,ElemType e)
{ //查找不成功时插入数据元素e到哈希表H中,并返回1;
  //若冲突次数过大,则返回0.
  int c,p;
  c=0;
  if(SearchHash(H,e.key,p,c))
	  return 10;
  else if(c<hashsize[H.sizeindex]/2){
    H.elem[p]=e;
	++H.count;
	return 1;
  }
  else
	return 0;
}

void print(int p,ElemType r)
{ //打印哈希表
  printf("address=%d: %d\t\t",p,r.key);
}

void TravelHash(HashTable H,void(*vi)(int,ElemType))
{ //按哈希地址的顺序遍历哈希表
  int i;
  printf("\t\t  HashAddress 0-----%d\n",m-1);
  for(i=0;i<m;i++){
	  if(H.elem[i].key!=0)
		  vi(i,H.elem[i]);
	  if((i+1)%2==0)putchar(10);
	}
}

void main()
{
   ElemType r[N];
   HashTable h;
   int i;
   int j;
   for(i=0;i<N;i++)r[i].key=20042148+i;
   InitHashTable(h);
   for(i=0;i<N;i++){
	//插入N个记录
    j=InsertHash(h,r[i]);
    if(j==10)
		//若记录已存在
		printf("HashTable has the %d elem.\n",r[i].key);
   }
   printf("\t\t    TraverHashTable:\n");
   TravelHash(h,print);  //遍历哈希表
   DestroyHashTable(h);  //销毁哈希表
}