A29395. 整型关键字的平方探测法散列
填空题
较难
知识点
题目描述
整型关键字的平方探测法散列
题目描述
本题的任务很简单：将给定的无重复正整数序列插入一个散列表，输出每个输入的数字在表中的位置。所用的散列函数是 H(key) = key % TSize，其中 TSize 是散列表的表长。要求用平方探测法（只增不减，即H(Key)+i2）解决冲突。
注意散列表的表长最好是个素数。如果输入给定的表长不是素数，你必须将表长重新定义为大于给定表长的最小素数。
时间限制：4000 内存限制：65536
输入
首先第一行给出两个正整数 MSize（≤ 104）和 N（≤ MSize），分别对应输入的表长和输入数字的个数。随后第二行给出 N 个不重复的正整数，数字间以空格分隔。
输出
在一行中按照输入的顺序给出每个数字在散列表中的位置（下标从 0 开始）。如果某个数字无法插入，就在其位置上输出 `-`。输出间以 1 个空格分隔，行首尾不得有多余空格。
样例输入
4 4
10 6 4 15
样例输出
0 1 4 -
参考答案
#include <stdio.h>
#include <stdlib.h>
#define bool char
#define true 1
#define false 0
//判断是否素数
bool SuShu(int n)
{
if(n == 1)
return false;
else if(n == 2)
return true;
int mark = 1;
for(int i = 2; i < n; i++)
{
if(n%i == 0)
{
mark = 0;
break;
}
}
if(mark == 1)
return true;
else
return false;
}
//如果不是素数就加一
//例如题目给的测试数据，由于给定散列表的长度为4，不是素数，散列表的长度通过Add增长成了5
int Add(int num)
{
while(!SuShu(num))
{
num++;
}
return num;
}
//哈希表结构
typedef struct HashTable
{
int data;
} HashTable;
//存储方式
void Cunchu(HashTable* H, int key[], int m, int n)
{
//从第一个数开始判断在散列表的哪个位置
for(int i = 0; i < n; i++)
{
//按照题意H（key） = key%Tsize
//例如第一个数是10，10对表长5取余=0，所以Hkey=0.
int Hkey = key[i]%m;
//被占用时
int j;
//pos是通过公式计算出当前数应该放的位置
int pos = Hkey;
//从当前位置判断是否被占用
for(j = 1; H[Hkey].data != -1; j++)
{
//如果被占用了就用题中所述用平方探测法（只增不减，即H(Key)+i2）解决冲突
//也就是从当前位置一个一个向下计算出Hkey，判断Hkey的位置是否被占用。
Hkey = (pos+j*j)%m;
//到了m还没探测出来那说明放没法放了，退出循环。
if(j == m)
{
break;
}
}
//这个条件说明这个数没地方放了，于是按照题意输出‘-’
if(j == m)
{
if(i == 0)
printf("-");
else
printf(" -");
}
//否则就是放进去了，按照格式输出这个数
else
{
if(i == 0)
printf("%d",Hkey);
else
printf(" %d",Hkey);
H[Hkey].data = key[i]; //存进散列表
}
}
}
int main()
{
//m是表长，n是数字个数
int m, n, i;
scanf("%d %d",&m,&n);
int num[n];
for(i = 0; i < n; i++)
{
scanf("%d",&num[i]);
}
//对表长进行余数处理
m = Add(m);
HashTable H[m];
//-1代表还没被占用
for(i = 0; i < m; i++)
{
H[i].data = -1;
}
//开始存储
Cunchu(H, num, m, n);
return 0;
}
上一题
下一题