A27927. 散列表平均查找时间本题目标很简单：首先将一系列各不相同的正整数键值插入一张散列表，随后在表中查找另外给定的一个整数键值系列，输出平均查找时间（确定一个数字在或不在表中所需要比较的次数）。这里用到的哈希函数定义为 H(key) = key % TSize，其中 TSize 是散列表的容量。使用平方探测（仅做正向递增的探测）来解决冲突。注意散列表的容量最好是一个素数。如果用户给出的容量不是素数，你必…
填空题
困难
知识点
题目描述
散列表平均查找时间
本题目标很简单：首先将一系列各不相同的正整数键值插入一张散列表，随后在表中查找另外给定的一个整数键值系列，输出平均查找时间（确定一个数字在或不在表中所需要比较的次数）。这里用到的哈希函数定义为 H(key) = key % TSize，其中 TSize 是散列表的容量。使用平方探测（仅做正向递增的探测）来解决冲突。
注意散列表的容量最好是一个素数。如果用户给出的容量不是素数，你必须将容量重新定义为比用户给定容量大的一个最小的素数。
输入
输入第一行给出 3 个正整数：MSize、N、M，分别是用户定义的散列表容量、要插入的键值的数量、以及要查找的键值的数量。这 3 个数都不超过 104。 随后第二行给出 N 个各不相同的正整数键值待插入。第三行给出 M 个正整数键值待查找。同一行中数字间以一个空格分隔，数均不超过 105。
输出
如果某个数无法插入，则在一行中输出 `X cannot be inserted.`，其中 `X` 是那个输入的数字。最后一行输出全部 M 个键值的平均查找时间，精确到小数点后 1 位。
样例输入
4 5 4
10 6 4 15 11
11 4 15 2样例输出
15 cannot be inserted.
2.8参考答案
//参考程序1
#include <iostream>
#include <vector>
#include <iomanip>
// 找到比给定数大的最小素数
int nextPrime(int num) {
if (num <= 2) return 2;
if (num % 2 == 0) num++;
while (true) {
bool isPrime = true;
for (int i = 3; i * i <= num; i += 2) {
if (num % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) break;
num += 2;
}
return num;
}
int main() {
int mSize, n, m;
std::cin >> mSize >> n >> m;
mSize = nextPrime(mSize);
std::vector<int> hashTable(mSize, -1);
// 插入键值
for (int i = 0; i < n; ++i) {
int key;
std::cin >> key;
int hash = key % mSize;
bool inserted = false;
for (int j = 0; j < mSize; ++j) {
int index = (hash + j * j) % mSize;
if (hashTable[index] == -1) {
hashTable[index] = key;
inserted = true;
break;
}
}
if (!inserted) {
std::cout << key << " cannot be inserted." << std::endl;
}
}
// 查找键值
int totalSearchTime = 0;
for (int i = 0; i < m; ++i) {
int key;
std::cin >> key;
int hash = key % mSize;
for (int j = 0; j <= mSize; ++j) {
totalSearchTime++;
int index = (hash + j * j) % mSize;
if (hashTable[index] == key || hashTable[index] == -1) {
break;
}
}
}
// 输出平均查找时间
double averageSearchTime = static_cast<double>(totalSearchTime) / m;
std::cout << std::fixed << std::setprecision(1) << averageSearchTime << std::endl;
return 0;
}
上一题
下一题