AcWing 840. 模拟散列表
原题链接
简单
作者:
术
,
2021-01-19 08:37:53
,
所有人可见
,
阅读 246
拉链法
#include <iostream>
#include <string.h>
using namespace std;
const int N=100003;
int ne[N],e[N],h[N];
int idx;//需要定义idx
void insert(int x){
int k=(x%N+N)%N;//保证负数的模是正确的
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
}
int find(int x){
int k=(x%N+N)%N;
int p=h[k];
while(p!=-1){
if(e[p]==x)
return 1;
p=ne[p];
}
return 0;
}
int main()
{
int n;
cin>>n;
memset(h,-1,sizeof(h));//每一位都是1 每个元素都是-1
while(n--){
char op[2];
int x;
scanf("%s%d",op,&x);
if(op[0]=='I'){
insert(x);
}
else
{
if(find(x)==1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
//cout << "Hello world!" << endl;
return 0;
}
开放寻址法
#include <iostream>
#include <string.h>
using namespace std;
const int N=200003;//两倍
int h[N];
int null=0x3f3f3f3f;
int find(int x){
int k=(x%N+N)%N;
while(h[k]!=x&&h[k]!=null){
k++;
if(k==N) k=0;
}
return k;
}
int main()
{
int n;
cin>>n;
memset(h,0x3f,sizeof(h));//每一位都是1 每个元素都是-1
while(n--){
char op[2];
int x;
scanf("%s%d",op,&x);
if(op[0]=='I'){
h[find(x)]=x;
}
else
{
if(h[find(x)]==x)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
//cout << "Hello world!" << endl;
//cout << "Hello world!" << endl;
return 0;
}