7-3 construction hash table (PTA program design)

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 ！