09-散列1. Hashing (25).zip

#include <iostream> #include <math.h> #include <stdlib.h> #include <memory.h> using namespace std; /* run this program using the console pauser or add your own getch, system("pause") or input loop */ struct Hash { bool * Storage; int MSize; }; Hash * Creat(int MSize) { Hash *h=new Hash; h->MSize=MSize; h->Storage=new bool[MSize]; fill(h->Storage,h->Storage+h->MSize,false); return h; } bool isPrim(int p) { int i=0; if(p<2) return false; for(i=2; i<=sqrt(p); i++) { if(p%i==0) return false; } return true; } int Prim(int n) { while(!isPrim(n)) { n++; } return n; } int Hash_Fun(int key, int MSize) { return key%MSize; } int main(int argc, char** argv) { int MSize,N; scanf("%d %d",&MSize,&N); MSize=Prim(MSize); Hash *H=Creat(MSize); for(int i=0; i<N; i++) { int tmp; bool flag=false; scanf("%d",&tmp); for(int j=0; j<N; j++) { int pos=Hash_Fun(Hash_Fun(tmp,H->MSize)+j*j,H->MSize); if(!H->Storage[pos]) { H->Storage[pos]=true; flag=true; (i==N-1)?printf("%d",pos):printf("%d ",pos); break; } } if(flag) continue; else { (i==N-1)?printf("-"):printf("- "); } } return 0; }