7-4 hash table search (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. 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 ！