用数据结构编写代码分别写出在散列表中插入和删除关键字为K的一个记录的算法,设散列函数为H,解决冲突的方法为链地址法。
时间: 2024-02-16 22:59:49 浏览: 171
以下是使用C++语言编写的代码:
```c++
#include <iostream>
#include <list>
using namespace std;
class HashTable {
private:
int size; // 散列表的大小
list<pair<int, int>>* table; // 散列表的数组,每个元素是一个链表
int hash_func(int key) { // 散列函数,使用简单的取模运算
return key % size;
}
public:
HashTable(int s = 100) : size(s) {
table = new list<pair<int, int>>[size];
}
~HashTable() {
delete[] table;
}
bool insert(int key, int value) { // 插入关键字为key,值为value的记录
int h = hash_func(key);
for (auto& p : table[h]) {
if (p.first == key) {
return false; // 已经存在相同的关键字,插入失败
}
}
table[h].push_front(make_pair(key, value)); // 在链表头部插入新记录
return true;
}
bool remove(int key) { // 删除关键字为key的记录
int h = hash_func(key);
for (auto& p : table[h]) {
if (p.first == key) {
table[h].remove(p); // 从链表中删除该记录
return true;
}
}
return false; // 没有找到关键字为key的记录,删除失败
}
};
```
这里使用了STL中的`list`容器来实现链表,每个散列地址对应的元素是一个链表,可以在链表中插入或删除记录。在插入记录时,需要先遍历链表,检查是否已经存在相同的关键字,如果存在则插入失败。在删除记录时,需要遍历链表,找到要删除的记录并从链表中删除。
阅读全文