C语言实现利用散列表根据待输入的7个关键字{7,8,30,11,18,9,14},要求装填因子为0.7,采用除留余数法建立散列函数为:H(key) = (key *3) MOD 7,,采用线性探测法处理冲突,生成散列表,然后进行查找操作。
时间: 2024-03-17 22:47:44 浏览: 69
好的,以下是C语言实现利用散列表根据待输入的7个关键字{7,8,30,11,18,9,14},要求装填因子为0.7,采用除留余数法建立散列函数为:H(key) = (key *3) MOD 7, 采用线性探测法处理冲突,生成散列表的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10 // 散列表的最大长度
#define EMPTY -1 // 散列表中空位的标志
// 散列表结构体
typedef struct {
int key;
int value;
} HashTable;
// 初始化散列表
void init(HashTable hashtable[], int size) {
for (int i = 0; i < size; i++) {
hashtable[i].key = EMPTY;
}
}
// 散列函数
int hash(int key) {
return (key * 3) % MAX_SIZE;
}
// 插入关键字
void insert(HashTable hashtable[], int size, int key, int value) {
int index = hash(key);
while (hashtable[index].key != EMPTY) {
// 发生冲突,使用线性探测法
index = (index + 1) % size;
}
hashtable[index].key = key;
hashtable[index].value = value;
}
// 查找关键字
int search(HashTable hashtable[], int size, int key) {
int index = hash(key);
while (hashtable[index].key != key) {
if (hashtable[index].key == EMPTY) {
return -1; // 没有找到
}
index = (index + 1) % size;
}
return hashtable[index].value;
}
int main() {
int keys[] = {7, 8, 30, 11, 18, 9, 14};
int values[] = {0, 1, 2, 3, 4, 5, 6};
int size = 0.7 * MAX_SIZE;
HashTable hashtable[MAX_SIZE];
init(hashtable, MAX_SIZE);
// 插入关键字
for (int i = 0; i < sizeof(keys) / sizeof(int); i++) {
insert(hashtable, MAX_SIZE, keys[i], values[i]);
}
// 查找关键字
int key = 30;
int value = search(hashtable, MAX_SIZE, key);
if (value != -1) {
printf("找到了 %d,值是 %d。\n", key, value);
} else {
printf("没找到 %d。\n", key);
}
return 0;
}
```
以上代码中,我们定义了一个散列表结构体 `HashTable`,包含两个属性:`key` 表示关键字,`value` 表示关键字对应的值。在 `init` 函数中,将散列表中所有位置的 `key` 属性初始化为 `EMPTY`,表示该位置为空。
在 `hash` 函数中,使用除留余数法计算出关键字 `key` 的散列值,然后返回该值。
在 `insert` 函数中,先计算出关键字 `key` 的散列值 `index`,如果该位置已经被占用,则使用线性探测法查找下一个空位,直到找到空位为止。最后将关键字 `key` 和值 `value` 插入到散列表的 `index` 位置。
在 `search` 函数中,先计算出关键字 `key` 的散列值 `index`,如果该位置的 `key` 属性等于 `key`,则说明已经找到了对应的值,直接返回该位置的 `value` 属性。如果该位置的 `key` 属性等于 `EMPTY`,则说明关键字不存在,返回 `-1`。如果该位置的 `key` 属性不等于 `key`,则使用线性探测法查找下一个位置,直到找到关键字为止。
在 `main` 函数中,我们定义了一个待插入的关键字数组 `keys` 和对应的值数组 `values`,然后计算出散列表的大小(即最终插入的关键字数量),并初始化散列表。接着使用 `insert` 函数将关键字插入散列表,最后使用 `search` 函数查找关键字 `30` 的值,输出查找结果。
需要注意的是,以上代码中并没有进行错误处理,实际使用中需要考虑散列表已满、关键字已存在等异常情况。
阅读全文