采用哈希存储方式将一组关键字(105,97,28,52,37,22,16,90,45,79,59,76)存入长度为15的表中,构造一个哈希函数(要求发生冲突尽可能少),设计解决冲突的方法,并设计程序实现存储、查找功能。在上交的材料中写明哈希函数、解决冲突的办法。
时间: 2023-09-23 10:11:16 浏览: 39
好的,让我来回答你的问题。针对你的问题,我会给出以下的回答:
首先,我们可以使用取余法作为哈希函数,即将关键字除以表长取余数作为存储位置。具体来说,哈希函数可以表示为:h(key) = key % 15。
其次,对于冲突的解决方法,我们可以采用开放定址法中的线性探测法,即当发生冲突时,在散列表中顺序查找下一个空闲位置进行存储。
具体实现上,我们可以定义一个长度为15的整型数组作为散列表,并在其中存储关键字。对于插入操作,我们首先使用哈希函数计算出关键字的存储位置,如果该位置已被占用,则使用线性探测法查找下一个空闲位置进行存储。对于查找操作,我们同样使用哈希函数计算出关键字的存储位置,并在散列表中查找该位置是否存储了对应的关键字,如果没有则继续向下查找直到找到对应的关键字或者查找到空闲位置。
以下是使用C++实现的代码示例:
```cpp
#include <iostream>
using namespace std;
// 哈希函数
int hashFunc(int key) {
return key % 15;
}
// 线性探测法解决冲突
int linearProbe(int hashTable[], int key) {
int pos = hashFunc(key); // 计算初始位置
while (hashTable[pos] != -1 && hashTable[pos] != key) {
pos = (pos + 1) % 15; // 查找下一个位置
}
return pos;
}
// 插入关键字
void insert(int hashTable[], int key) {
int pos = linearProbe(hashTable, key);
if (hashTable[pos] == -1) {
hashTable[pos] = key;
}
}
// 查找关键字
bool search(int hashTable[], int key) {
int pos = linearProbe(hashTable, key);
return (hashTable[pos] == key);
}
int main() {
int hashTable[15];
// 初始化哈希表
for (int i = 0; i < 15; i++) {
hashTable[i] = -1;
}
// 插入关键字
insert(hashTable, 105);
insert(hashTable, 97);
insert(hashTable, 28);
insert(hashTable, 52);
insert(hashTable, 37);
insert(hashTable, 22);
insert(hashTable, 16);
insert(hashTable, 90);
insert(hashTable, 45);
insert(hashTable, 79);
insert(hashTable, 59);
insert(hashTable, 76);
// 查找关键字
cout << search(hashTable, 52) << endl;
cout << search(hashTable, 100) << endl;
return 0;
}
```
在这个程序中,我们首先定义了一个长度为15的哈希表,并初始化所有元素为-1。然后,我们按照顺序插入了一组关键字,并分别查找了其中的某个关键字以及一个不存在的关键字。运行程序后,输出结果为:
```
1
0
```
其中,1表示查找成功,0表示查找失败。