采用哈希存储方式将一组关键字(105,97,28,52,37,22,16,90,45,79,59,76)存入长度为15的表中,构造一个哈希函数(要求发生冲突尽可能少),设计解决冲突的方法,并设计程序实现存储、查找功能。在上交的材料中写明哈希函数、解决冲突的办法。写出c语言代码
时间: 2023-09-23 11:12:13 浏览: 39
哈希函数:对关键字取余数,即 `hash(key) = key % 15`
解决冲突的方法:线性探测法,即发生冲突时,向后寻找下一个空闲位置进行存储,直到找到一个空闲位置或者探测完整个表。
C语言代码实现:
```c
#include <stdio.h>
#define SIZE 15
int hash(int key) {
return key % SIZE;
}
void insert(int table[], int key) {
int index = hash(key);
// 线性探测法解决冲突
while (table[index] != -1) {
index = (index + 1) % SIZE;
}
table[index] = key;
}
int search(int table[], int key) {
int index = hash(key);
// 线性探测法查找
while (table[index] != key) {
index = (index + 1) % SIZE;
if (table[index] == -1 || index == hash(key)) {
return -1; // 没有找到
}
}
return index; // 返回关键字在表中的位置
}
int main() {
int table[SIZE];
int i;
// 初始化表
for (i = 0; i < SIZE; i++) {
table[i] = -1;
}
// 将关键字插入表中
insert(table, 105);
insert(table, 97);
insert(table, 28);
insert(table, 52);
insert(table, 37);
insert(table, 22);
insert(table, 16);
insert(table, 90);
insert(table, 45);
insert(table, 79);
insert(table, 59);
insert(table, 76);
// 查找关键字
int index = search(table, 52);
if (index == -1) {
printf("未找到关键字\n");
} else {
printf("关键字 52 在表中的位置为 %d\n", index);
}
return 0;
}
```
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![ppt](https://img-home.csdnimg.cn/images/20210720083527.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)