问题描述

从空表开始，将输入元素按照输入顺序逐个插入一个哈希表，以生成哈希表。之后查找元素，输出探测序列，即输出查找过程中经过的结点中的数据。表长为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);
	}
}