The task of this problem is simple: insert a sequence of distinct positive integers into a hash table first. Then try to find another sequence of integer keys from the table and output the average search time (the number of comparisons made to find whether or not the key is in the table). The hash function is defined to be H(key)=key%TSize where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.
Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.
Input Specification:
Each input file contains one test case. For each case, the first line contains 3 positive numbers: MSize, N, and M, which are the user-defined table size, the number of input numbers, and the number of keys to be found, respectively. All the three numbers are no more than 104. Then N distinct positive integers are given in the next line, followed by M positive integer keys in the next line. All the numbers in a line are separated by a space and are no more than 105.
Output Specification:
For each test case, in case it is impossible to insert some number, print in a line X cannot be inserted. where X is the input number. Finally print in a line the average search time for all the M keys, accurate up to 1 decimal place.
Sample Input:
4 5 4 10 6 4 15 11 11 4 15 2
Sample Output:
15 cannot be inserted. 2.8
题目大意：哈希表问题。第一行给三个数字，分别是哈希表大小，输入个数，查询个数，接着给出要插入到哈希表中的数据，再给出查询数据，要求计算平均搜索时间。
注意：使用平方探测法，而且是正数的平方探测法！！例如H(x)=1，则探测的为1，1+1，1+4，1+9，1+16......
如果使用了负数，只能得三分，有三个测试点过不去！
查询时也一样，正数正数！！
计算搜索时间得时候只需要计算比较了多少次，注意两个数字相等也算一次比较，看看比较了多少次查了出来，或者比较了多少次发现查不出来。
注意如果再平方探测序列内发现有没有插入的空位，说明这个数字根本不在哈希表里，否则早插到空位里面了。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10010;
int H[maxn], tsize;
bool isprime(int n) {
for(int i = 2; i * i <= n; i++)
if(n % i == 0) return false;
return true;
}
bool insert(int n){ //要插入的数字
int hash = n % tsize;
for(int i = 0; i < tsize; i++){
int idx1 = hash + i * i;
//int idx2 = hash - i * i;
while(idx1 >= tsize) idx1 %= tsize;
//while(idx2 < 0) idx2 += tsize;
if(H[idx1] == -1){
H[idx1] = n;
return true;
}
/*if(H[idx2] == -1){
H[idx2] = n;
return true;
}*/
}
return false;
}
int main(){
fill(H, H + maxn, -1);
int icnt, qcnt;
cin >> tsize >> icnt >> qcnt;
while(!isprime(tsize)) tsize++;
for(int i = 0; i < icnt; i++){
int num;
cin >> num;
if(!insert(num)) cout << num << " cannot be inserted." << endl;
}
int ans = 0;
for(int i = 0; i < qcnt; i++) {
int tmp;
cin >> tmp;
for(int j = 0; j <= tsize; j++) {
ans++;
int pos = (tmp + j * j) % tsize;
if(H[pos] == tmp || H[pos] == -1) break;
}
}
printf("%.1f\n", ans * 1.0 / qcnt);
return 0;
}