1013: 哈希表（开放定址法处理冲突）
题目描述
采用除留余数法（H（key）=key %n）建立长度为n的哈希表，处理冲突用开放定址法的线性探测。
输入
第一行为哈希表的长度n； 第二行为关键字的个数； 第三行为关键字集合； 第三行为要查找的数据。
输出
如果查找成功，输出关键字所哈希表中的地址和比较次数；如果查找不成功，输出-1。
样例输入
13
11
16 74 60 43 54 90 46 31 29 88 77
16
样例输出
3,1
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 200003, null = 0x3f3f3f3f; int size; int h[N]; int cnt; int find(int u) { int t = u%size; cnt = 1; while(h[t]!=null&&h[t]!=u){ cnt++; t++; if(t == size) t = 0; } return t; } int main() { int n; memset(h,0x3f,sizeof h); cin>>size>>n; while(n--) { int tmp; cin>>tmp; h[find(tmp)] = tmp; } int f; cin>>f; if(h[find(f)] == null) cout<<"-1"; else cout<<find(f)<<","<<cnt; return 0; }
