经典指数          
原因
3605
浏览数
0
收藏数
 

已知某哈希表 HT 的装填因子小于 1 ,哈希函数 H(key) 为关键字的第一个字母在字母表中的序号。 (1) 处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。 (2) 处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意,此算法中规定不能用公式直接求解计算。

     举报   纠错  
 
切换
1 个答案
[题目分析] 本题未直接给出哈希表表长,但已给出装填因子小于1,且哈希函数H(k)为关键字第一个字母在字母表中的序号,字母‘A’的序号为1,表长可设为n(n≥27),而链地址法中,表长26。查找不成功是指碰到空指针为止(另一种观点是空指针不计算比较次数)。 (1)void  Print(rectype h[ ])        //按关键字第一个字母在字母表中的顺序输出各关键字       {int   i,j;for(i=0;i≤26;i++) // 哈希地址0到26   {j=1;printf(“\n”);    while(h[j]!=null) // 设哈希表初始值为null      {if(ord(h[j])==i)// ord()取关键字第一字母在字母表中的序号         printf(“%s”,h[j]);j=(j+1)% n;     }}} (2)int   ASLHash(rectype  h[ ])       // 求链地址解决冲突的哈希表查找不成功时的平均查找长度      {int  i,j;count=0;//记查找不成功的总的次数LinkedList  p;for(i=0;i≤26;i++)   {p=h[i];j=1;//按我们约定,查找不成功指到空指针为止。     while(p!=null){j++;p=p->next;}     count+=j;    }   return  (count/26.0);}
 
切换
撰写答案
扫描后移动端查看本题