编写一个C/C++程序,实现对于有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77},采用哈希函数:H(key)=key % 13 ,采用开放地址法的线性探测方法解决冲突,试在 0~18 的散列地址空间中对该关键字序列构造哈希表。
时间: 2024-03-12 16:45:53 浏览: 70
好的,以下是一个简单的C++程序,实现对于有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77},采用哈希函数:H(key)=key % 13 ,采用开放地址法的线性探测方法解决冲突,在 0~18 的散列地址空间中对该关键字序列构造哈希表。
```cpp
#include <iostream>
using namespace std;
// 哈希表的大小
const int TABLE_SIZE = 19;
// 哈希表的节点结构体
struct HashNode {
int key;
int value;
};
// 哈希表类
class HashMap {
private:
HashNode* table[TABLE_SIZE];
public:
HashMap() {
for (int i = 0; i < TABLE_SIZE; i++) {
table[i] = NULL;
}
}
// 哈希函数
int hash(int key) {
return key % TABLE_SIZE;
}
// 插入关键字到哈希表中
void put(int key, int value) {
int index = hash(key);
while (table[index] != NULL && table[index]->key != key) {
index = (index + 1) % TABLE_SIZE;
}
if (table[index] != NULL) {
delete table[index];
}
table[index] = new HashNode{key, value};
}
// 获取关键字在哈希表中的值
int get(int key) {
int index = hash(key);
while (table[index] != NULL && table[index]->key != key) {
index = (index + 1) % TABLE_SIZE;
}
if (table[index] != NULL) {
return table[index]->value;
} else {
return -1;
}
}
// 从哈希表中删除指定关键字
void remove(int key) {
int index = hash(key);
while (table[index] != NULL) {
if (table[index]->key == key) {
delete table[index];
table[index] = NULL;
return;
}
index = (index + 1) % TABLE_SIZE;
}
}
// 打印哈希表
void print() {
for (int i = 0; i < TABLE_SIZE; i++) {
if (table[i] != NULL) {
cout << i << ": " << table[i]->value << endl;
} else {
cout << i << ": NULL" << endl;
}
}
}
};
int main() {
// 创建哈希表
HashMap map;
// 插入关键字到哈希表中
map.put(19, 1);
map.put(01, 2);
map.put(23, 3);
map.put(14, 4);
map.put(55, 5);
map.put(20, 6);
map.put(84, 7);
map.put(27, 8);
map.put(68, 9);
map.put(11, 10);
map.put(10, 11);
map.put(77, 12);
// 打印哈希表
map.print();
// 删除指定关键字的节点
map.remove(23);
map.remove(84);
// 打印删除指定关键字后的哈希表
map.print();
return 0;
}
```
注意,这个程序中采用的是开放地址法的线性探测方法来解决冲突,如果需要采用其他方法解决冲突,需要修改哈希表类中的put和get函数。
阅读全文