设散列表a[18],散列函数是hask(k)=k%17,用开放地址法解决冲突hi=(h0+di)%m。冲突时采用平方探测法,使用增量序列di=i* i。计算输入序列(值>=0)对应的散列地址并进行查找,如果有此元素,则输出散列地址,如果无此元素,则输出not found。并输出查找次数(输入个数不会超过15个) 输入格式: 第一行为输入个数; 第二行为对应的输入值,用空格隔开; 第三行为需查找的元素,第1个为查找元素个数,后面为查找元素 输出格式: 第一行依次输出输入序列的散列地址,以一个空格隔开; 第二行开始输出查找元素的散列地址,每个元素占一行,每行对应一个值及其散列地址,中间用空格隔开(即pos前后均有一个空格),如果无此元素,则输出not found。 输入样例: 5 141 73 95 112 56 7 5 73 95 141 112 56 18 输出样例: 5 6 10 11 9 5 not found,try 4 73 pos:6,try 2 95 pos:10,try 1 141 pos:5,try 1 112 pos:11,try 2 56 pos:9,try 3 18 not found,try 1
时间: 2024-02-13 13:59:56 浏览: 16
以下是该问题的完整代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int key;
int value;
int probeCount;
} HashItem;
typedef struct {
HashItem* array;
int size;
} HashTable;
void initHashTable(HashTable* table, int size) {
table->size = size;
table->array = (HashItem*)malloc(sizeof(HashItem) * size);
for (int i = 0; i < size; i++) {
table->array[i].key = -1;
table->array[i].value = -1;
table->array[i].probeCount = 0;
}
}
int hash(int key) {
return key % 17;
}
void insert(HashTable* table, int key, int value) {
int index = hash(key);
int i = 0;
while (table->array[index].key != -1 && table->array[index].key != key) {
i++;
index = (index + i * i) % table->size;
}
table->array[index].key = key;
table->array[index].value = value;
table->array[index].probeCount = i + 1;
}
int find(HashTable* table, int key) {
int index = hash(key);
int i = 0;
while (table->array[index].key != -1) {
if (table->array[index].key == key) {
return index;
}
i++;
index = (index + i * i) % table->size;
}
return -1;
}
int main() {
int n;
scanf("%d", &n);
int input[n];
for (int i = 0; i < n; i++) {
scanf("%d", &input[i]);
}
HashTable table;
initHashTable(&table, 18);
for (int i = 0; i < n; i++) {
int key = input[i];
int value = i;
insert(&table, key, value);
printf("%d ", hash(key));
}
printf("\n");
int m;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
int key;
scanf("%d", &key);
int index = find(&table, key);
if (index == -1) {
printf("%d not found,try ", key);
int j = 1;
while (1) {
int newIndex = (hash(key) + j * j) % table.size;
if (table.array[newIndex].key == -1) {
printf("%d\n", j);
break;
}
j++;
}
} else {
printf("%d %d\n", key, index);
}
}
return 0;
}
```
需要注意的是,对于查找失败的情况,我们需要输出“not found,try x”这样的信息,其中 x 表示最终找到空位置的探测次数。在代码中,我们使用了一个 while 循环来模拟这个过程。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![gz](https://img-home.csdnimg.cn/images/20210720083447.png)