整形关键字的平方探测法,用C语言写代码
时间: 2024-03-27 21:39:38 浏览: 12
平方探测法是一种哈希表的解决冲突的方法,其中一个常见的应用是在哈希表中使用。下面是使用C语言实现整型关键字的平方探测法的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TABLE_SIZE 11 // 哈希表的大小
#define EMPTY -1 // 哈希表中空位置的值
int hash_table[TABLE_SIZE]; // 哈希表的数组
int collisions = 0; // 记录冲突次数
// 哈希函数
int hash(int key) {
return key % TABLE_SIZE;
}
// 平方探测函数
int probe(int key, int i) {
return (hash(key) + i * i) % TABLE_SIZE;
}
// 插入关键字到哈希表中
void insert(int key) {
int i = 0;
int index = hash(key);
while (hash_table[index] != EMPTY) {
i++;
index = probe(key, i);
collisions++;
if (i == TABLE_SIZE) {
printf("哈希表已满,插入失败\n");
return;
}
}
hash_table[index] = key;
}
// 在哈希表中查找关键字
bool search(int key) {
int i = 0;
int index = hash(key);
while (hash_table[index] != key) {
i++;
index = probe(key, i);
if (hash_table[index] == EMPTY || i == TABLE_SIZE) {
return false;
}
}
return true;
}
// 主函数
int main() {
// 初始化哈希表
for (int i = 0; i < TABLE_SIZE; i++) {
hash_table[i] = EMPTY;
}
// 插入关键字
insert(12);
insert(44);
insert(13);
insert(88);
insert(23);
insert(94);
insert(11);
insert(39);
insert(20);
// 查找关键字
int key = 44;
if (search(key)) {
printf("%d 在哈希表中\n", key);
} else {
printf("%d 不在哈希表中\n", key);
}
// 输出哈希表中的元素及冲突次数
printf("哈希表中的元素为:\n");
for (int i = 0; i < TABLE_SIZE; i++) {
printf("%d ", hash_table[i]);
}
printf("\n冲突次数为:%d\n", collisions);
return 0;
}
```
上述代码中,我们定义了一个哈希表的大小为11,使用-1表示哈希表中的空位置。在哈希表中插入关键字时,我们使用平方探测函数进行解决冲突,直到找到空位置或者哈希表已满为止。在查找关键字时,我们也使用平方探测函数进行查找,直到找到关键字或者找到空位置或者已探测TABLE_SIZE次为止。最后,我们输出哈希表中的元素及冲突次数。