AcWing 840. 模拟散列表(开放寻址法详细注释版)
原题链接
简单
作者:
我不不不不秃头
,
2023-11-02 11:09:01
,
所有人可见
,
阅读 47
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2000003,null=0x3f3f3f3f;
//null表示的是一个不太可能存在的数
int h[N];
int find(int x){
int t = (x%N+N)%N;
//加上一个N是为了防止是负数
while(h[t]!=null&&h[t]!=x){
//如果存在冲突,则t+1;寻找下一个非空坐标
t++;
if(t==N) t=0;//如果搜索超范围的话,从头开始寻找
}
return t;//返回的t代表着插入数映射哈希表的下标
}
int main()
{
memset(h,0x3f,sizeof h);
//将h中所有的字节都设置为03xf,03xf对应的是“?”,不会引起冲突
int n;
scanf("%d",&n);
while(n--)
{
char op[2];
int x;
scanf("%s%d",op,&x);
if(*op == 'I') h[find(x)] = x;//将x插入到它的对应下表
else{
if(h[find(x)]==null) puts("No");//如果对应的为空的话,说明元素不在
else puts("Yes");
}
}
return 0;
}