PTA散列表平方探测法解决冲突
核心问题
当所有的位置都被填上了,且不能插入关键词,要进入死循环了怎么办?
题目
本题的任务很简单:将给定的无重复正整数序列插入一个散列表,输出每个输入的数字在表中的位置。所用的散列函数是 H(key)=key%TSize,其中 TSize 是散列表的表长。要求用平方探测法(只增不减,即H(Key)+i2)解决冲突.
注意散列表的表长最好是个素数。如果输入给定的表长不是素数,你必须将表长重新定义为大于给定表长的最小素数。
输入格式
首先第一行给出两个正整数 MSize(≤104)和 N(≤MSize),分别对应输入的表长和输入数字的个数。随后第二行给出 N 个不重复的正整数,数字间以空格分隔。
输出格式
在一行中按照输入的顺序给出每个数字在散列表中的位置(下标从 0 开始)。如果某个数字无法插入,就在其位置上输出 -。输出间以 1 个空格分隔,行首尾不得有多余空格。
输入样例
4 4
10 6 4 15
输出样例
0 1 4 -
AC代码
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
int is(int n) {
if(n == 1)return 0;
if(n == 2 || n == 3)return 1;
if(n % 6 != 1 && n % 6 != 5)return 0;
for(int i = 5;i * i <= n;i += 6)
if(n % i == 0 || n % (i + 2) == 0)return 0;
return 1;
}
int main() {
int m,n;
int s,p,v[10007] = {0};
scanf("%d %d",&m,&n);
while(!is(m))m ++;
//因为平方以后只需要到m,就能完全探测到整个散列表,具体去看数学推导
for(int i = 0;i < n;i ++) {
p = -1;//判断是否插入成功
scanf("%d",&s);
for(int j = 0;j < m;j ++) {
if(!v[(s + j * j) % m]) {
v[(s + j * j) % m] = 1;
p = (s + j * j) % m;
break;
}
}
if(i)putchar(' ');
if(p == -1)printf("-");
else printf("%d",p);
}
}
核心代码
//让从i到n,如果关键词能够查下去的则一定能,否则不能
for(int j = 0;j < m;j ++) {
if(!v[(s + j * j) % m]) {
v[(s + j * j) % m] = 1;
p = (s + j * j) % m;
break;
}
}
标签:平方,return,表长,int,PTA,列表,include,输入
From: https://www.cnblogs.com/Archer-lian/p/16986131.html