题目

题目链接 PAT A1078
hash表，平方探测解决冲突，插入数据并返回插入位置
注：hash表长必须为质数，若不为质数，需要转换为大于指定表长n的最小质数为表长

解题思路

平方探测hash函数H(key)=(key+d*d)%m;(d=0,1,2,..表长-1)
1 若不冲突，插入返回位置
2 若冲突，平方探测，有空位置，插入并返回位置
3 若冲突，平方探测，探测一轮后i从0~表长-1，没有空位置，打印'-'

易错点

1 找到插入位置后，除了打印，还要将数据插入该位置或者标记该位置已占用

单词语法

Quadratic probing /kwɑˈdrætɪk/ 二次探测
(with positive increments only) 只正序探测
solve the collisions 解决冲突

Code

Code 01

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
bool isPrime(int x) {
    if(x<=1)return false;
    int sqr = (int)sqrt(1.0*x);
    for(int i=2; i<=sqr; i++) {
        if(x%i==0)return false;
    }
    return true;
}
int main(int argc,char * argv[]) {
    int m,n,k;
    scanf("%d%d",&m,&n);
    while(!isPrime(m))m++;
    int ht[m]= {0};
    for(int i=0; i<n; i++) {
        scanf("%d",&k);
        int h = k%m;
        //平方探测
        int j;
        for(j = 0; j<m&&ht[(h+j*j)%m]!=0; j++);
        if(i!=0)printf(" ");
        if(j>=m)printf("-"); //如果没有探测到位置 
        else { //如果探测到位置 
            int hq = (h+j*j)%m;
            ht[hq]=k;
            printf("%d",hq);
        }
    }
    return 0;
}