Time Limit: 400 ms Memory Limit: 65536 KiB
Submit Statistic Discuss
Problem Description
给定的一组无重复数据的正整数，根据给定的哈希函数建立其对应hash表，哈希函数是H(Key)=Key%P，P是哈希表表长，P是素数，处理冲突的方法采用平方探测方法，增量di=±i^2,i=1,2,3,...,m-1
Input
输入包含多组测试数据，到 EOF 结束。
每组数据的第1行给出两个正整数N(N <= 500)和P(P >= 2N的最小素数)，N是要插入到哈希表的元素个数，P是哈希表表长；第2行给出N个无重复元素的正整数，数据之间用空格间隔。
Output
按输入数据的顺序输出各数在哈希表中的存储位置 (hash表下标从0开始)，数据之间以空格间隔，以平方探测方法处理冲突。
Sample Input
4 11
10 6 4 15
9 11
47 7 29 11 9 84 54 20 30Sample Output
10 6 4 5
3 7 8 0 9 6 10 2 1
Hint
做这个的时候先做的线性哈希表，但总感觉上哪儿不对劲。先完成的部分是二次探测再散列d[ i ]，具体步骤用了下找规律和for循环就写完了，然后就开始正儿八经的按步骤输入关键字，对关键字按照表长p取余。余数记作position,也是关键值放置的初始位置。若表中a[position]的值为0，代表没有插入关键值，进行关键值赋值。当a[position]不为0时，有可能恰好为关键值。若仍然不是关键值，则继续进行合理地址的寻找，利用while循环，结束条件是a[k]=0，相当于找到了一个新的空位置。输出空位置，将该位置的关键字值赋值为key。这儿恰好为关键值一步其实取巧了，正常情况应该是写for循环遍历a[0]到a[p-1]，若出现值等于关键值则直接输出地址。
代码：
#include <iostream>using namespace std;int hash_1(int key,int p)
{return key%p;
}int main()
{int n,p;int d[2000]={0};//作为平方探测法的数组int k=1;int key=0;int position=0;int place=0;while(cin>>n>>p){d[1]=1;int a[2000]={0};for(int i=2;i<=p/2;i++){if(i%2==0){d[i]=-(i/2)*(i/2);}else if(i%2==1){int t=i/2;d[i]=(1+t)*(1+t);}}while(n--){cin>>key;position=hash_1(key,p);if(a[position]==0){a[position]=key;cout<<position;//相当于直接定位完成，需要先进行赋值}else if(a[position]!=0){if(a[position]==key){cout<<position;//当数值与关键值相同时，等于成功找到位置}else{place=position;k=1;while(a[place]!=0)//寻找合适的空位置，从d[1]开始到d[p-1]结束（其实该d[0]）{place=(position+d[k])%p;k++;}a[place]=key;//别忘了赋值，不然就是白插入元素cout<<place;}}if(n>0){cout<<" ";}else if(n==0){cout<<endl;}}}return 0;
}值得注意的是输出格式，以后直接用while循环或for循环过程对下标进行判定，不需要单独再写一遍输入输出