1078 Hashing (25分)

1078

分析：

給一個(gè)mszie和n個(gè)數(shù)，要求輸出每一個(gè)數(shù)在散列表中的位置。使用正向平方探測(cè)法。如果msize不是質(zhì)數(shù)，則往上尋找一個(gè)最小的質(zhì)數(shù)替代。
使用hashTable記錄每個(gè)位置是否存放值。
注意正向平方探測(cè)的方法是 M = (a + step * step) % msize ,step從1一直增長(zhǎng)到msize（可以證明如果達(dá)到msize時(shí)還無法插入，則這個(gè)元素?zé)o法被插入）。

C++：

#include <cstdio>
#include <cmath>

const int maxn = 10010;
bool hashTable[maxn];

bool isPrime(int n) {
    if (n <= 1) return false;
    int sqr = (int) sqrt(n * 1.0);
    for (int i = 2; i <= sqr; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int msize, n;
    scanf("%d %d", &msize, &n);
    while (isPrime(msize) == false) {
        msize++;
    }
    int a;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a);
        int mod = a % msize;
        if (hashTable[mod] == false) {
            hashTable[mod] = true;
            if (i == n - 1) {
                printf("%d", mod);
            } else {
                printf("%d ", mod);
            }
        } else {
            int step;
            for (step = 1; step < msize; step++) {
                mod = (a + step * step) % msize;
                if (hashTable[mod] == false) {
                    hashTable[mod] = true;
                    if (i == n - 1) {
                        printf("%d", mod);
                    } else {
                        printf("%d ", mod);
                    }
                    break;
                }
            }
            if (step >= msize) {
                if (i == n - 1) {
                    printf("-");
                } else {
                    printf("- ");
                }
            }
        }
    }
    return 0;
}