假设散列表长为m,散列函数为除留余数法,即H(key)=key%p,m和p在主函数中由用户从键盘输入,待散列的数据也由用户从键盘输入,算法如下:
闭散列表构造算法
int CreatHash(int ht[ ], int m)
{
for (i=0; i<m; i++) //散列表初始化
ht[ i ]=0;
cin>>k;
while (k! =’#’) // #作为结束标志
{
j =k % p;
if (ht[ j ] = = 0) ht[ j ] =k; //没有发生冲突,直接存入
else{
i = (j+1) % m;
while (ht[ i ]!=0 && i!=j)
{
if (ht[ i ] = = 0){
ht[ i ] =k; //发生冲突,向后探测若干次后存入
break;
}
else i= (i+1) % m; //向后探测一个位置
}
if (i = = j)throw“溢出”;
}
cin>>k;
}
}
假设在已建立的散列表中进行静态查找,在查找过程中设置计数器count统计元素的比较次数,查找算法如下:
闭散列表的查找算法 HashSearch
int HashSearch ( int ht[ ], int m, int k)
{
j =k %p; count =0; i =j;
while (ht[ i ]!=0)
{
if ( ++count && ht[ i ] = = k) { //发生冲突,比较若干次查找成功
cout<<“查找成功,比较次数为:”<<count<<endl;
return i;
}
i= (i+1) % m; //向后探测一个位置
if (i = = j)break;
}
cout<<“查找不成功,比较次数为:”<<count<<endl;
}