当前位置:网站首页>7-3 construction hash table (PTA program design)
7-3 construction hash table (PTA program design)
2022-07-06 13:54:00 【Programming Lindaiyu】
Set hash table a[18], The hash function is hask(k)=k%17, Use the open address method to solve conflicts hi=(h0+di)%m. When the conflict , Use incremental sequence di=5i. Calculate the input sequence ( value >=0) Corresponding hash address value .( The number of entries will not exceed 15 individual )
Input format :
The first line is to input the number ;
The input value corresponding to the second line , Space off .
Output format :
Output its hash address in the order of input . Each row corresponds to a value and its hash address , Space separates the middle ( namely pos There is a space before and after )
sample input :
5
141 73 95 112 56
sample output :
141 pos: 5
73 pos: 10
95 pos: 15
112 pos: 2
56 pos: 7
Code (Python):
list1=[] # Create an empty list , Used to store the input number
list2=[] # Construct hash tables
for i in range(18): # If there is no initial value assigned here , The list is empty. , An error will be reported below list index out of range
list2.append(0) # If you write directly here list2[i]=0 You're going to report a mistake list assignment index out of range, In one case, the subscript is out of bounds , Another case is that the list is empty
n=int(input()) # How many numbers are there
#map() The function is to func Act on seq Every element in , And take the results of all calls as a list return .
# Although the result is list return , But it is still encouraged to add list(), Otherwise, there may be errors
list1=list(map(int,input().split())) # This row assigns a row of numbers separated by spaces to the list
for i in range(n): # Make exist list1 Each number in is stored in the hash table as required list2
j=list1[i]%17 # The hash function is hask(k)=k%17
if list2[j]==0: #list It's empty , Use in this case list[0] It's a mistake , So the top will give list2 assignment
list2[j]=list1[i] # That is, when the position of the hash table has not been saved list1 Get the number of hours , Save it in the hash table
else: # Otherwise, there are already in the hash table list1 The value in , Hash collision
while(list2[j]!=0): # Resolve conflicts hi=(h0+di)%m, When the conflict , Use incremental sequence di=5i: It is equivalent to conflict , Deposit subscript +5 The back position
j=(j+5)%18 # We must add 5 Then divide by 18 Remainder , Otherwise you cross the line
list2[j]=list1[i] # Save data in hash table
for i in range(n): # Start input , Traverse list1 The number in
for j in range(0,18): # Traverse the number in the hash table
if list2[j]!=0 and list1[i]==list2[j]: # Press list1 The order output hash table in the list is not 0 Value
print("{} pos: {}".format(list1[i],j)) # Output as required
The above program gives more detailed comments , For novice Xiaobai's reference . The thinking design of the program is not optimal , yes “ Stupid way ”, You are welcome to correct your mistakes or give better ideas .
I am a rookie who wants to be Kunpeng , Everyone's encouragement is my driving force , Welcome to like collection comments !
边栏推荐
- (original) make an electronic clock with LCD1602 display to display the current time on the LCD. The display format is "hour: minute: Second: second". There are four function keys K1 ~ K4, and the fun
- C language Getting Started Guide
- A piece of music composed by buzzer (Chengdu)
- UGUI—Text
- SRC挖掘思路及方法
- 稻 城 亚 丁
- 渗透测试学习与实战阶段分析
- .Xmind文件如何上传金山文档共享在线编辑?
- Canvas foundation 2 - arc - draw arc
- canvas基础1 - 画直线(通俗易懂)
猜你喜欢
仿牛客技术博客项目常见问题及解答(三)
Strengthen basic learning records
一段用蜂鸣器编的音乐(成都)
Nuxtjs quick start (nuxt2)
仿牛客技术博客项目常见问题及解答(一)
Have you encountered ABA problems? Let's talk about the following in detail, how to avoid ABA problems
[hand tearing code] single case mode and producer / consumer mode
[dark horse morning post] Shanghai Municipal Bureau of supervision responded that Zhong Xue had a high fever and did not melt; Michael admitted that two batches of pure milk were unqualified; Wechat i
ABA问题遇到过吗,详细说以下,如何避免ABA问题
[during the interview] - how can I explain the mechanism of TCP to achieve reliable transmission
随机推荐
FAQs and answers to the imitation Niuke technology blog project (II)
【educoder数据库实验 索引】
Mixlab unbounded community white paper officially released
ABA问题遇到过吗,详细说以下,如何避免ABA问题
[the Nine Yang Manual] 2016 Fudan University Applied Statistics real problem + analysis
简述xhr -xhr的基本使用
SRC挖掘思路及方法
[modern Chinese history] Chapter 9 test
7-14 错误票据(PTA程序设计)
Difference and understanding between detected and non detected anomalies
[during the interview] - how can I explain the mechanism of TCP to achieve reliable transmission
Package bedding of components
Principles, advantages and disadvantages of two persistence mechanisms RDB and AOF of redis
canvas基础2 - arc - 画弧线
1143_ SiCp learning notes_ Tree recursion
深度强化文献阅读系列(一):Courier routing and assignment for food delivery service using reinforcement learning
[data processing of numpy and pytoch]
实验八 异常处理
Miscellaneous talk on May 27
[the Nine Yang Manual] 2022 Fudan University Applied Statistics real problem + analysis