AcWing 840. 模拟散列表
原题链接
简单
拉链法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200003;
struct Node {
int val;
Node* next;
Node(int _val): val(_val), next(NULL){}
}*h[N];
void add(int i, int x) {
Node *node = new Node(x);
node->next = h[i];
h[i] = node;
}
int _hash(int x) {
return (x % N + N) % N;
}
void insert(int x) {
int d = _hash(x);
add(d, x);
}
void query(int x) {
int d = _hash(x);
Node* p;
for(p = h[d]; p; p = p->next) {
if(p->val == x) {
printf("Yes\n");
return;
}
}
printf("No\n");
}
int main() {
int n;
scanf("%d", &n);
while(n --) {
char op[2];
int x;
scanf("%s%d", op, &x);
if(op[0] == 'I') {
insert(x);
} else if(op[0] == 'Q') {
query(x);
}
}
return 0;
}
开放定址法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200003, _null = 0x3f3f3f3f;
int h[N];
int find(int x) {
int d = (x % N + N) % N;
while(h[d] != _null && h[d] != x) {
d = (d + 1) % N;
}
return d;
}
void insert(int x) {
h[find(x)] = x;
}
void query(int x) {
if(x == h[find(x)]) {
printf("Yes\n");
} else {
printf("No\n");
}
}
int main() {
memset(h, 0x3f, sizeof h);
int n;
scanf("%d", &n);
while(n --) {
char op[2];
int x;
scanf("%s%d", op, &x);
if(op[0] == 'I') {
insert(x);
} else if(op[0] == 'Q') {
query(x);
}
}
return 0;
}