散列表线性探测法散列函数:除留余数法利用c++
时间: 2024-02-09 13:41:35 浏览: 31
散列表线性探测法是一种解决散列冲突的方法,其中散列函数是将键映射到散列表中的索引位置。除留余数法是一种常见的散列函数,它可以将键转换为一个整数,然后使用模运算将其映射到散列表中的索引位置。
以下是使用除留余数法实现散列表线性探测法的示例代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int SIZE = 10; //散列表大小
const int EMPTY = -1; //空位置标记
class HashTable {
private:
int* table; //散列表
int hash(int key); //散列函数
public:
HashTable();
void insert(int key);
void remove(int key);
void display();
};
//构造函数,初始化散列表
HashTable::HashTable() {
table = new int[SIZE];
memset(table, EMPTY, SIZE * sizeof(int));
}
//散列函数,除留余数法
int HashTable::hash(int key) {
return key % SIZE;
}
//插入键到散列表中
void HashTable::insert(int key) {
int index = hash(key); //计算散列值
int i = index;
do {
if (table[i] == EMPTY) { //如果位置为空
table[i] = key; //插入键
return;
}
i = (i + 1) % SIZE; //线性探测
} while (i != index); //回到起始位置,散列表已满
cout << "散列表已满,插入失败!" << endl;
}
//从散列表中删除键
void HashTable::remove(int key) {
int index = hash(key); //计算散列值
int i = index;
do {
if (table[i] == key) { //如果找到键
table[i] = EMPTY; //删除键
return;
}
i = (i + 1) % SIZE; //线性探测
} while (i != index); //回到起始位置,未找到键
cout << "未找到键,删除失败!" << endl;
}
//显示散列表中的键
void HashTable::display() {
for (int i = 0; i < SIZE; i++) {
if (table[i] != EMPTY) {
cout << table[i] << " ";
}
}
cout << endl;
}
int main() {
HashTable ht;
ht.insert(3);
ht.insert(7);
ht.insert(11);
ht.insert(22);
ht.insert(31);
ht.display();
ht.remove(11);
ht.remove(7);
ht.display();
ht.insert(33);
ht.insert(44);
ht.insert(55);
ht.insert(66);
ht.display();
return 0;
}
```
在这个示例中,我们使用除留余数法作为散列函数,将键映射到散列表中的索引位置。如果该位置已经被占用,则使用线性探测法寻找下一个可用位置。当散列表已满时,插入操作将失败。删除操作将从散列表中删除键,并将其位置标记为空。显示操作将输出散列表中的所有键。