首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

小题求大家帮帮忙 新人啊

2013-07-08 
小题求大家帮帮忙 新人在线等啊!已知一组关键字?(32,40,?36,?53,?16,?46,?71,?27,?42,?24,?49,?64)?哈希表

小题求大家帮帮忙 新人在线等啊!
已知一组关键字?(32,40,?36,?53,?16,?46,?71,?27,?42,?24,?49,?64)?哈希表长度为13,哈希函数为:H(key)=key%13???(1)设计用线性探测再散列处理冲突的哈希表
[解决办法]
采用除留余数法加线性探查法:
   关键字集合的哈希表:(32,40, 36, 53, 16, 46, 71, 27, 42, 24, 49, 64)
   解:n=12,m=13  哈希函数:H(key)=key%13 则有:
   H(32)=6,                没有冲突,将32放在Ha[6]处
   H(40)=1,                没有冲突,将32放在Ha[1]处
   H(36)=10,               没有冲突,将32放在Ha[10]处
   H(53)=1,                有冲突   
      d0=1,d1=(1+1)%13=2      没有冲突,将32放在Ha[2]处
   H(16)=3,                没有冲突,将32放在Ha[3]处
   H(46)=7,                没有冲突,将32放在Ha[7]处
   H(71)=5,                没有冲突,将32放在Ha[5]处
   H(27)=1,                有冲突
      d0=1,d1=(1+1)%13=2      有冲突
      d2=(2+1)%13=3           有冲突
      d3=(3+1)%13=4           没有冲突,将32放在Ha[4]处
   H(42)=3,                有冲突
      d0=3,d1=(3+1)%13=4      有冲突
      d2=(4+1)%13=5           有冲突
      d3=(5+1)%13=6           有冲突
      ......                  有冲突


      d5=(7+1)%13=8           没有冲突,将32放在Ha[8]处
   H(24)=11,               没有冲突,将32放在Ha[11]处
   H(49)=10,               有冲突
     ......                   有冲突
      d2=(11+1)%13=12         没有冲突,将32放在Ha[12]处
   H(64)=12,               有冲突
      d0=12,d1=(12+1)%13=0    没有冲突,将32放在Ha[0]处


建立的哈希表如下:
下标        0    1   2   3   4   5   6   7   8   9   10   11   12
K           64   40  53  16  27  71  32  46  42      36   24   49
探查次数    2    1   2   1   4   1   1   1   6   1   1    1    3

热点排行