天天看点

平方探测法————附完整实现代码

文章目录

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