基于上述LinkList类,建立一个采用链接法处理散列冲突的散列表,实现插入、 查找和删除操作。散列函数采用除法散列法,假定表中要存放500个元素,装载 因子约为3,选择合适的散列表大小。
时间: 2023-06-27 07:04:45 浏览: 92
数据结构实验:链地址法解决冲突构建散列表
首先,我们需要确定散列表的大小。装载因子为3,意味着散列表中元素的个数是散列表大小的3倍,即500*3=1500。因此,我们可以选择散列表大小为1500左右,为了方便,我们选择散列表大小为1499,一个质数。
接下来,我们需要定义散列函数。我们采用除法散列法,即将关键字除以散列表大小,得到的余数作为散列地址。
插入操作的实现:
```
void HashTable::insert(int key, int value) {
int index = hashFunction(key);
if (table[index] == nullptr) {
table[index] = new LinkList;
}
table[index]->insert(key, value);
}
```
查找操作的实现:
```
int HashTable::find(int key) {
int index = hashFunction(key);
if (table[index] == nullptr) {
return -1;
}
return table[index]->find(key);
}
```
删除操作的实现:
```
void HashTable::remove(int key) {
int index = hashFunction(key);
if (table[index] == nullptr) {
return;
}
table[index]->remove(key);
}
```
其中,`hashFunction`函数实现除法散列法:
```
int HashTable::hashFunction(int key) {
return key % size;
}
```
完整代码如下:
```
class HashTable {
private:
int size;
LinkList **table;
public:
HashTable(int tableSize) {
size = tableSize;
table = new LinkList *[size]();
}
~HashTable() {
for (int i = 0; i < size; ++i) {
if (table[i] != nullptr) {
delete table[i];
}
}
delete[] table;
}
int hashFunction(int key) {
return key % size;
}
void insert(int key, int value) {
int index = hashFunction(key);
if (table[index] == nullptr) {
table[index] = new LinkList;
}
table[index]->insert(key, value);
}
int find(int key) {
int index = hashFunction(key);
if (table[index] == nullptr) {
return -1;
}
return table[index]->find(key);
}
void remove(int key) {
int index = hashFunction(key);
if (table[index] == nullptr) {
return;
}
table[index]->remove(key);
}
};
```
阅读全文