Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1253844
  • 博文数量: 160
  • 博客积分: 4132
  • 博客等级: 中校
  • 技术积分: 2086
  • 用 户 组: 普通用户
  • 注册时间: 2010-11-06 21:56
文章分类

全部博文(160)

文章存档

2012年(25)

2011年(120)

2010年(15)

分类: C/C++

2012-05-06 00:22:38

利用线性探测法构造哈希表

      已知一组关键字为(26,36,41,38,44,15,68,12,06,51),用除余法构造散列函数,用线性探查法解决冲突构造这组关键字的散列表。
  解答:为了减少冲突,通常令装填因子α     由除余法的散列函数计算出的上述关键字序列的散列地址为(0,10,2,12,5,2,3,12,6,12)。
     前5个关键字插入时,其相应的地址均为开放地址,故将它们直接插入T[0],T[10),T[2],T[12]和T[5]中。
     当插入第6个关键字15时,其散列地址2(即h(15)=15%13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)%13=3,此地址开放,所以将15放入T[3]中。
     当插入第7个关键字68时,其散列地址3已被非同义词15先占用,故将其插入到T[4]中。
     当插入第8个关键字12时,散列地址12已被同义词38占用,故探查hl=(12+1)%13=0,而T[0]亦被26占用,再探查h2=(12+2)%13=1,此地址开放,可将12插入其中。
     类似地,第9个关键字06直接插入T[6]中;而最后一个关键字51插人时,因探查的地址12,0,1,…,6均非空,故51插入T[7]中。

阅读(12432) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~