hash.h

数据结构算法之一

#include "iostream.h"
#include "string.h"
#include "malloc.h"
#define SUCCESS 1
#define OK 1
#define UNSUCCESS 0
#define DUPLICATE -1
#define NULLKEY ""
#define DIV_P 37
#define DIV_P2 31
#define PLUS_P 30
#define TABLE_LEN 40

typedef int Status;

typedef char KeyType[20];

#define EQ(a,b) (!strcmp((a),(b)))
#define LT(a,b) (strcmp((a),(b))<0)
#define LQ(a,b) (strcmp((a),(b))<=0)
int hashsize[]={TABLE_LEN};
typedef struct{
KeyType key;
}ElemType;

typedef struct{
ElemType *elem;
int count;
int sizeindex;
}HashTable;

void  collision(HashTable H,int &p2,int &c2)
{p2=(p2)*PLUS_P%DIV_P2+1;

if(strcmp(H.elem[p2].key,NULLKEY)!=0) collision(H,p2,c2);

}

Status Hash(KeyType K)
{int p=0;
for(int i=0;i<int(strlen(K));i++)
{p+=int(K[i]);
}
p=p%DIV_P;
 return p;
}

Status SearchHash(HashTable H,KeyType K,int &p1,int &c1)
{
 p1=Hash(K);
 //while(H.elem[p1].key!=NULLKEY&&!EQ(K,H.elem[p1].key))
 if(H.elem[p1].key!=NULLKEY&&!EQ(K,H.elem[p1].key))
	collision(H,p1,++c1);
 if(EQ(K,H.elem[p1].key))
	 return SUCCESS;
 else  return UNSUCCESS;

}

Status InsertHash(HashTable &H,ElemType e)
{int c=0,p;
if(SearchHash(H,e.key,p,c))
return DUPLICATE;
else if(c<hashsize[H.sizeindex/2]){
	H.elem[p]=e; ++H.count;return OK;
}
else return UNSUCCESS;
}