用c语言实现:已知一维数组A中存放n个整型数,用除留余数法构造散列函数,用线性探测法处理冲突,将其存放在一维数组B中。
时间: 2024-02-09 15:09:27 浏览: 27
好的,下面是用 C 语言实现将一组数据存放到散列表中的代码,使用的是除留余数法和线性探测法:
```c
#include <stdio.h>
#include <stdlib.h>
#define M 11 // 散列表的大小
void hash_insert(int A[], int B[], int n, int m) {
int i, j, pos;
for (i = 0; i < m; i++) {
B[i] = -1; // -1 表示该位置为空
}
for (i = 0; i < n; i++) {
pos = A[i] % m; // 计算散列地址
if (B[pos] == -1) { // 如果该位置为空,则直接插入
B[pos] = A[i];
} else { // 否则,使用线性探测法查找下一个可用位置
j = (pos + 1) % m;
while (B[j] != -1) {
j = (j + 1) % m;
}
B[j] = A[i];
}
}
}
int main() {
int A[] = {12, 25, 36, 20, 30, 8, 42, 15, 23, 9};
int B[M];
int n = sizeof(A) / sizeof(A[0]);
hash_insert(A, B, n, M);
printf("Hash table contents:\n");
for (int i = 0; i < M; i++) {
if (B[i] != -1) {
printf("%d ", B[i]);
}
}
printf("\n");
return 0;
}
```
在这段代码中,我们首先定义了散列表的大小为 11,然后定义了一个 hash_insert() 函数,该函数接受四个参数:原始数据数组 A、散列表数组 B、原始数据数组 A 的大小 n,以及散列表数组 B 的大小 m。该函数首先将散列表数组 B 中所有位置初始化为 -1,表示该位置为空。然后,对于原始数据数组 A 中的每个元素,我们计算其散列地址 pos = A[i] % m。如果散列表数组 B 中该位置为空,则直接将元素插入该位置;否则,使用线性探测法查找下一个可用位置,并将元素插入该位置。
最后,我们在主函数中调用 hash_insert() 函数,并输出散列表数组 B 中的内容。注意,由于使用了线性探测法,因此散列表数组 B 中可能存在空位置,因此在输出内容时需要判断该位置是否为空。