【1078】Hashing (25 分)
【摘要】
#include<iostream>#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#include<algorithm> #include<map>#inclu...
-
#include<iostream>
-
#include<stdio.h>
-
#include<stdlib.h>
-
#include<math.h>
-
#include<string.h>
-
#include<algorithm>
-
#include<map>
-
#include<vector>
-
#include<queue>
-
using namespace std;
-
key:散列函数H(key)=key%TSize,解决冲突使用二次方探查法
-
可证明得:如果步长step从0~TSize-1枚举仍然无法找到位置,则step≥TSize也不可能找到位置了
-
-
const int N=11111;
-
-
bool isPrime(int n){ //判断n是否素数
-
if(n <= 1) return false;
-
int sqr=(int)sqrt(1.0*n);
-
for(int i=2;i<=sqr;i++){
-
if(n%i == 0) return false;
-
}
-
return true;
-
}
-
bool hashTable[N]={0};//hashTable[x] == false 则x号位未被使用
-
-
int main(){
-
int n,TSize,a;
-
scanf("%d%d",&TSize,&n);
-
while(isPrime(TSize) == false){ //寻找第一个≥TSize的质数
-
TSize++;
-
}
-
for(int i=0;i<n;i++){
-
scanf("%d",&a);
-
int M=a%TSize;
-
if(hashTable[M] == false) { //如果M号位未被使用,则已找到
-
hashTable[M]=true;
-
if(i == 0) printf("%d",M);
-
else printf(" %d",M);
-
}else {
-
int step; //二次方探查法步长
-
for(step=1;step < TSize ;step++){ //可以证明TSize为循环节
-
M=(a+step*step)%TSize; //下一次检测值
-
if(hashTable[M] == false){ //如果M号位置未被使用,则已找到
-
hashTable[M]=true;
-
if(i == 0) printf(" %d",M);
-
else printf(" %d",M);
-
break;//记住要break
-
}
-
}
-
if(step >=TSize){ //找不到插入的地方
-
if(i >0) printf(" ");
-
printf("-");
-
}
-
}
-
}
-
system("pause");
-
return 0;
-
}
文章来源: andyguo.blog.csdn.net,作者:山顶夕景,版权归原作者所有,如需转载,请联系作者。
原文链接:andyguo.blog.csdn.net/article/details/99893394
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)