采用平方探测法处理冲突,C语言
时间: 2023-08-23 14:19:59 浏览: 42
好的,下面是使用C语言实现哈希表和平方探测法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10
int hash(int key) {
return key % SIZE;
}
void insert(int table[], int key) {
int index = hash(key);
int i = 1;
while (table[index] != -1) {
index = (index + i*i) % SIZE;
i++;
}
table[index] = key;
}
int search(int table[], int key) {
int index = hash(key);
int i = 1;
while (table[index] != -1) {
if (table[index] == key) {
return 1;
}
index = (index + i*i) % SIZE;
i++;
}
return 0;
}
int main() {
int table[SIZE];
int i;
for (i = 0; i < SIZE; i++) {
table[i] = -1;
}
insert(table, 5);
insert(table, 15);
insert(table, 25);
printf("Search 5: %d\n", search(table, 5));
printf("Search 15: %d\n", search(table, 15));
printf("Search 25: %d\n", search(table, 25));
printf("Search 35: %d\n", search(table, 35));
return 0;
}
```
在这个代码中,我们首先定义了一个哈希函数hash,然后定义了insert和search函数来处理插入和搜索操作。在insert函数中,我们使用平方探测法来处理冲突,当找到一个被占用的位置时,我们将下标增加i*i,其中i表示探测的次数。在search函数中,我们也使用平方探测法来查找关键字。
在main函数中,我们创建一个大小为SIZE的哈希表,并初始化所有元素为-1。然后插入一些关键字,并搜索它们。输出结果为1表示找到了,为0表示没有找到。
希望这个代码对你有帮助!