11-散列2 Hashing (25分)
11-散列2 Hashing (25分)
The task of this problem is simple: insert a sequence of distinct positive integers into a hash table, and output the positions of the input numbers. The hash function is defined to be H(key)=key%TSize where TSize is the maximum size of the hash table. Quadratic probing (with positive increments only) is used to solve the collisions.
这个问题的任务很简单:将一个不同的正整数序列插入到哈希表中,然后输出输入数字的位置。哈希函数定义为H(key)= key%TSize,其中TSize是哈希表的最大大小。二次探测(仅具有正增量)用于解决冲突。
Note that the table size is better to be prime. If the maximum size given by the user is not prime, you must re-define the table size to be the smallest prime number which is larger than the size given by the user.
请注意,表大小最好是素数。如果用户给出的最大大小不是素数,则必须将表大小重新定义为最小的素数,该最小素数大于用户给出的大小。
Input Specification:
Each input file contains one test case. For each case, the first line contains two positive numbers: MSize (≤10^4) and N (≤MSize) which are the user-defined table size and the number of input numbers, respectively. Then N distinct positive integers are given in the next line. All the numbers in a line are separated by a space.
每个输入文件包含一个测试用例。对于每种情况,第一行均包含两个正数:MSize(≤10^4)和N(≤MSize)分别是用户定义的表大小和输入数字的数量。然后在下一行中给出N个不同的正整数。一行中的所有数字都用空格分隔。
Output Specification:
For each test case, print the corresponding positions (index starts from 0) of the input numbers in one line. All the numbers in a line are separated by a space, and there must be no extra space at the end of the line. In case it is impossible to insert the number, print “-“ instead.
对于每个测试用例,在一行中打印输入数字的相应位置(索引从0开始)。一行中的所有数字均以空格分隔,并且行尾不得有多余的空格。如果无法插入数字,请打印“-”。
Sample Input:
4 4
10 6 4 15
Sample Output:
0 1 4 -
解析
哈希表长是比原表 大的最小素数:例如原表是4,则哈希表为5
用数组存储,输入数除余后,检测所在数组位置是否被占用,如果被占用,则每次用余数加i的平方(i从1开始),如果全不合适,就输出“-”
代码
#include<bits/stdc++.h>
using namespace std;
int size(int x){
if(x==1)
return 2;
int p,flag;
p=x;
while(1){
flag=1;
for(int i=2;i<=sqrt(x);i++){
if(p%i==0){
flag=0;
break;
}
}
if(flag==0){
p+=1;
}else{
return p;
}
}
}
int get(int key,int n){
return key%n;
}
int main(){
int n,m;
cin>>n>>m;
n=size(n); //大于表长最大的素数
int a[n],x,pos,tempx;
memset(a,-1,sizeof(a));
for(int i=0;i<m;i++){
if(i!=0)
cout<<" ";
cin>>x;
pos=get(x,n);
tempx=pos;
if(a[tempx]==-1){ //验证所在位置是否为空
a[tempx]=x;
cout<<pos;
}else{
int cnt,flag=0;
for(cnt=1;cnt<n;cnt++){
pos=get(tempx+cnt*cnt,n); //判断其他位置是否可以插入
if(a[pos]==-1){
flag=1;
a[pos]=x;
cout<<pos;
break;
}
}
if(flag==0){
cout<<"-";
}
}
}
return 0;
}