设散列表a[18],散列函数是hask(k)=k%17,用开放地址法解决冲突hi=(h0+di)%m。冲突时采用平方探测法,使用增量序列di=i* i。计算输入序列(值>=0)对应的散列地址并进行查找,如果有此元素,则输出散列地址,如果无此元素,则输出not found。并输出查找次数(输入个数不会超过15个) 输入格式: 第一行为输入个数; 第二行为对应的输入值,用空格隔开; 第三行为需查找的元素,第1个为查找元素个数,后面为查找元素 输出格式: 第一行依次输出输入序列的散列地址,以一个空格隔开; 第二行开始输出查找元素的散列地址,每个元素占一行,每行对应一个值及其散列地址,中间用空格隔开(即pos前后均有一个空格),如果无此元素,则输出not found。
时间: 2024-02-13 10:59:53 浏览: 18
这是一个比较复杂的问题,需要用到一些算法和数据结构知识,我会尽力解答。
首先,我们需要定义一个散列表结构体,用来存储数据和一些相关信息:
```c
typedef struct
{
int key; // 关键字
int value; // 数据
int probeCount; // 探测次数
} HashItem;
typedef struct
{
HashItem *array; // 数组指针
int size; // 数组大小
} HashTable;
```
然后,我们需要实现一些基本操作,如初始化散列表、插入元素、查找元素等:
```c
// 初始化散列表
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;
}
```
最后,我们需要根据输入序列构建散列表,并输出查找结果:
```c
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("not found\n");
}
else
{
printf("%d %d\n", index, table.array[index].probeCount);
}
}
return 0;
}
```
这样,我们就完成了这个问题的求解。