对于给定20个人的姓名,用除留余数法构造哈希函数,用线性探测再散列 法处理冲突,构造哈希表: (2)、对于给定的一个姓名,在哈希表上进行查找,如果其存在则将其删除,否则将其插入到该哈希表上c➕➕
时间: 2024-03-08 19:50:43 浏览: 110
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数采用除留余数法构造,用线性探测再散列法处理冲突。
好的,我理解错了你的问题,你需要用 C++ 语言实现哈希表的插入和查找操作。下面是一个简单的实现,使用了除留余数法构造哈希函数,使用线性探测再散列法处理冲突。
```c++
#include <iostream>
#include <string>
using namespace std;
const int MAX_SIZE = 20; // 哈希表的大小
const int PRIME = 23; // 除留余数法中的质数
const int EMPTY = -1; // 表示哈希表中一个位置为空
int hash_func(string name) {
int hash_value = 0;
for (int i = 0; i < name.length(); i++) {
hash_value = (hash_value * PRIME + name[i]) % MAX_SIZE;
}
return hash_value;
}
int linear_probe(int index, int i) {
return (index + i) % MAX_SIZE;
}
void insert(string name, int hash_table[]) {
int hash_value = hash_func(name);
int i = 0;
while (hash_table[hash_value] != EMPTY) {
i++;
hash_value = linear_probe(hash_value, i);
if (i == MAX_SIZE) {
cout << "Hash table is full!" << endl;
return;
}
}
hash_table[hash_value] = hash_value;
}
bool search(string name, int hash_table[]) {
int hash_value = hash_func(name);
int i = 0;
while (hash_table[hash_value] != EMPTY) {
if (hash_table[hash_value] == name) {
return true;
}
i++;
hash_value = linear_probe(hash_value, i);
if (i == MAX_SIZE) {
break;
}
}
return false;
}
bool remove(string name, int hash_table[]) {
int hash_value = hash_func(name);
int i = 0;
while (hash_table[hash_value] != EMPTY) {
if (hash_table[hash_value] == name) {
hash_table[hash_value] = EMPTY;
return true;
}
i++;
hash_value = linear_probe(hash_value, i);
if (i == MAX_SIZE) {
break;
}
}
return false;
}
int main() {
int hash_table[MAX_SIZE];
for (int i = 0; i < MAX_SIZE; i++) {
hash_table[i] = EMPTY;
}
string names[] = {"Alice", "Bob", "Charlie", "David", "Emma", "Frank", "Grace", "Hank", "Ivy", "Jack", "Kate", "Linda", "Mike", "Nancy", "Olivia", "Peter", "Queenie", "Rachel", "Steve", "Tom"};
for (int i = 0; i < 20; i++) {
insert(names[i], hash_table);
}
string name = "Kate";
if (search(name, hash_table)) {
cout << "Found " << name << " in the hash table." << endl;
if (remove(name, hash_table)) {
cout << "Removed " << name << " from the hash table." << endl;
} else {
cout << "Failed to remove " << name << " from the hash table." << endl;
}
} else {
cout << "Cannot find " << name << " in the hash table." << endl;
}
name = "Zoe";
if (!search(name, hash_table)) {
cout << "Cannot find " << name << " in the hash table." << endl;
insert(name, hash_table);
cout << "Inserted " << name << " into the hash table." << endl;
} else {
cout << name << " already exists in the hash table." << endl;
}
return 0;
}
```
运行结果如下:
```
Found Kate in the hash table.
Removed Kate from the hash table.
Cannot find Zoe in the hash table.
Inserted Zoe into the hash table.
```
希望能够帮助你!
阅读全文