【1078】Hashing (25 分)

举报
野猪佩奇996 发表于 2022/01/23 02:13:35 2022/01/23
【摘要】 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#include<algorithm> #include<map>#inclu...

  
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<math.h>
  5. #include<string.h>
  6. #include<algorithm>
  7. #include<map>
  8. #include<vector>
  9. #include<queue>
  10. using namespace std;
  11. key:散列函数H(key)=key%TSize,解决冲突使用二次方探查法
  12. 可证明得:如果步长step从0~TSize-1枚举仍然无法找到位置,则step≥TSize也不可能找到位置了
  13. const int N=11111;
  14. bool isPrime(int n){ //判断n是否素数
  15. if(n <= 1) return false;
  16. int sqr=(int)sqrt(1.0*n);
  17. for(int i=2;i<=sqr;i++){
  18. if(n%i == 0) return false;
  19. }
  20. return true;
  21. }
  22. bool hashTable[N]={0};//hashTable[x] == false 则x号位未被使用
  23. int main(){
  24. int n,TSize,a;
  25. scanf("%d%d",&TSize,&n);
  26. while(isPrime(TSize) == false){ //寻找第一个≥TSize的质数
  27. TSize++;
  28. }
  29. for(int i=0;i<n;i++){
  30. scanf("%d",&a);
  31. int M=a%TSize;
  32. if(hashTable[M] == false) { //如果M号位未被使用,则已找到
  33. hashTable[M]=true;
  34. if(i == 0) printf("%d",M);
  35. else printf(" %d",M);
  36. }else {
  37. int step; //二次方探查法步长
  38. for(step=1;step < TSize ;step++){ //可以证明TSize为循环节
  39. M=(a+step*step)%TSize; //下一次检测值
  40. if(hashTable[M] == false){ //如果M号位置未被使用,则已找到
  41. hashTable[M]=true;
  42. if(i == 0) printf(" %d",M);
  43. else printf(" %d",M);
  44. break;//记住要break
  45. }
  46. }
  47. if(step >=TSize){ //找不到插入的地方
  48. if(i >0) printf(" ");
  49. printf("-");
  50. }
  51. }
  52. }
  53. system("pause");
  54. return 0;
  55. }

 

文章来源: andyguo.blog.csdn.net,作者:山顶夕景,版权归原作者所有,如需转载,请联系作者。

原文链接:andyguo.blog.csdn.net/article/details/99893394

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。