帮我写一个代码:7-2 整型关键字的散列映射 分数 50 作者 DS课程组 单位 浙江大学 给定一系列整型关键字和素数P,用除留余数法定义的散列函数H(Key)=Key将关键字映射到长度为P的散列表中。用线性探测法解决冲突。 输入格式: 输入第一行首先给出两个正整数N(≤1000)和P(≥N的最小素数),分别为待插入的关键字总数、以及散列表的长度。第二行给出N个整型关键字。数字间以空格分隔。 输出格式: 在一行内输出每个整型关键字在散列表中的位置。数字间以空格分隔,但行末尾不得有多余空格。
时间: 2024-02-15 10:03:38 浏览: 79
数据结构实验报告--多关键字排序.doc
以下是Python3的代码实现:
```python
def find_pos(key, htable, p):
pos = key % p
i = 0
while htable[pos] != -1 and htable[pos] != key:
i += 1
pos = (key + i) % p
if htable[pos] == -1:
htable[pos] = key
return pos
n, p = map(int, input().split())
nums = list(map(int, input().split()))
htable = [-1] * p
for num in nums:
pos = find_pos(num, htable, p)
print(pos, end=' ')
```
思路解析:
首先读入输入的参数n和p,以及n个整型关键字nums。然后定义一个长度为p的散列表htable,初始化为-1。
接着,定义一个find_pos函数,用于寻找给定整数key在散列表htable中的位置。首先计算key在散列表中的初始位置pos,然后循环查找下一个空位置,直到找到空位置或者找到key为止。如果找到了空位置,则将key插入散列表;否则,说明key已经在散列表中存在,直接返回key的位置pos。
最后,遍历nums列表,依次将每个整数插入散列表htable,并输出其在散列表中的位置。
阅读全文