数据结构实验之查找五:平方之哈希表 (SDUT 3377)
2023-06-13 09:17:22 时间
Hash表的平方探测思路:如果当前这个没存放数值,就放进去,如果当前这个地方Hash [ i ] 已经有数值了,就以平方的间隔左右寻找没有存放数的空白 Hash [ i ]。
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int a[2000];
int Hash[2000];
int main()
{
int n,p;
while(~scanf("%d%d",&n,&p))
{
for(int i = 0; i < n; i ++)
{
scanf("%d",&a[i]);
}
memset(Hash,inf,sizeof(Hash)); //初始化一下。
for(int i = 0; i < n; i ++)
{
int d = a[i] % p;
if(Hash[d] == inf) // 如果这个地方没有存放数据,可以存放
{
Hash[d] = a[i];
a[i] = d; //里面更改成存放 a[i] 的下标值
}
else {
for(int j = 1; ; j ++) // 正反向寻找
{
int tm = j * j;
if(Hash[(d + tm)%p] == inf) // 记住别忘记 MOD p ,因为可能会超过给的表的长度
{
Hash[(d + tm)%p] = a[i];
a[i] = (d + tm)%p;
break;
}
else if(Hash[(d -tm)%p] == inf)
{
Hash[(d - tm)%p] = a[i];
a[i] = (d - tm)%p;
break;
}
}
}
}
for(int i = 0; i < n; i ++)
{
if(i == 0)printf("%d",a[i]);
else printf(" %d",a[i]);
}
printf("\n");
}
return 0;
}
相关文章
- 02142数据结构导论真题解析_00246国际经济法概论自考
- 数据结构(1)-线性表「建议收藏」
- 数据结构:数组和链表的区别(数组和链表的优缺点 & 数组和链表的适用场景)
- Lua数据结构
- 数据结构、算法与应用 习题6.1 p124
- 数据结构小记【Python/C++版】——散列表篇
- 预备小菜:Python入门之数据结构
- 数据结构实验之数组一:矩阵转置(SDUT 2130)
- 数据结构实验之二叉树一:树的同构 (SDUT 3340)
- 数据结构实验之查找七:线性之哈希表 (SDUT 3379)
- 【数据结构】栈队列代码实现
- 【数据结构】顺序表的增删查改 (C语言实现)
- 【数据结构初阶】数组栈和链式队列的实现
- [C语言] 数据结构-预备知识动态内存分配详解编程语言
- 【数据结构】之二叉树的java实现详解编程语言
- 简介Redis五种数据结构概述(redis五种数据结构)
- Python中列表、字典、元组、集合数据结构整理