采用哈希存储方式将一组关键字(105,97,28,52,37,22,16,90,45,79,59,76)存入长度为15的表中,构造一个哈希函数(要求发生冲突尽可能少),设计解决冲突的方法,并设计程序实现存储、查找功能。在上交的材料中写明哈希函数、解决冲突的办法。
时间: 2023-09-19 18:10:03 浏览: 19
哈希函数的设计可以采用取余法,即将关键字除以表长取余数,得到的余数就是该关键字应该存储的位置。
哈希函数:$h(key) = key \mod 15$
解决冲突的方法可以采用开放地址法的线性探测法,即如果发生冲突,就往后依次查找下一个空闲位置,直到找到一个空闲位置为止。
具体实现可以定义一个长度为15的数组来存储关键字,如果发生冲突就采用线性探测法查找下一个空闲位置,直到找到一个空闲位置为止。
以下是一个示例程序:
```c++
#include <iostream>
using namespace std;
const int size = 15;
int hashTable[size];
int hashFunc(int key) {
return key % size;
}
int insert(int key) {
int index = hashFunc(key);
while (hashTable[index] != 0) {
index = (index + 1) % size;
}
hashTable[index] = key;
return index;
}
int search(int key) {
int index = hashFunc(key);
while (hashTable[index] != key) {
index = (index + 1) % size;
if (hashTable[index] == 0) {
return -1;
}
}
return index;
}
int main() {
int keys[] = {105, 97, 28, 52, 37, 22, 16, 90, 45, 79, 59, 76};
for (int i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) {
insert(keys[i]);
}
int index = search(45);
if (index != -1) {
cout << "Found at index " << index << endl;
} else {
cout << "Not found" << endl;
}
return 0;
}
```
输出结果为:
```
Found at index 0
```