创建哈希表,设定哈希表为H(k)=k mod m,输入关键字序列,将其依此存入哈希表中,分别采用线性探测法和平方探测法处理冲突
时间: 2023-08-15 16:21:28 浏览: 119
这里提供一个C语言的简单实现,使用线性探测法和平方探测法处理冲突:
```c
#include <stdio.h>
#include <stdlib.h>
#define m 11 // 哈希表大小
#define NULLKEY -32768 // 哈希表空位置的标志
int hash(int key) {
return key % m;
}
int linear_probe(int H[], int key) {
int index = hash(key);
int i = 0;
while (H[(index + i) % m] != NULLKEY) {
i++;
}
return (index + i) % m;
}
int quadratic_probe(int H[], int key) {
int index = hash(key);
int i = 0;
while (H[(index + i*i) % m] != NULLKEY) {
i++;
}
return (index + i*i) % m;
}
void insert_linear(int H[], int key) {
int index = hash(key);
if (H[index] != NULLKEY) {
index = linear_probe(H, key);
}
H[index] = key;
}
void insert_quadratic(int H[], int key) {
int index = hash(key);
if (H[index] != NULLKEY) {
index = quadratic_probe(H, key);
}
H[index] = key;
}
void display(int H[]) {
for (int i = 0; i < m; i++) {
printf("%d ", H[i]);
}
printf("\n");
}
int main() {
int H[m];
int keys[] = { 12, 44, 13, 88, 23, 94, 11, 39, 20, 16 };
for (int i = 0; i < m; i++) {
H[i] = NULLKEY;
}
printf("Insert using linear probing:\n");
for (int i = 0; i < 10; i++) {
insert_linear(H, keys[i]);
}
display(H);
for (int i = 0; i < m; i++) {
H[i] = NULLKEY;
}
printf("Insert using quadratic probing:\n");
for (int i = 0; i < 10; i++) {
insert_quadratic(H, keys[i]);
}
display(H);
return 0;
}
```
上述代码中,`hash()`函数为哈希函数,`linear_probe()`函数和`quadratic_probe()`函数为线性探测法和平方探测法的探测函数,`insert_linear()`函数和`insert_quadratic()`函数为插入操作,`display()`函数用于显示哈希表中的元素。程序中使用了一个数组`keys`来存储关键字序列。运行程序后,会输出使用线性探测法和平方探测法插入后的哈希表。
阅读全文