PAT甲级-1145 Average Search Time

题目

题目大意

题目要求哈希表的大小必须是大于s的素数，给出需要插入的数量n以及需要查找的数目m。要求按照题目给出的哈希函数构造哈希表，使用二次探测法解决冲突。如果某个元素不能插入，按规定格式输出。最后计算平均查找步长。

思路

典型的哈希表数据结构，用平方探测法构建哈希表，并用该哈希表查找元素，计算平均查找次数，根据题目模拟即可。

代码

#include <iostream>
#include <vector>
using namespace std;

bool isPrime(int n){
    for (int i = 2; i < n; i++){
        if (n % i == 0){
            return false;
        }
    }
    return true;
}

int main(){
    int s, n, m;
    cin >> s >> n >> m;
    while (!isPrime(s)){
        s++;
    }  // s必须是素数
    vector<int> v(s, 0);  // 哈希表
    for (int i = 0; i < n; i++){
        int a;
        cin >> a;
        int flag = 0;  // 是否可以插入表
        for (int j = 0; j < s; j++){  // 插入最多探测 s 次
            if (v[(a + j * j) % s] == 0){
                flag = 1;
                v[(a + j * j) % s] = a;
                break;
            }
        }
        if (flag == 0){
            cout << a << " cannot be inserted." << endl;
        }
    }  // 平方探测法构建哈希表

    int sum = 0;  // 总查找次数
    for (int i = 0; i < m; i++){
        int q;
        cin >> q;
        for (int j = 0; j <= s; j++){  // 查找最多探测 s+1 次
            sum++;
            if (v[(q + j * j) % s] == q || v[(q + j * j) % s] == 0){  // 等于0说明该元素不存在，可以停止查找
                break;
            }
        }
    }
    printf("%.1lf\n", sum * 1.0 / m);

    return 0;
}