【PAT甲级 - C++题解】1078 Hashing

1078 Hashing

The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be H ( k e y ) = k e y % T S i z e H(key)=key \% TSizeH(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 two positive numbers: MSize (≤104) and N (≤MSize) which are the user-defined table size and the number of input numbers, respectively. Then N distinct positive integers are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print “-” instead.

Sample Input:

4 4
10 6 4 15

Sample Output:

0 1 4 -

题意

这道题给定一个表的大小以及元素的个数，我们需要利用二次探测法来计算每个元素在表中的位置，如果能找到对应位置则输出对应位置的下标，反之输出 - 。另外，表的大小必须为质数，如果给定的不是质数，则需要求出大于该值的最小质数当做表长。

关于什么是二次探测法，我在之前的 C++ 实现查找的博客中有详细讲解，传送门如下：

(239条消息) C++实现查找 - 顺序、二分和哈希查找_Pandaconda的博客-CSDN博客_顺序查找c++

思路

思路如下：

1. 判断表长是否为质数，如果不是则递增表长，直至找到大于给定表长的第一个质数。
2. 查找给定元素在表中的下标位置，通过二次探测法解决哈希冲突，如果能找到一个位置则返回该下标，否则返回 -1 。
3. 根据查找的结果更新哈希表中的值，并输出相应结果。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int h[N];
int m, n;
//判断x是否为质数
bool is_prime(int x)
{
    if (x == 1)    return false;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;
    return true;
}
//用二次探测法计算位置
int find(int x)
{
    int t = x % m;
    for (int k = 0; k < m; k++)
    {
        int i = (t + k * k) % m;
        if (!h[i])   return i;
    }
    return -1;
}
int main()
{
    cin >> m >> n;
    //先确保m为质数
    while (!is_prime(m))  m++;
    //判断数字能否插入到表中
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        //计算是否能找到插入位置
        int t = find(x);
        if (t == -1)   cout << "-";
        else
        {
            h[t] = x;
            cout << t;
        }
        //末尾不能有空格
        if (i != n - 1)  cout << " ";
    }
    return 0;
}