首页 > 试题广场 >

有一组关键字为{77,28,38,41,45,1,9,31,

[问答题]

有一组关键字为{77,28,38,41,45,1,9,31,99,51,23,47,68,61}.1,请构造一个hash函数，形式为H（key）=key mod p，装填因子a=0.8，用链地址法解决冲突；2计算等概率情况下查找成功的平均查找长度；3计算等概率情况下查找失败的平均查找长度（空指针的比较不计入）。

努力变强的王小姐

hhhh

发表于 2017-08-10 19:09:43 回复(0)

冷静。

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;

int main()
{
int key[14] = {77,28,38,41,45,1,9,31,99,51,23,47,68,61};
int remain[14];
int remain_conts = 0;
int temp;
int p = 0;
while(++p)
{
remain_conts = 0;
for (int i = 0; i < 14; i++)
{
temp = key[i]%p;
int j = 0;
for (; j < remain_conts; j++)
{
if (remain[j] == temp) break;
}
if (j == remain_conts)
{
remain[remain_conts++] = temp;
}
}
if (abs((float)remain_conts/p-0.8) < 0.1)
{
break;
}
}
cout<<p<<endl;
cout<<"对应的余数:"<<endl;
for (int i = 0; i< 14; i++)
{
cout<<key[i]%p<<endl;
}
return 0;

}

通过计算，p等于6，对应的余数为：5 4 2 5 3 1 3 1 3 3 5 5 2 1，共占5个表项，5/6约等于0.83

发表于 2018-08-05 18:11:20 回复(2)

没毛病

装填因子为0.8 元素个数为14个，那么表长为14/0.8＝17.5，那么表长取18 :)我总感觉不太对:) 那p取18 hash函数为mod 18，对应的槽编号为{5 10 2 5 9 1 9 13 9 15 5 11 14 7}，查找成功的比较次数为{1 1 1 2 1 1 2 1 3 1 3 1 1 1}查找14个数需要比较20次查找成功平均查找长度为 20/14。链地址法，查找失败，每个元素都会比较一次，18次查找失败的总比较次数为元素总数14，失败平均查找长度为14/18

编辑于 2017-08-18 23:42:44 回复(6)