您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

PAT 1078 Hashing：二次探測法構建雜湊表完整實現

編輯：C++ 入門

PAT 1078 Hashing：二次探測法解決衝突的雜湊表構建

題目大意

給定表大小 TableSize 和 N 個整數鍵值。雜湊函數 H(key) = key % TableSize。衝突時使用二次探測：H_i = (H(key) + i²) % TableSize，i = 1, 2, ..., TableSize-1。要求 TableSize 為不小於輸入大小的最小質數。輸出每個鍵值最終存放位置，無法插入輸出 -。

核心步驟

質數表大小：從輸入 TableSize 開始遞增，找第一個質數（篩法預計算）
雜湊插入：計算初始位置，衝突則按 i² 探測
輸出格式：位置間用空格分隔，首個無前導空格

完整程式碼

#include <cstdio>, <cstring>, <iostream>, <cmath>
using namespace std;

const int MAXP = 10100;
int prime[MAXP], vis[MAXP], pcnt;

void sieve() {
    memset(vis, 0, sizeof(vis));
    pcnt = 0;
    for (int i = 2; i < MAXP; ++i) {
        if (!vis[i]) {
            prime[pcnt++] = i;
            for (int j = i*2; j < MAXP; j += i) vis[j] = 1;
        }
    }
}

int main() {
    sieve();
    int MSize, N;
    while (scanf("%d%d", &MSize, &N) == 2) {
        int tableSize = MSize;
        for (int i = 0; i < pcnt; ++i)
            if (prime[i] >= MSize) { tableSize = prime[i]; break; }
        
        vector hashTable(tableSize, 0);  // 0=空, 1=佔用
        
        for (int i = 0; i < N; ++i) {
            int key; scanf("%d", &key);
            int pos = key % tableSize;
            
            if (!hashTable[pos]) {
                hashTable[pos] = 1;
            } else {
                // 二次探測
                bool placed = false;
                for (int step = 1; step < tableSize; ++step) {
                    pos = (key + step * step) % tableSize;
                    if (!hashTable[pos]) {
                        hashTable[pos] = 1;
                        placed = true;
                        break;
                    }
                }
                if (!placed) pos = -1;  // 標記失敗
            }
            
            // 輸出
            if (i) printf(" ");
            if (pos == -1) printf("-");
            else printf("%d", pos);
        }
        printf("\n");
    }
    return 0;
}