整型关键字的平方探测法散列 (25分)
本题的任务很简单:将给定的无重复正整数序列插入一个散列表,输出每个输入的数字在表中的位置。所用的散列函数是 H(key)=key%TSize,其中 TSize 是散列表的表长。要求用平方探测法(只增不减,即H(Key)+i2 )解决冲突。
注意散列表的表长最好是个素数。如果输入给定的表长不是素数,你必须将表长重新定义为大于给定表长的最小素数。
输入格式:
首先第一行给出两个正整数 MSize(≤104 )和 N(≤MSize),分别对应输入的表长和输入数字的个数。随后第二行给出 N 个不重复的正整数,数字间以空格分隔。
输出格式:
在一行中按照输入的顺序给出每个数字在散列表中的位置(下标从 0 开始)。如果某个数字无法插入,就在其位置上输出 -
。输出间以 1 个空格分隔,行首尾不得有多余空格。
输入样例:
4 4
10 6 4 15
输出样例:
0 1 4 -
#include <iostream>
using namespace std;
int N, M, x, flag = 0;
int v[20005];
int isPrime(int x) {
for (int i = 2; i <= (int)sqrt(x); ++i)
if (x % i == 0)
return 0;
return 1;
}
void Insert(int x) {
for (int i = 0; i < M; ++i)
if (v[(x + i * i) % M] == 0) {
v[(x + i * i) % M] = x;
cout << (x + i * i) % M;
return;
}
cout << "-";
}
int main() {
cin >> M >> N;
M = max(M, 2);
while (!isPrime(M))
M++;
for (int i = 0; i < N; ++i) {
cin >> x;
cout << (i ? " " : "");
Insert(x);
}
return 0;
}
版权声明:本文为qq_45798109原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。