平方探測法————附完整實作代碼

文章目錄

• ​​1概念​​
• ​​2 實作代碼​​

1概念

開放位址法：之可存放新的空閑位址既向它的同義詞表項開放，有向它的非同義表項開放。其數學遞推公式為:

式中，;m表示散清單的表長；d為增量序列。

平方探測法：當時，稱為平方探測法，其中,散列平方探測法是一種較好的處理沖突的方法，可以避免出現“堆積“問題，它的缺點在于不能探測到散清單上的所有單元，但至少能探測一半單元。

“堆積“問題：大量元素在相鄰的散列位址上”聚集“（或堆積）起來，大大降低了查找效率。

2 實作代碼

#include 
#include 

const int MAXN = 100010;
bool hash[MAXN] = {false};//散清單

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

void quadraticProbing(int Tsize, int num){
    int pos = num % Tsize;//應該插入在hash表中的位置
    if(hash[pos] == false){//如果該位置為空
        hash[pos] = true;
        printf("%d", pos);
    }else{
        int isFound = false;//是否被找到
        for (int i = 0;i <= Tsize/2; ++i)//尋找和數的插入位置
        {
            if(hash[(pos + i*i)%Tsize] == false){//平方二次探測法
                hash[(pos + i*i)%Tsize] = true;
                isFound = true;
                printf("%d", (pos + i*i)%Tsize);
                break;
            }
            if(hash[((pos - i*i)%Tsize + Tsize)%Tsize] == false){
                hash[((pos - i*i)%Tsize + Tsize)%Tsize] = true;//取兩次模為了是讓位置的值非負
                isFound = true;
                printf("%d", ((pos - i*i)%Tsize + Tsize)%Tsize);
                break;
            }
        }
            if(isFound == false){
                printf("-");
            }
        }
}

int main(int argc, char const *argv[])
{
    int Tsize, num;/表長、插入數字
    scanf("%d", &Tsize);
    //選擇合适的表長
    while(isPrime(Tsize) == false && (Tsize - 3)/4 == 0){//如果表長不是4k+3倍的素數，則轉換為4k+3倍的素數
        Tsize++;
    }
    while(scanf("%d", &num) != EOF){
        quadraticProbing(Tsize, num);
        printf(" ");
    }
    return 0;
}