acwing840 模拟散列表 2021/11/27

本文主要是介绍acwing840 模拟散列表 2021/11/27，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
int const n=100003;

int h[n],e[n],ne[n],idx;
h[]是哈希函数的一维数组//e[]是链表中存的值//ne[]是指针存的指向的地址//idx是当前指针

void insert(int x)
{
    int k = (x % n + n) % n; 对负数的处理,k是哈希值

    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++;                          //如果不同单链表的idx都是从0开始单独计数，
                                            //那么不同链表之间可能会产生冲突
                                            //比如如果第0个节点被分配给了第一个单链表，
                                            //那么所有单链表就只能从下一个节点开始分配，
                                            //所以所有单链表需要共用一个idx。
                                            //就是单链表的插入操作 开放寻址法
}
bool find(int x)
{
    int k= (x % n + n) % n;  ///为了让负数在整数有映射,负数的取模还是负数,加上maxn后为正,再%即可
    for(int i = h[k]; i != -1; i = ne[i])//
        if(e[i] == x)
            return true;

return false;
}
int main(void)
{
   cin.tie(0);//减少时间 提高效率
   int n;  cin>>n;
   
   memset(h, -1, sizeof(h));  ///所有槽都清空,对应的是单链表的头(head) 指针为-1表示清空
   
   while(n--) 
   {
       char op[2]; int x;
       scanf("%s%d", op, &x);
       
       if(op[0] == 'I') insert(x);
       else 
       {

           if(find(x)) cout<<"Yes"<<endl;
           else cout<<"No"<<endl;
       }
   }
   
    return 0;  
    
}

这篇关于acwing840 模拟散列表 2021/11/27的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！