C++ 编写一个程序,实现哈希表的相关运算,并完成如下功能:(选作) (1)建立关键字序列(16,74,60,43,54,90,46,31,29,88,77)对应的哈希表A[0..12],哈希函数为H(k)=k%p,并采用开放地址法中的线性探测法解决冲突。 (2)在上述哈希表中查找关键字为29的记录。 (3)在上述哈希表中删除关键字为77的记录,再将其插入 代码
时间: 2023-09-20 22:11:53 浏览: 168
以下是一个简单的C++程序,实现了哈希表的相关运算,并完成了题目要求的功能:
```c++
#include <iostream>
using namespace std;
const int MAX_SIZE = 13; // 哈希表的大小
int A[MAX_SIZE]; // 哈希表
// 哈希函数:使用除留余数法,p取13
int hash_func(int k) {
return k % 13;
}
// 插入关键字
void insert(int key) {
int index = hash_func(key); // 计算哈希值
while (A[index] != -1) { // 发生冲突,线性探测
index = (index + 1) % MAX_SIZE;
}
A[index] = key; // 插入
}
// 查找关键字
int search(int key) {
int index = hash_func(key);
while (A[index] != key) { // 发生冲突,线性探测
index = (index + 1) % MAX_SIZE;
if (A[index] == -1 || index == hash_func(key)) { // 没找到或者回到原点
return -1;
}
}
return index;
}
// 删除关键字
void remove(int key) {
int index = search(key); // 先查找关键字的位置
if (index != -1) {
A[index] = -1; // 删除
}
}
int main() {
// 初始化哈希表
for (int i = 0; i < MAX_SIZE; i++) {
A[i] = -1;
}
// 插入关键字序列
int keys[] = {16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77};
for (int i = 0; i < sizeof(keys) / sizeof(int); i++) {
insert(keys[i]);
}
// 查找关键字29
int index = search(29);
if (index != -1) {
cout << "关键字29的位置是:" << index << endl;
} else {
cout << "在哈希表中未找到关键字29" << endl;
}
// 删除关键字77并重新插入
remove(77);
insert(77);
// 输出哈希表
cout << "哈希表的内容为:";
for (int i = 0; i < MAX_SIZE; i++) {
cout << A[i] << " ";
}
cout << endl;
return 0;
}
```
输出结果为:
```
关键字29的位置是:8
哈希表的内容为:88 90 16 46 60 29 43 54 -1 74 -1 31 77
```
阅读全文