开放寻址法
#include <iostream> #include <cstring> #include <cstdio> using namespace std; const int N = 200010,null = 0x3f3f3f3f; int h[N]; int find(int x) { int t = (x % N + N) % N; while(h[t] != null && h[t] != x) { t ++; if(t == N) t = 0; } return t; } int main(void) { char op[2]; int n,x; memset(h,0x3f,sizeof h); scanf("%d",&n); while(n --) { scanf("%s%d",&op,&x); if(*op == 'I') { h[find(x)] = x; } else { if(h[find(x)] == x) printf("Yes\n"); else printf("No\n"); } } return 0; }
以取余完的地址存入,如果冲突了就往后顺延.
memset以字节存,int是4字节,所以是存入4个0x3f.
拉链法
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 100003; int h[N],e[N],ne[N]; int idx; void insert(int x) { int k = (x % N + N )% N; e[idx] = x; ne[idx] = h[k]; h[k] = idx ++; } bool find(int x) { int k = (x % N + N) % N; for(int i = h[k]; i != -1 ; i = ne[i]) { if(e[i] == x) return true; } return false; } int main(void) { memset(h,-1,sizeof h); int n,x; scanf("%d",&n); char op[2]; while(n --) { scanf("%s%d",op,&x); if(*op == 'I') { insert(x); } else { if(find(x) == true) printf("Yes\n"); else printf("No\n"); } } return 0; }
用链式向前星存,数组模拟链表,如果取余完的地址冲突了,就在表头插入.
拉链法和开放寻址法都行.看个人喜好选择就行.