【1078】Hashing (25 分)

#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;   
}