用C语言编译以下代码设散列表a[18],散列函数是hask(k)=k%17,用开放地址法解决冲突hi=(h0+di)%m。冲突时采用平方探测法,使用增量序列di=i* i。计算输入序列(值>=0)对应的散列地址并进行查找,如果有此元素,则输出散列地址,如果无此元素,则输出not found。并输出查找次数(输入个数不会超过15个) 输入格式: 第一行为输入个数; 第二行为对应的输入值,用空格隔开; 第三行为需查找的元素,第1个为查找元素个数,后面为查找元素 输出格式: 第一行依次输出输入序列的散列地址,以一个空格隔开; 第二行开始输出查找元素的散列地址,每个元素占一行,每行对应一个值及其散列地址,中间用空格隔开(即pos前后均有一个空格),如果无此元素,则输出not found。
时间: 2023-12-24 11:02:50 浏览: 221
这是一道比较典型的散列表题目,可以使用C语言来实现。以下是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 18
int hash(int k) {
return k % 17;
}
int probe(int h, int i) {
return (h + i * i) % MAX_SIZE;
}
int search(int a[], int key) {
int i = 0;
int h = hash(key);
while (a[h] != -1 && a[h] != key && i < MAX_SIZE) {
h = probe(h, i);
i++;
}
if (a[h] == -1 || i >= MAX_SIZE) {
return -1; // not found
} else {
return h; // found
}
}
int main() {
int a[MAX_SIZE]; // 散列表
int input_count, search_count;
scanf("%d", &input_count);
for (int i = 0; i < MAX_SIZE; i++) {
a[i] = -1; // 初始化为-1
}
for (int i = 0; i < input_count; i++) {
int value;
scanf("%d", &value);
int h = hash(value);
int j = 0;
while (a[h] != -1 && j < MAX_SIZE) {
h = probe(h, j);
j++;
}
if (j >= MAX_SIZE) {
printf("散列表已满,插入失败\n");
exit(1);
}
a[h] = value;
}
for (int i = 0; i < MAX_SIZE; i++) {
printf("%d ", a[i]);
}
printf("\n");
scanf("%d", &search_count);
for (int i = 0; i < search_count; i++) {
int key;
scanf("%d", &key);
int pos = search(a, key);
if (pos == -1) {
printf("not found\n");
} else {
printf("%d %d\n", key, pos);
}
}
return 0;
}
```
上述代码中,`hash` 函数实现了散列函数 `hask(k)=k%17`;`probe` 函数实现了开放地址法中的探测函数 `hi=(h0+di)%m`,其中增量序列 `di=i* i`;`search` 函数实现了在散列表中查找元素的功能,采用平方探测法来解决冲突。
在 `main` 函数中,首先读入输入个数,并初始化散列表为 `-1`。然后按照散列函数和探测函数的规则将输入元素插入到散列表中。接着输出散列表中的元素,并读入需要查找的元素个数。最后按照查找元素的值来在散列表中进行查找,并输出散列地址或者 not found。
注意,对于本题中的平方探测法,需要注意探测序列不能超过散列表的容量 `MAX_SIZE`,否则会陷入死循环。因此,在插入新元素时,需要判断是否已经探测了 `MAX_SIZE` 次,如果是,则说明散列表已满,插入失败,程序应该终止运行。
阅读全文