A1078 Hashing (25分)

題意：
1、创建hashtable,输出每一个值的下标位置，
2、哈希函数是取余，冲突采用平方探测法，正向冲突
3、给出的Tsize不是素数，要重新改为第一个比TSIZE大的素数

解题：
1、首先，对于一个不是素数的TSIZE，必须找到第一个比他的素数
2、开一个bool型数组，如果是false，表示未被使用，则直接插入
如果是true，则使用平方探测法，令step为1，瞎拍一部检测为（a + step * step）% size，
注意：如果到了tsize，还没有找到可用位置，表明这个位置无法插入

learn && wrong:
1、冲突处理公式记得摸上tsize
2、1号监测点错了，是把1当做素数
3、最后一个监测点超时，是因为程序出现死循环，一般是因为使用了while(tashtable[key] == true)且在找到位置没有中断这个循环
4、格式错误挺好的，i为0，先除数数字，后面是空格+数字，三种输出空格解法之一
5、0~tsize - 1，还找不到，之后也找不到，是可以证明的，略

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

const int maxn = 11111;

bool isprime(int 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[maxn] = {0}; //hashtable[x] == false怎x号位未被使用

int main(int argc, char** argv) {
    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号位未被使用，则已经找到
                    if(i == 0) printf("%d",M);  //!!!处理空格
                    else printf(" %d",M);
                    break;  //记得break！！！
                }
            }
            if(step >= tsize) { //找不到可以插入的地方
                if(i > 0) printf(" ");
                printf("-");
            }
        }
    }
    return 0;

}