当前位置:网站首页>7-3 构造散列表(PTA程序设计)
7-3 构造散列表(PTA程序设计)
2022-07-06 09:22:00 【编程林黛玉】
设散列表a[18],散列函数是hask(k)=k%17,用开放地址法解决冲突hi=(h0+di)%m。冲突时,使用增量序列di=5i。计算输入序列(值>=0)对应的散列地址值。(输入个数不会超过15个)
输入格式:
第一行为输入个数;
第二行为对应的输入值,用空格隔开。
输出格式:
按输入顺序输出其散列地址。每行对应一个值及其散列地址,中间用空格隔开(即pos前后均有一个空格)
输入样例:
5
141 73 95 112 56
输出样例:
141 pos: 5
73 pos: 10
95 pos: 15
112 pos: 2
56 pos: 7
代码(Python):
list1=[] #创建空列表,用来存放输入的数
list2=[] #构造散列表
for i in range(18): #如果这里不赋初值的话,列表为空,下面就会报错list index out of range
list2.append(0) #这里如果直接写list2[i]=0就会报错list assignment index out of range,一种情况是下标越界,另一种情况是列表为空
n=int(input()) #一共有几个数
#map()函数是将func作用于seq中的每一个元素,并将所有的调用的结果作为一个list返回。
#虽然结果作为list返回,但还是鼓励在外面加上list(),否则可能会有错误
list1=list(map(int,input().split())) #这一行是将一行以空格为分隔的数赋值给列表
for i in range(n): #使存在list1中的每个数按要求存入散列表list2
j=list1[i]%17 #散列函数是hask(k)=k%17
if list2[j]==0: #list为空,在这种情况下使用list[0]便会报错,所以上面就会先给list2赋值
list2[j]=list1[i] #即当散列表该位置还未存入list1中得到数时,使其存入散列表
else: #否则散列表中已经有了list1中的值,散列冲突
while(list2[j]!=0): #解决冲突hi=(h0+di)%m,冲突时,使用增量序列di=5i:就是相当于冲突时,存入下标+5后的位置
j=(j+5)%18 #这里一定要加5之后再除以18取余,否则会越界
list2[j]=list1[i] #在散列表中存数
for i in range(n): #开始输入,遍历list1中的数
for j in range(0,18): #遍历散列表中的数
if list2[j]!=0 and list1[i]==list2[j]: #按list1列表里的顺序输出散列表里不为0的值
print("{} pos: {}".format(list1[i],j)) #按要求输出
上面的程序给出了比较详细的注释,以便新手小白参考。程序的思路设计并不是最优的,是“笨办法”,欢迎各位大佬指正错误或者给出更优质的思路。
我是一只想成为鲲鹏的菜鸟,大家的鼓励是我前进的动力,欢迎大家点赞收藏评论哦!
边栏推荐
- 深度强化文献阅读系列(一):Courier routing and assignment for food delivery service using reinforcement learning
- 一段用蜂鸣器编的音乐(成都)
- 5月14日杂谈
- 【九阳神功】2020复旦大学应用统计真题+解析
- This time, thoroughly understand the MySQL index
- 1. Preliminary exercises of C language (1)
- 记一次猫舍由外到内的渗透撞库操作提取-flag
- A comprehensive summary of MySQL transactions and implementation principles, and no longer have to worry about interviews
- [graduation season · advanced technology Er] goodbye, my student days
- vector
猜你喜欢
扑克牌游戏程序——人机对抗
Caching mechanism of leveldb
受检异常和非受检异常的区别和理解
4. Branch statements and loop statements
MySQL事务及实现原理全面总结,再也不用担心面试
There is always one of the eight computer operations that you can't learn programming
QT meta object qmetaobject indexofslot and other functions to obtain class methods attention
The difference between cookies and sessions
C语言入门指南
Cookie和Session的区别
随机推荐
2. First knowledge of C language (2)
5. Download and use of MSDN
vector
Nuxtjs快速上手(Nuxt2)
Why use redis
Leetcode.3 无重复字符的最长子串——超过100%的解法
.Xmind文件如何上传金山文档共享在线编辑?
Redis实现分布式锁原理详解
5月27日杂谈
PriorityQueue (large root heap / small root heap /topk problem)
FAQs and answers to the imitation Niuke technology blog project (III)
稻 城 亚 丁
[modern Chinese history] Chapter V test
3.输入和输出函数(printf、scanf、getchar和putchar)
2. Preliminary exercises of C language (2)
[中国近代史] 第六章测验
There is always one of the eight computer operations that you can't learn programming
【九阳神功】2021复旦大学应用统计真题+解析
Questions and answers of "Fundamentals of RF circuits" in the first semester of the 22nd academic year of Xi'an University of Electronic Science and technology
深度强化文献阅读系列(一):Courier routing and assignment for food delivery service using reinforcement learning