拉链法实现哈希表和哈希表开放定址法

显示全部楼层 · 发表于 2011-12-31 22:32:54

/*
*哈希表拉链法
*/
#include<stdio.h>
#include<stdlib.h>
#define MinTableSize 10
typedef int ElemType;
typedef unsigned int Index;
typedef struct ListNode
{
ElemType element;
struct ListNode *next;
}*Position;
typedef Position List;
/* List *TheList will be an array of lists, allocated later */
/* The lists use headers (for simplicity), */
/* though this wastes space */
typedef struct HashTbl
{
int TableSize;
List *TheLists;
}*HashTable;
int NextPrime(int N)
{
int i;
if(N%2==0)
N++;
for(;;N+=2)
{
for(i=3;i*i<=N;i+=2)
if(N%i==0)
return 0;
return N;
}
}
/*Hash function for ints*/
Index Hash(ElemType Key,int TableSize)
{
return Key%TableSize;
}
HashTable InitializeTable(int TableSize)
{
HashTable H;
int i;
if(TableSize<MinTableSize)
{
printf("Table size too small!\n");
return NULL;
}
/*Allocate table*/
H=(HashTable)malloc(sizeof(struct HashTbl));
if(NULL==H)
printf("Out of space!!!\n");
H->TableSize=NextPrime(TableSize);
/*Allocate array of lists*/
H->TheLists=(List *)malloc(sizeof(List)*H->TableSize);
if(NULL==H->TheLists)
{
printf("Out of space!!!\n");
free(H);
return NULL;
}
/*Allocate list headers*/
for(i=0;i<H->TableSize;i++)
{
H->TheLists[i]=(Position)malloc(sizeof(struct ListNode));
if(NULL==H->TheLists[i])
printf("Out of space!!!\n");
else
H->TheLists[i]->next=NULL;
H->TheLists[i]->element=0;//哈希表中所有元素的key初始化为0
}
return H;
}
Position Find(ElemType Key,HashTable H)
{
Position p;
List L;
L=H->TheLists[Hash(Key,H->TableSize)];
p=L->next;
while(p!=NULL&&p->element!=Key)/*Probably need strcmp!!*/
p=p->next;
return p;
}
void Insert(ElemType Key,HashTable H)
{
Position pos,newCell;
List L;
pos=Find(Key,H);
if(NULL==pos)/*Key is not found*/
{
newCell=(Position)malloc(sizeof(struct ListNode));
if(NULL==newCell)
printf("Out of space!!!");
else
{
L=H->TheLists[Hash(Key,H->TableSize)];
newCell->next=L->next;
newCell->element=Key;/*Probably need strcpy*/
L->next=newCell;
}
}
}
void DestroyTable(HashTable H)
{
int i;
for(i=0;i<H->TableSize;i++)
{
Position p=H->TheLists[i];
Position temp;
while(p!=NULL)
{
temp=p->next;
free(p);
p=temp;
}
}
free(H->TheLists);
free(H);
}
void printHash(HashTable H,int len)
{
int i;
for(i=0;i<len;i++)
{
Position p=H->TheLists[i];
while(p)
{
printf("address=%d value=%d\n",i,p->element);
p=p->next;
}
}
}
int main()
{
HashTable H;
Position p=NULL;
int array[]={19,14,23,01,68,20,84,27,55,11,10,79};
int len=sizeof(array)/sizeof(array[0]);
int i;
ElemType k;
H=InitializeTable(len);
for(i=0;i<len;i++)
{
Insert(array[i],H);
}
printHash(H,len);
printf("\n\n");
printf("please input the value which need find:");
scanf("%d",&k);
p=Find(k,H);
if(p)
printf("%d",p->element);
else
printf("cannot find the value!");
printf("\n\n");
printf("free the table\n");
DestroyTable(H);
printf("it's done!!!");
printf("\n\n");
return 0;
}

复制代码

