#include<stdio.h>
#include<string.h>
#include<malloc.h>
#define MaxSize 100
#define NULLKEY -1
#define DELKEY -2
typedef int KeyType;
typedef char* InfoType;
typedef struct
{
KeyType key;//关键字
InfoType data;//其他数据
int count; //探查次数
}HashTable[MaxSize];
HashTable ha;
//拉链法查询
int SearchHT(HashTable ha,int p,KeyType k)
{
typedef struct node
{
int val;
node * next;
};
//拉链法
node *pt;
int i=0,adr;
adr=k%p;
// pt=(node*)malloc(sizeof(pt));
pt=(node*)ha[adr].key;
if(ha[adr].key!=NULLKEY)
{
while(pt!=NULL)
{
if(pt->val==k)
return ha[adr].key;//返回该元素所在链表的头指针pt=pt->next;
}
}
return -1;
}
//删除
void DeleteHT(HashTable ha,int p,int k,int n) {
int adr;
int adr2;
adr2=k%p;
typedef struct node
{
int val;
node * next;
};
//拉链法
node *pt,*r;
adr=SearchHT(ha,p,k);//查找关键字
pt=(node*)adr;
if(adr!=-1)
{
while(pt->val!=k)
{
r=pt;
pt=pt->next;
}
if(pt->val==k)
{
if((int)pt==adr)
{
if(pt->next==NULL)
ha[adr2].key=NULLKEY;
else
adr=(int)pt->next;
}
else
r->next=pt->next;
}
ha[adr2].count--;
}
else
printf("删除失败！");
}
//插入
void InsertHT(HashTable ha,int n,KeyType k,int p)
{/*
int i,adr;
adr=k%p;
if(ha[adr].key==NULLKEY||ha[adr].key==DELKEY) //直接插入哈希表{
ha[adr].key=k;
ha[adr].count=1;
}
else //采用线性探查的方法解决冲突
{
i=1;
do
{
adr=(adr+1)%p;
i++;
}
while( ha[adr].key!=NULLKEY && ha[adr].key!=DELKEY) ;
ha[adr].key=k;
ha[adr].count=i;
}
n++;*/
typedef struct node
{
int val;
node * next;
};
//拉链法
node *pt,*s;
int adr;
int i;
adr=k%p;
if(ha[adr].key==NULLKEY)
{
pt=(node*)malloc(sizeof(pt));
ha[adr].key=(int)pt;
pt->val=k;
pt->next=NULL;
ha[adr].count=1;
}
else
{
pt=(node*)ha[adr].key;
s=(node*)malloc(sizeof(pt));
s->val=k;
for(i=1;i<ha[adr].count;i++)
{
pt=pt->next;
}
pt->next=s;
s->next=NULL;
ha[adr].count++;
}
n++;
}
//创建哈希表
void CreateHT(HashTable ha,KeyType x[],int n,int m,int p) {
int i,n1=0;
for(i=0;i<m;i++)
{
ha[i].key=NULLKEY;
ha[i].count=0;
}
for(i=0;i<n;i++)
{
InsertHT(ha,n1,x[i],p);
}
}
void main()
{
int s,d,i;
int sadr;
KeyType x[]={12,4,2,5,7,8};
CreateHT(ha,x,6,100,5);
printf("哈希表创建完成！\n");
while(1)
{
printf("输入查找的关键字:");
scanf("%d",&s);
sadr=SearchHT(ha,5,s);
if(sadr==-1)
printf("查找失败！\n");
else
printf("关键字%d的地址为%d:",s,sadr); printf("输入删除的关键字:");
scanf("%d:",&d);
DeleteHT(ha,5,d,6);
printf("关键字%d删除完成!",d);
printf("输入插入数据:");
scanf("%d",&i);
InsertHT(ha,6,i,5);
}
}。