模拟散列表

拉链法

#include<iostream>
#include<cstring>
using namespace std;
const int N = 100003;//N的值为质数,而且离2的幂越远越好,这样不容易冲突
int h[N], e[N], ne[N], 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;
    for(int i = h[k]; i != -1; i = ne[i])
    {
        if(e[i] == x)return true;
    }
    return false;
}
int main()
{
    memset(h, -1, sizeof h);
    int n;
    cin >> n;
    while(n --)
    {
        char op[2];
        int x;
        cin >> op >> x;
        if(*op == 'I')insert(x);
        else {
            if(find(x))puts("Yes");
            else puts("No");
        }
    }
}

开放寻址法

#include<iostream>
#include<cstring>
using namespace std;
const int N = 200003, nu = 0x3f3f3f3f;//N一般是题目给的2~5倍。
int h[N];
int find(int x)
{
    int k = (x % N + N) % N;
    while(h[k] != nu && h[k] != x)
    {
        k ++;
        if(k == N)k = 0;
    }
    return k;
}
int main()
{
    int n;
    memset(h, 0x3f, sizeof h);
    cin >> n;
   
    while(n --)
    {
        char op[2];
        int x;
        cin >> op >> x;
        int k = find(x);
        if(*op == 'I')
        {
            h[k] = x;
        }
        else if(*op == 'Q'){
            if(h[k] == nu)puts("No");
            
            else puts("Yes");
        }
    }
}
数据结构 文章被收录于专栏

数据结构

全部评论

相关推荐

面向对象的火龙果很爱...:去吃一顿炸鸡就走
点赞 评论 收藏
分享
05-29 22:11
门头沟学院 Java
Elastic90:抛开学历造假不谈,这公司的招聘需求也挺怪的,Java开发还要求你有图文识别、移动端开发和c++的经验,有点逆天了。
点赞 评论 收藏
分享
05-12 17:00
门头沟学院 Java
king122:你的项目描述至少要分点呀,要实习的话,你的描述可以使用什么技术,实现了什么难点,达成了哪些数字指标,这个数字指标尽量是真实的,这样面试应该会多很多,就这样自己包装一下,包装不好可以找我,我有几个大厂最近做过的实习项目也可以包装一下
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务