问题描述
从空表开始，将输入元素按照输入顺序逐个插入一个哈希表，以生成哈希表。之后查找元素，输出探测序列，即输出查找过程中经过的结点中的数据。表长为m，哈希函数为Hash(key)=key mod P (P<=m)，用二次探测再散列法处理冲突，即探测序列为Hi=(Hash(key)+di) mod m，其中增量序列为di = 1, -1, 2, -2,3,-3 …, k, -k (k≤m/2)。
输入说明
第一行为三个整数n、m、P，n为输入元素的个数，m为哈希表的表长，P为哈希函数Hash(key)=key mod P中的P。第二行为n个整数，为输入数据。后面每一行是一个要查找的整数，以-1结束。最后的-1不查找。
输出说明
对于每个要查找的数字，在一行上输出探测序列，即输出查找过程中经过的结点中的数据，中间以空格隔开。对于哈希表中不存在的数字，探测到最后一个空位置时，要输出字符串“NULL”。每个数字的探测序列后面要换行。
输入样例
11 14 13
62 42 53 69 100 26 87 74 56 61 48
48
30
8
56
87
61
35
-1
输出样例
100 62 87 74 56 69 26 61 48
69 56 42 87 26 74 100 NULL
87 100 48 NULL
69 56
100 62 87
100 62 87 74 56 69 26 61
#include <stdio.h>
int m,n,P;
int *list;
int search(int x,bool print)
{
int h,hi;
h=hi=x%P;
for (int i=2;i<=m/2*2+2;i++)
{
if (list[hi]==x || list[hi]==-1)
break;
if (print)
printf("%d ",list[hi]);
if (i%2==0)
hi=(h+(i/2)*(i/2))%m;
else
hi=((h-(i/2)*(i/2))%m+m)%m;
}
if (print)
{
if (list[hi]==-1)
printf("NULL\n");
if (list[hi]==x)
printf("%d\n",x);
}
return hi;
}
void insert(int x)
{
int location;
location=search(x,0);
if (list[location]==x)
return;
if (list[location]==-1)
list[location]=x;
else
printf("Table FULL!\n");
}
int main()
{
int i,x;
scanf("%d%d%d",&n,&m,&P);
list=new int[m];
for (i=0;i<m;i++)
list[i]=-1;
for (i=0;i<n;i++)
{
scanf("%d",&x);
insert(x);
}
/*
printf("List is: ");
for (i=0;i<m;i++)
printf("%d ",list[i]);
printf("\n");
*/
for(;;)
{
scanf("%d",&x);
if (x==-1)
return 0;
search(x,1);
}
}