当前位置:网站首页>7-4 hash table search (PTA program design)
7-4 hash table search (PTA program design)
2022-07-06 13:56: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. Square detection method is used in case of conflict , Use incremental sequence di=i* i. Calculate the input sequence ( value >=0) Corresponding hash address and search , If there is this element , Then output hash address , If there is no such element , The output not found. And output the search times ( 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 ;
The third line is the element to be found , The first 1 Number is the number of search elements , The following is the search element
Output format :
The first row outputs the hash address of the input sequence in turn , Separated by a space ;
The second line begins to output the hash address of the search element , Each element occupies one line , Each row corresponds to a value and its hash address , Space separates the middle ( namely pos There is a space before and after ), If there is no such element , The output not found.
sample input :
5
141 73 95 112 56
7 5 73 95 141 112 56 18
sample output :
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
Code (Python):
list1=[] # Saved number
list2=[] # Save with hash table list1 The number in
list3=[] # Looking for elements , The first 1 Number is the number of search elements , The following is the search element , That is, input the third line of data in the sample
ct=[] # Deposit try The number of times
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(0,n): # Make exist list1 Each number in is stored in the hash table as required list2
d=1 # Square detection method is used in case of conflict , Use incremental sequence di=i*i, send d At the beginning of 1
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
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
ct.append(d) #try Once , take try Value added to the list ct in
else: # Otherwise, there are already in the hash table list1 The value in , Hash collision
while(list2[j]!=0): # Use the open address method to solve conflicts hi=(h0+di)%m. Square detection method is used in case of conflict , Use incremental sequence di=i*i
j=(list1[i]%17+d*d)%18 # Use the address before the conflict plus the increment to get the remainder 18, Otherwise, it will cross the border
d+=1 #try It's worth adding 1
ct.append(d) # take try Value added to the list ct in
list2[j]=list1[i] # take list1 The value in the list is stored in the hash table
print(j,end=' ') # Output the hash address of the input sequence in turn , That is, the number of the first line of output
print() # Output carriage return
list3=list(map(int,input().split())) # Looking for elements , The first 1 Number is the number of search elements , The following is the search element
for i in range(1,len(list3)): # In fact, it is from the first 2 Elements start with , But the subscript is 1
if list3[i] in list1: # First, check whether the number you want to find is in list1 in
pos1=list1.index(list3[i]) # This number is in the list 1 Subscript in , The purpose is to output with its subscript ct In the list try frequency
pos2=list2.index(list3[i]) # This number is in the list 2 Subscript in , The purpose is to output its position
print("{} pos:{},try {}".format(list3[i],pos2,ct[pos1])) # Output as required
else: # Otherwise, the number you are looking for is not list1 in
m=list3[i]%17 # But also find it try frequency
d=1 #try The number starts with 1
while list2[m]!=0: # If it should have been list2 Position in is not 0 Words , It indicates that it may encounter hash conflicts , Move on to the next place it should be
m=(list3[i]%17+d*d)%18 # This must be divided by 18 Remainder , Otherwise you cross the line
d+=1 # Every judgment d Add 1
print("{} not found,try {}".format(list3[i],d)) # Output as required
Ideas : This question can be divided into two steps , First step , Store the data in the hash table ; The second step , Start to find the specified element in the hash table and output the address and number of attempts in the hash table . One difficulty here is the number of attempts , You can read my notes above to understand .
The above program gives more detailed comments , For novice Xiaobai's reference . The idea of program design or code implementation is not optimal , 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 !
边栏推荐
- Canvas foundation 1 - draw a straight line (easy to understand)
- Difference and understanding between detected and non detected anomalies
- 【MySQL数据库的学习】
- Brief introduction to XHR - basic use of XHR
- [the Nine Yang Manual] 2019 Fudan University Applied Statistics real problem + analysis
- Implementation principle of automatic capacity expansion mechanism of ArrayList
- 3. Input and output functions (printf, scanf, getchar and putchar)
- 1143_ SiCp learning notes_ Tree recursion
- Renforcer les dossiers de base de l'apprentissage
- 强化学习系列(一):基本原理和概念
猜你喜欢
Strengthen basic learning records
Principles, advantages and disadvantages of two persistence mechanisms RDB and AOF of redis
FAQs and answers to the imitation Niuke technology blog project (III)
2022泰迪杯数据挖掘挑战赛C题思路及赛后总结
附加简化版示例数据库到SqlServer数据库实例中
仿牛客技术博客项目常见问题及解答(三)
1. First knowledge of C language (1)
这次,彻底搞清楚MySQL索引
Poker game program - man machine confrontation
Callback function ----------- callback
随机推荐
强化学习基础记录
HackMyvm靶机系列(5)-warez
Intensive literature reading series (I): Courier routing and assignment for food delivery service using reinforcement learning
7-4 散列表查找(PTA程序设计)
[the Nine Yang Manual] 2021 Fudan University Applied Statistics real problem + analysis
Simply understand the promise of ES6
抽象类和接口的区别
SRC mining ideas and methods
【educoder数据库实验 索引】
[during the interview] - how can I explain the mechanism of TCP to achieve reliable transmission
实验七 常用类的使用
Programme de jeu de cartes - confrontation homme - machine
Beautified table style
扑克牌游戏程序——人机对抗
7-14 错误票据(PTA程序设计)
MySQL lock summary (comprehensive and concise + graphic explanation)
Why use redis
3. Input and output functions (printf, scanf, getchar and putchar)
[the Nine Yang Manual] 2017 Fudan University Applied Statistics real problem + analysis
. Net6: develop modern 3D industrial software based on WPF (2)