#include <stdio.h>
#include <malloc.h>
#define m 13 // mod number
#define n 13 //
#define NLL 0 // 初始化值
typedef struct nodetype
{
int key;
struct nodetype *next;
} CHashTable;
/******初始化哈希表******/
void HashListInit(CHashTable **HT[])
{
int i;
for(i=0;i<n;i++)
HT[i]=NLL;
}
/******清空哈希表******/
void HashListClear(CHashTable **HT)
{
CHashTable *p;
int i;
for(i=0;i<n;i++)
{
p=HT[i];
while(p!=NULL)
{
HT[i]=p->next;
HashListDelete(**HT,p->key); // 删除结点,并释放空间
p=HT[i];
}
}
}
/******哈希函数******/
int Hash(int k)
{
return k%m; //取余模型
}
/****** 在哈希表中查找元素******/
int HashListSearch(CHashTable **HT,int k) // 1-找到,0-未找到
{
int d;CHashTable *p;
d=Hash(k); // 哈希值
p=HT[d]; //结点地址给p
while(p!=NULL)
{
if(p->key==k) // 找到了,返回退出
return(1);
else
p=p->next; // 继续寻找
}
return 0; // 未找到,返回0
}
/******在哈希表中插入一个元素(key)******/
void HashListInsert(CHashTable **HT,int k)
{
int d;
CHashTable *p; // 定义一个临时表结点
d=Hash(k);
p=(CHashTable *)malloc(sizeof(CHashTable)); // 申请一段空间
p->key=k;
p->next=HT[d];
HT[d]=p;
}
int HashListDelete(CHashTable **HT,int k)
{
int d;
CHashTable *p,*q;
d=Hash(k);
p=HT[d];
if(p==NULL)
{
printf("哈希表中无%d\n",k);
exit(1);
}
if(p->key==k)
{
HT[d]=p->next;
free(p); // 释放结点
return;
}
else
{
q=p->next;
while(q!=NULL)
{
if(q->key==k)
{
p->next=q->next;
free(q);
return ;
}
else // 依次向链表后面寻找
{
p=q;
q=q->next;
}
}
}
printf("哈希表中无%d\n",k);
exit(1);
}
/*****输出哈希表中所有元素***** */
void PrintHashList(CHashTable **HT)
{
int i;CHashTable *p;
for(i=0;i<n;i++)
{
p=HT[i];
printf("\n ");
printf("%d-> ",i);
while(p)
{
printf("%d->",p->key);
p=p->next; // 依次打印相近数
}
printf("空");
}
}
main()
{
/***********拉链法**************/
int k,i;
CHashTable **HT[n];
HashListInit(HT);
for(i=0;i<13;i++) // 给 hash 赋值
HashListInsert(HT,i);
HashListInsert(HT,13); // 0
HashListInsert(HT,26); // 0
HashListInsert(HT,39); // 0
HashListInsert(HT,17);
HashListInsert(HT,14);
printf("所建立的哈希表:\n");
PrintHashList(HT);
printf("\n");
printf("请输入要删除的关键字:");
scanf("%d",&k);
HashListDelete(HT,k);
printf("删除后的哈希表:\n");
PrintHashList(HT);
printf("\n");
printf("请输入要插入的关键字:");
scanf("%d",&k);
HashListInsert(HT,k);
printf("插入后的哈希表:\n");
PrintHashList(HT);
getchar();
getchar();
system("pause");
}
