当前位置:网站首页>7-4 散列表查找(PTA程序设计)
7-4 散列表查找(PTA程序设计)
2022-07-06 09:22:00 【编程林黛玉】
设散列表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
代码(Python):
list1=[] #存好的数
list2=[] #用散列表存list1中的数
list3=[] #查找的元素,第1个为查找元素个数,后面为查找元素,即输入样例中的第三行数据
ct=[] #存放try的次数
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(0,n): #使存在list1中的每个数按要求存入散列表list2
d=1 #冲突时采用平方探测法,使用增量序列di=i*i,使d一开始为1
j=list1[i]%17 #散列函数是hask(k)=k%17
if list2[j]==0: #list为空,在这种情况下使用list[0]便会报错
list2[j]=list1[i] #即当散列表该位置还未存入list1中得到数时,使其存入散列表
ct.append(d) #try了一次的情况,将try值加入列表ct中
else: #否则散列表中已经有了list1中的值,散列冲突
while(list2[j]!=0): #用开放地址法解决冲突hi=(h0+di)%m。冲突时采用平方探测法,使用增量序列di=i*i
j=(list1[i]%17+d*d)%18 #用冲突前的地址加上增量再取余18,否则将会越界
d+=1 #try值加1
ct.append(d) #将try值加入列表ct中
list2[j]=list1[i] #将list1列表中的该值存入散列表中
print(j,end=' ') #依次输出输入序列的散列地址,即输出的第一行数
print() #输出回车
list3=list(map(int,input().split())) #查找的元素,第1个为查找元素个数,后面为查找元素
for i in range(1,len(list3)): #其实是从第2个元素开始的,但下标为1
if list3[i] in list1: #先看要找的数在不在list1中
pos1=list1.index(list3[i]) #该数在列表1中的下标,目的是用其下标输出ct列表中的try次数
pos2=list2.index(list3[i]) #该数在列表2中的下标,目的是输出其位置
print("{} pos:{},try {}".format(list3[i],pos2,ct[pos1])) #按要求输出
else: #否则要找的数不在list1中
m=list3[i]%17 #但也要找其try次数
d=1 #try次数开始时为1
while list2[m]!=0: #如果其本来应该在list2中的位置不为0的话,说明它可能遇到散列冲突,继续向下一个它应该在的位置
m=(list3[i]%17+d*d)%18 #这里一定要除以18取余,否则会越界
d+=1 #每判断一次d加1
print("{} not found,try {}".format(list3[i],d)) #按要求输出
思路:该题可分为两个步骤,第一步,将数据存入散列表中;第二步,开始在散列表中查找指定元素并输出在散列表里的地址和尝试次数。这里的一个难点就是尝试次数,大家可以看我上面的注释以加以理解。
上面的程序给出了比较详细的注释,以便新手小白参考。程序的思路设计或者代码实现并不是最优的,欢迎各位大佬指正错误或者给出更优质的思路。
我是一只想成为鲲鹏的菜鸟,大家的鼓励是我前进的动力,欢迎大家点赞收藏评论哦!
边栏推荐
- 1. First knowledge of C language (1)
- 4.二分查找
- 仿牛客技术博客项目常见问题及解答(三)
- Redis cache obsolescence strategy
- 透彻理解LRU算法——详解力扣146题及Redis中LRU缓存淘汰
- 使用Spacedesk实现局域网内任意设备作为电脑拓展屏
- 2022泰迪杯数据挖掘挑战赛C题思路及赛后总结
- 简单理解ES6的Promise
- 3. C language uses algebraic cofactor to calculate determinant
- FAQs and answers to the imitation Niuke technology blog project (II)
猜你喜欢
2. C language matrix multiplication
C language Getting Started Guide
9. Pointer (upper)
(ultra detailed onenet TCP protocol access) arduino+esp8266-01s access to the Internet of things platform, upload real-time data collection /tcp transparent transmission (and how to obtain and write L
. Net6: develop modern 3D industrial software based on WPF (2)
Write a program to simulate the traffic lights in real life.
2. Preliminary exercises of C language (2)
View UI plus released version 1.3.0, adding space and $imagepreview components
5.MSDN的下载和使用
fianl、finally、finalize三者的区别
随机推荐
MySQL锁总结(全面简洁 + 图文详解)
vector
2.初识C语言(2)
受检异常和非受检异常的区别和理解
C language to achieve mine sweeping game (full version)
Safe driving skills on ice and snow roads
仿牛客技术博客项目常见问题及解答(三)
仿牛客技术博客项目常见问题及解答(二)
Wei Pai: the product is applauded, but why is the sales volume still frustrated
【九阳神功】2022复旦大学应用统计真题+解析
Cookie和Session的区别
杂谈0516
5.函数递归练习
ABA问题遇到过吗,详细说以下,如何避免ABA问题
C language Getting Started Guide
5. Function recursion exercise
Service ability of Hongmeng harmonyos learning notes to realize cross end communication
Comparison between FileInputStream and bufferedinputstream
View UI plus releases version 1.1.0, supports SSR, supports nuxt, and adds TS declaration files
string