7-3 构造散列表（PTA程序设计）

设散列表a[18]，散列函数是hask(k)=k%17，用开放地址法解决冲突hi=(h0+di)%m。冲突时，使用增量序列di=5i。计算输入序列(值>=0)对应的散列地址值。（输入个数不会超过15个）

输入格式:

第一行为输入个数；

第二行为对应的输入值，用空格隔开。

输出格式:

按输入顺序输出其散列地址。每行对应一个值及其散列地址，中间用空格隔开（即pos前后均有一个空格）

输入样例:

5
141 73 95 112 56

输出样例:

141 pos: 5
73 pos: 10
95 pos: 15
112 pos: 2
56 pos: 7

代码(Python):

list1=[]  #创建空列表，用来存放输入的数
list2=[]  #构造散列表
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(n):  #使存在list1中的每个数按要求存入散列表list2
    j=list1[i]%17  #散列函数是hask(k)=k%17
    if list2[j]==0:      #list为空，在这种情况下使用list[0]便会报错，所以上面就会先给list2赋值
        list2[j]=list1[i]  #即当散列表该位置还未存入list1中得到数时，使其存入散列表
    else:  #否则散列表中已经有了list1中的值，散列冲突
        while(list2[j]!=0):  #解决冲突hi=(h0+di)%m，冲突时，使用增量序列di=5i：就是相当于冲突时，存入下标+5后的位置
            j=(j+5)%18    #这里一定要加5之后再除以18取余，否则会越界
        list2[j]=list1[i]  #在散列表中存数
for i in range(n):  #开始输入，遍历list1中的数
    for j in range(0,18):  #遍历散列表中的数
        if list2[j]!=0 and list1[i]==list2[j]:  #按list1列表里的顺序输出散列表里不为0的值
            print("{} pos: {}".format(list1[i],j))  #按要求输出

上面的程序给出了比较详细的注释，以便新手小白参考。程序的思路设计并不是最优的，是“笨办法”，欢迎各位大佬指正错误或者给出更优质的思路。

我是一只想成为鲲鹏的菜鸟，大家的鼓励是我前进的动力，欢迎大家点赞收藏评论哦！