C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
// //拉链法
// const int N=1e5+3;// 取大于1e5的第一个质数，取质数冲突的概率最小 
// int h[N],e[N],nt[N],idx;//因为操作不超过100000，所以虽然N代表大于1e5的第一个指数也可以在开辟数组时使用
// void insert(int x)
// {
//     int k=(x%N+N)%N;//防止x是小数导致下标越界
//     e[idx]=x;
//     nt[idx]=h[k];
//     h[k]=idx++;//加入当前链表
// }
// bool query(int x)
// {
//     int k=(x%N+N)%N;//防止x是小数导致下标越界
//     for(int i=h[k];i!=-1;i=nt[i])
//     {
//         if(e[i]==x)
//         {
//             return true;
//         }
//     }
//     return false;
// }
// int main()
// {
//     int n,x;
//     scanf("%d",&n);
//     char op[2];
//     memset(h,-1,sizeof h);//清空，空指针用-1代替
//     for(int i=0;i<n;i++)
//     {
//         scanf("%s%d",op,&x);
//         if(*op=='I')
//         {
//             insert(x);
//         }
//         else
//         {
//             if(query(x))
//             {
//                 printf("Yes\n");
//             }
//             else
//             {
//                 printf("No\n");
//             }
//         }
//     }
//     return 0;
// }

//开放寻址法
//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 2e5 + 3;        //大于数据范围的第一个质数
const int null = 0x3f3f3f3f;  //规定空指针为 null 0x3f3f3f3f
int h[N];
int find(int x)//如果存在数则返回下标，如果不存在则返回遇到的第一个null的下标
{
    int k=(x%N+N)%N;
    while(h[k]!=null&&h[k]!=x)
    {
        k++;
        if(k==N)
        {
            k=0;
        }
    }
    return k;
}
int main()
{
    int n,x;
    scanf("%d",&n);
    char op[2];
    memset(h,0x3f3f3f3f,sizeof h);//清空，空指针用-1代替
    for(int i=0;i<n;i++)
    {
        scanf("%s%d",op,&x);
        if(*op=='I')
        {
            h[find(x)]=x;
        }
        else
        {
            if(h[find(x)]==null)
            {
                printf("No\n");
            }
            else
            {
                printf("Yes\n");
            }
        }
    }
    return 0;
}