首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C语言 >

很简单的构造哈希表,计算查找长度的有关问题(数据结构版没人会,小弟我很着急只好发在这里试试)

2012-03-05 
很简单的构造哈希表,计算查找长度的问题(数据结构版没人会,我很着急只好发在这里试试)设有一组关键字{9,01

很简单的构造哈希表,计算查找长度的问题(数据结构版没人会,我很着急只好发在这里试试)
设有一组关键字{9,01,23,14,55,20,84,27},采用哈希函数:H(key)=key   mod   7   ,表长为10,用开放地址法的二次探测再散列方法Hi=(H(key)+di)mod10(di=1*1,2*2,3*3….)解决冲突。要求:对该关键字序列构造哈希表,并计算查找成功的平均查找长度


我算出来的答案是

地址               0       1     2       3       4       5       6       7     8     9    
值                 14     01     9     23     84     27     55     20
比较次数       1       1     1       2       3       4       1       2

平均查找长度:   (1+1+1+2+3+4+1+2)/8=15/8=1.875

具体过程如下:
9mod7=2  
1mod7=1
23mod7=2   与9位置冲突,   (23mod7+1)mod10=3
14mod7=0
55mod7=6
20mod7=6   与55位置冲突,   (20mod7+1)mod10=7
84mod7=0   与14位置冲突,(84mod7+1)mod10=1   与1位置冲突,  
                  (84mod7+2*2)mod10=4
27mod7=6   与55位置冲突,(27mod7+1)mod10=7   与20位置冲突,
                  (27mod7+2*2)mod10=0   与14位置冲突,
                  (27mod7+3*3)mod10=5

我的答案跟标准答案对不上,我又实在没发现我计算过程哪里错了,大家能帮着看看吗,发现我哪里错了请给我指一下,不胜感激!

标准答案给的是:
地址       0       1       2       3       4       5       6       7       8       9
值         55       1       9     20     84     23     14                     27
次数       4       1       1       2       2       1       2                       4

我怎么也得不出来,是不是答案有问题啊


[解决办法]
要怀疑答案
[解决办法]
我编了个小程序试了下,发现你真的比较靠谱。
原来以为不同排列次序,结果不同。
再仔细一看标准答案:
9==1
23==1
最起码这两个很不靠谱嘛。

热点排行