AcWing 840. 模拟散列表
原题链接
简单
作者:
时过境迁
,
2021-02-03 19:43:00
,
所有人可见
,
阅读 220
#include <iostream>
#include <cstring>
using namespace std;
//拉链方法,数据结构:邻接表
//即把本来放置在该位置的数用链表链起来
const int N = 100003; //散列函数的常数者最好为素数
//for(int i = 100000; ; i ++)
// {
// bool exist = true;
// for(int j = 2; j * j <= i; ++j)
// {
// if(i % j == 0)
// exist = false;
// }
// if(exist)
// {
// cout<<i<<endl;
// break;
// }
// }
int h[N], e[N], ne[N], idx;
int n;
void insert(int x)
{
int k = (x%N + N)%N; //本来只需要x%N即可,但是考虑到负数,故为此公式
//采用头插法将x插入到第k个链表中
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++;
}
bool query(int x)
{
//找到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()
{
cin>>n;
memset(h, -1, sizeof(h)); //初始化邻接表
while(n--)
{
char op;
int x;
cin>>op>>x;
if(op == 'I')
insert(x);
else
{
if(query(x))
puts("Yes");
else
puts("No");
}
}
return 0;
}
#include <iostream>
#include <cstring>
using namespace std;
//蹲坑法,数据结构:蹲坑数组(自己瞎起的...)
//即把本来放置在该位置的数 放在其后面空着的位置
const int null = 0x3f3f3f3f; //为了看当前位置是否为空,该值时x不会出现的值
const int N = 100003; //散列函数的常数者最好为素数
//for(int i = 100000; ; i ++)
// {
// bool exist = true;
// for(int j = 2; j * j <= i; ++j)
// {
// if(i % j == 0)
// exist = false;
// }
// if(exist)
// {
// cout<<i<<endl;
// break;
// }
// }
int h[N];
int n;
void insert(int x)
{
int k = (x%N + N)%N; //本来只需要x%N即可,但是考虑到负数,故为此公式
while(h[k] != null)
{
if(k == N)
k = 0;
else
k++;
}
h[k] = x;
}
bool query(int x)
{
//找到x应该所在哪个位置中
int k = (x%N + N)%N;
while(h[k] != null)
{
if(h[k] == x)
return true;
if(k == N)
k = 0;
else
k++;
}
return false;
}
int main()
{
cin>>n;
memset(h, 0x3f, sizeof(h)); //初始化蹲坑数组
while(n--)
{
char op;
int x;
cin>>op>>x;
if(op == 'I')
insert(x);
else
{
if(query(x))
puts("Yes");
else
puts("No");
}
}
return 0;
}