模拟散列表
题目 模拟散列表
思路分析
代码实现
开放寻址法
/*
只用一个数组去存储映射后的关系
如果冲突了 就继续往后找 直到找到一个坑没被占
那这样的话 数组长度就应该比理想情况要大了 大多少 最好开两到三倍
对于这么一个结构来说 核心就是查找了
如果得到一个k 从h[k]开始去找
如果当前位置有数 并且就为x 那就找到了x
如果当前位置有数 但不是x 那就往后找
如果当前位置没数 那就x不存在（执行删除还是返回没找到看操作要求 核心就是一个find）
怎么表示该某位置没元素？ 全初始化成无穷大
*/
#include<bits/stdc++.h>
using namespace std;
const int N=200003;//开双倍
const int null=0x3f3f3f3f;//无穷大
int h[N];
//若存在 返回位置 若不存在 返回应该存的位置
int find(int x)
{
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;
cin>>n;
//初始化为无穷大
memset(h,0x3f,sizeof h);
while(n--)
{
char op[2];
int x;
scanf("%s%d",op,&x);
int k=find(x);
if(*op=='I')
h[k]=x;
else
{
if(h[k]!=null)
puts("Yes");
else
puts("No");
}
}
return 0;
}
拉链法
/*
就是把一个数处理后 得到一个下标位置
但如果这个下标位置已经有元素了
那就把它链在后面
但是这里我们还是用数组模拟的链表
嗯 一个e放数据本身 一个ne放下一个位置的下标
在一维的每一个结点的后面都接两个数组
其实没必要
因为一维中存的不过是一个下标 作用就是单链表中的head
各个域中的head并不冲突 它只需要根据下标找到e数组中的第一个数
再链着ne找下一个数 直到所有
所以 完全可以把所有的数都存放在一个e、ne中
不同域去就相当于不同的head 去进行一个索引
嗯 把一个数组拆成多个链
把一维的每一个位置都当做head即可 不过是对一个数组有多个head访问罢了
那么既然是当head用
所以初始化就是要把所有的值都赋为-1表示空
memset(h,-1,sizeof h);
插入一个点 就是头插
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
遍历也很简单 从头开始 i=h[k]
直到结束i!=-1 每次往后寻 i=ne[i]
for(int i=h[k];i!=-1;i=ne[i])
*/
#include<bits/stdc++.h>
using namespace std;
const int N=100003;
int h[N],e[N],ne[N];
int idx;
void insert(int x)
{
int k=(x%N+N)%N;
//找到了k位置
//其实就是头插了
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
}
bool 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()
{
int n;
cin>>n;
memset(h,-1,sizeof h);
while(n--)
{
char op[2];
int x;
scanf("%s%d",op,&x);
if(*op=='I')
insert(x);
else
{
if(find(x))
puts("Yes");
else
puts("No");
}
}
return 0;
}
💬 评论