设散列表a[18]，散列函数是hask(k)=k%17，用开放地址法解决冲突hi=(h0+di)%m。冲突时采用平方探测法，使用增量序列di=i* i。计算输入序列(值>=0)对应的散列地址并进行查找，如果有此元素，则输出散列地址，如果无此元素，则输出not found。并输出查找次数（输入个数不会超过15个）
输入格式:
第一行为输入个数；
第二行为对应的输入值，用空格隔开；
第三行为需查找的元素，第1个为查找元素个数，后面为查找元素
输出格式:
第一行依次输出输入序列的散列地址，以一个空格隔开；
第二行开始输出查找元素的散列地址，每个元素占一行，每行对应一个值及其散列地址，中间用空格隔开（即pos前后均有一个空格），如果无此元素，则输出not found。
输入样例:
5
141 73 95 112 56
7 5 73 95 141 112 56 18
输出样例:
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
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
#include <stdio.h>
int hs[2000], p, m, ct;
int hash(int t) { return t % p; }
int getPos(int t) {int key = hash(t), pos = key;int i;for (i = 0; i < p; i++) {pos = (key + i * i) % m;if (hs[pos] == -1 || hs[pos] == t) break;}ct = i + 1;return pos;
}
int main() {int n;scanf("%d", &n);int t;p = 17, m = 18;for (int i = 0; i < p; i++) hs[i] = -1;while (n--) {scanf("%d", &t);int pos = getPos(t);hs[pos] = t;printf("%d ", pos);}scanf("%d", &n);while (n--) {scanf("%d", &t);int pos = getPos(t);if (hs[pos] == t)printf("%d pos:%d,try %d\n", t, pos, ct);elseprintf("%d not found,try %d\n", t, ct);}return 0;
}