题目描述
定义哈希函数为H(key) = key。输入表长（大于、等于11），输入关键字集合，用二次探测再散列构建哈希表，并查找给定关键字。
输入
测试次数t
每组测试数据格式如下：
哈希表长m、关键字个数n
n个关键字
查找次数k
k个待查关键字
输出
对每组测试数据，输出以下信息：
构造的哈希表信息，数组中没有关键字的位置输出NULL
对k个待查关键字，分别输出：
0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）
输入样例1
1 12 10 22 19 21 8 9 30 33 4 41 13 4 22 15 30 41
输出样例1
22 9 13 NULL 4 41 NULL 30 19 8 21 33 1 1 1 0 3 1 3 8 1 6 6
AC代码
代码语言：javascript复制#include<iostream>
using namespace std;
int main() {
int t, m, n, k, temp;
cin >> t;
while (t--) {
cin >> m >> n;
int hash[m];
for (int i = 0; i < m; i )
hash[i] = 0x3f3f3f3f;
while (n--) {
cin >> temp;
int h = temp % 11;
if (hash[h] == 0x3f3f3f3f)
hash[h] = temp;
else {
for (int i = 1, j = 1;; i ) {
int plus;
if (i % 2 == 0)
plus = -j * j;
else
plus = j * j;
plus = (h m plus) % m;
if (hash[plus] == 0x3f3f3f3f) {
hash[plus] = temp;
break;
}
if (i % 2 == 0)
j ;
}
}
}
for (int i = 0; i < m - 1; i )
if (hash[i] == 0x3f3f3f3f)
cout << "NULL ";
else
cout<<hash[i]<<' ';
if(hash[m-1]==0x3f3f3f3f)
cout<<"NULL"<<endl;
else cout<<hash[m-1]<<endl;
cin>>k;
while (k--) {
cin >> temp;
int h = temp % 11,count=2;
if(hash[h]==temp){
cout<<"1 1 "<<h 1<<endl;
}else if(hash[h]==0x3f3f3f3f){
cout<<"0 0"<<endl;
}else {
for (int i = 1, j = 1;; count ,i ) {
int plus;
if (i % 2 == 0)
plus = -j * j;
else
plus = j * j;
plus = (h m plus) % m;
if (hash[plus] == temp) {
cout<<"1 "<<count<<' '<<plus 1<<endl;
break;
}else if(hash[plus]==0x3f3f3f3f){
cout<<"0 "<<count<<endl;
break;
}
if (i % 2 == 0)
j ;
}
}
}
}
return 0;
}
