#include
#include
#include
typedef struct
{
int key;
//char data;
}record;
/*m是hash表的长度，第一个函数是取得小于m最大的质数
d第二个函数是探测数据的地址，也就是说利用key%p得到的余数，余数肯定是小于p的所以可以填充
hash表，hash表不一定要填满所以p
hash表可以存满吗？怎么存满的？*/
int hp(int m)//m为哈希表的长度
{
int i,p,flag=1;
for(p=m;p>=2;p--)
{
for(i=2;i<(int)sqrt(p)+1;i++)
{
if(p%i==0)
{
flag=0;
break;
}
}
if(flag==1)
{
break;
}
flag=1;
}
return p;
}
int hi(int key,int p)
{
return key%p;
}
void Input(record**r,int n)
{
int i;
(*r)=(record*)malloc(n*sizeof(record));
printf("输入数据%d数:\n",n);
for(i=0;i<n;i++)
scanf("%d",&(*r)[i].key);
}
void CreateHashTable(record**ht,record*r,int n,int m,int p)
{
int i,j;//j是地址数据储存的地址
(*ht)=(record*)malloc(m*sizeof(record));
for(i=0;i<m;i++)
(*ht)[i].key=0;//存放关键字的数组初始化
for(i=0;i<n;i++)
{
j=hi(r[i].key,p);
while((*ht)[i].key!=0)//存留余数法找到
j=(j+1)%m;//找到为0的地址也就是初始化后没有存放值的地方
(*ht)[j].key=r[i].key;
}
}
int search(record*ht,int key,int p,int*k)
{
int i;
*k=1;
i=hi(key,p);
while(ht[i].key!=0&&ht[i].key!=key)
{
i++;
++*k;
}
if(ht[i].key==0)
return -1;
else
return i;
}
int main()
{
record*r,*ht;
int key,i,n,m,p,k;
char ch='0';
printf("\n输入记录个数n，和散列表的长度m:\n");
scanf("%d%d",&n,&m);
Input(&r,n);
p=hp(m);
printf("这个小于表长的质数是:%d",p);
CreateHashTable(&ht,r,n,m,p);
printf("\n得到的散列表：");
printf("\n位置");
for(i=0;i<m;i++)
{
printf("%d ",i);
}
printf("\n");
for(i=0;i<m;i++)
printf("%d ",ht[i].key);
do
{
printf("\n输入要查找的关键字:\n");
scanf("%d",&key);
i=search(ht,key,p,&k);
if(i!=-1)
{
printf("查找成功,位置是：%d",i);
printf("\n比较次数是:%d ",k);
}
else
{
printf("查找失败");
printf("\n比较次数是：%d\n",k);
}
// ch=getchar();
}while(ch=='y'||ch=='Y');
}