/*
*哈希表
*/
#include<stdio.h>
#include<stdlib.h>
#define NULLKEY 0//0为无记录标志
#define N 10//数据元素个数
typedef int KeyType;//设关键字域为整型
typedef struct
{
KeyType key;
int ord;
}ElemType;//数据元素类型
#define EQ(a,b) ((a)==(b))
int hashsize[]={11,19,29,37};//哈希表容量递增表一个合适的素数序列
int m=0;//哈希表表长全局变量
typedef struct
{
ElemType *elem;//数据元素存储基址动态分配数组
int count;//当前数据元素个数
int size_index;//hashsize[size_index]为当前容量
}HashTable;
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
/* 操作结果: 构造一个空的哈希表 */
int initHashTable(HashTable *H)
{
int i;
(*H).count=0;//当前元素个数为0
(*H).size_index=0;//初始存储容量为hashsize[0]
m=hashsize[0];
(*H).elem=(ElemType *)malloc(m*sizeof(ElemType));
if(!(*H).elem)
exit(0);//存储分配失败
for(i=0;i<m;i++)
(*H).elem[i].key=NULLKEY;//未填记录的标记
return 1;
}
/* 初始条件:哈希表H存在*/
/* 操作结果:销毁哈希表H*/
void destroyHashTable(HashTable *H)
{
free((*H).elem);
(*H).elem=NULL;
(*H).count=0;
(*H).size_index=0;
}
/* 一个简单的哈希函数(m为表长全局变量)*/
unsigned Hash(KeyType K)
{
return K%m;
}
/*线性探测再散列*/
void collision(int *p,int d)
{
*p=(*p+d)%m;//开放定址法处理冲突
}
/* 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据 */
/* 元素在表中位置,并返回SUCCESS;否则,以p指示插入位置,并返回UNSUCCESS */
/* c用以计冲突次数，其初值置零，供建表插入时参考 */
int searchHash(HashTable H,KeyType K,int *p,int *c)
{
*p=Hash(K);//求得哈希地址
while(H.elem[*p].key!=NULLKEY&&!EQ(K,H.elem[*p].key))//该位置中填有记录并且关键字不相等
{
(*c)++;
if(*c<m)
collision(p,*c);//求得下一探查地址p
else
break;
}
if EQ(K,H.elem[*p].key)
return SUCCESS;//查找成功 p返回待查数据元素位置
else
return UNSUCCESS;//查找不成功(H.elem[p].key==NULLKEY p返回的是插入的位置)
}
int insertHash(HashTable *,ElemType);//对函数的声明
void recreateHashTable(HashTable *H)//重建哈希表
{
int i,count=(*H).count;
ElemType *p,*elem=(ElemType *)malloc(count*sizeof(ElemType));
p=elem;
printf("重建哈希表\n");
for(i=0;i<m;i++)//保存原有的数据到elem中
if(((*H).elem+i)->key!=NULLKEY)//该单元有数据
*p++=*((*H).elem+i);
(*H).count=0;
(*H).size_index++;//增大存储容量
m=hashsize[(*H).size_index];
p=(ElemType *)realloc((*H).elem,m*sizeof(ElemType));
if(!p)
exit(0);//存储分配失败
(*H).elem=p;
for(i=0;i<m;i++)
(*H).elem[i].key=NULLKEY;//未填记录买的标志（初始化）
for(p=elem;p<elem+count;p++)//将原有的数据按照新的表长插入到重建的哈希表中
insertHash(H,*p);
}
/* 查找不成功时插入数据元素e到开放定址哈希表H中，并返回1 */
/* 若冲突次数过大，则重建哈希表 */
int insertHash(HashTable *H,ElemType e)
{
int c,p;
c=0;
if(searchHash(*H,e.key,&p,&c))//表中已有与e有相同关键字的元素
return DUPLICATE;
else if(c<hashsize[(*H).size_index]/2)//冲突次数c未达到上线 c的阀值可调
{
(*H).elem[p]=e;//插入e
++(*H).count;
return 1;
}
else
recreateHashTable(H);//重建哈希表
return 0;
}
/* 按哈希地址的顺序遍历哈希表 */
void traverseHash(HashTable H,void(*Vi)(int ,ElemType))
{
int i;
printf("哈希地址0~%d\n",m-1);
for(i=0;i<m;i++)
{
if(H.elem[i].key!=NULLKEY)//有数据
Vi(i,H.elem[i]);
}
}
/* 在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据 */
/* 元素在表中位置,并返回SUCCESS;否则,返回UNSUCCESS */
int find(HashTable H,KeyType K,int *p)
{
int c=0;
*p=Hash(K);//求得哈希地址
while(H.elem[*p].key!=NULLKEY&&!EQ(K,H.elem[*p].key))//该位置中填有记录．并且关键字不相等
{
c++;
if(c<m)
collision(p,c); //求得下一探查地址p
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)
}
if EQ(K,H.elem[*p].key)
return SUCCESS; //查找成功，p返回待查数据元素位置
else
return UNSUCCESS; // 查找不成功(H.elem[p].key==NULLKEY)
}
void printHash(int p,ElemType r)
{
printf("address=%d (%d %d)\n",p,r.key,r.ord);
}
int main()
{
ElemType r[N]={{17,1},{60,2},{29,3},{38,4},{1,5},{2,6},{3,7},{4,8},{60,9},{13,10}};
HashTable h;
int i,p;
int j;
KeyType k;
initHashTable(&h);
for(i=0;i<N-1;i++)//插入前N-1个记录
{
j=insertHash(&h,r[i]);
if(j==DUPLICATE)
printf("表中已有关键字尾%d的记录无法再插入记录(%d %d)\n",r[i].key,r[i].key,r[i].ord);
}
printf("按哈希地址的顺序遍历哈希表\n");
traverseHash(h,printHash);
printf("\n\n");
printf("请输入带查找记录的关键字:");
scanf("%d",&k);
j=find(h,k,&p);
if(j==SUCCESS)
printHash(p,h.elem[p]);
else
printf("没找到\n");
printf("\n\n");
j=insertHash(&h,r[i]);//插入第N个记录
if(j==0)//j==ERROR 重建哈希表
j=insertHash(&h,r[i]);//重建哈希表后重新插入第N个记录
printf("按哈希地址的顺序遍历重建后的哈希表\n");
traverseHash(h,printHash);
printf("\n\n");
printf("请输入带查找记录的关键字:");
scanf("%d",&k);
j=find(h,k,&p);
if(j==SUCCESS)
printHash(p,h.elem[p]);
else
printf("没找到\n");
printf("\n\n");
destroyHashTable(&h);
printf("哈希表销毁成功!");
printf("\n\n");
return 0;
}

复制代码

显示全部楼层 · 发表于 2011-12-31 22:40:18

看不懂

显示全部楼层 · 发表于 2012-1-1 00:28:48

不知道用途

显示全部楼层 · 发表于 2012-1-1 00:48:20

卡饭怎么还有这么牛的问题？

显示全部楼层 · 发表于 2012-1-1 03:11:26

技术贴？

[分享] 拉链法实现哈希表 和 哈希表 开放定址法

[分享] 拉链法实现哈希表和哈希表开放定址法