文章目录
- 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;
}