设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为:H(key)=key%17,分别采用线性探测方法和平方探测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表,并计算成功查找的平均查找长度。
时间: 2023-12-05 17:04:29 浏览: 135
根据散列函数H(key)=key%17,我们可以将关键字序列的散列地址计算出来:
```
key : 29 01 13 15 56 20 87 27 69 9 10 74
H(key) : 12 1 13 15 6 3 5 10 1 9 10 5
```
由于采用线性探测方法解决冲突,我们需要在散列表中寻找下一个可用的空位置。若当前位置已经被占用,则继续向后查找,直到找到一个空位置或者查找完整个散列表。
```
地址 : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
: [1] [13] [56] [20] [87] [69] [9] [10] [27] [74] [12] [15] [3]
```
以上是采用线性探测方法解决冲突的散列表,用中括号括起来的数字表示该位置存储的关键字。
接下来,我们可以计算成功查找的平均查找长度(ASL)。
对于每个关键字,它的查找长度是它在散列表中的位置与它原本的散列地址之差。例如,关键字10的查找长度为11-10=1。
成功查找的平均查找长度是所有关键字的查找长度之和除以关键字个数。在本例中,采用线性探测方法的ASL计算公式如下:
ASL = (1+1+1+1+2+1+1+1+1+1+1+1)/12 = 12/12 = 1
因此,采用线性探测方法时,成功查找的平均查找长度为1。
接下来,我们采用平方探测方法解决冲突。平方探测是指当发生冲突时,按照一定的步长进行查找。步长的大小是一个平方数,例如,第一次查找时步长为1,第二次查找时步长为4,第三次查找时步长为9,以此类推。
为了避免死循环,步长的大小应该与散列表的长度互质。在本例中,散列表的长度为19,因此我们可以采用步长为3的平方探测。
```
地址 : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
: [1] [13] [56] [20] [87] [69] [9] [10] [27] [74] [12] [15] [3]
[1+3^2] [56+3^2] [20+3^2] [9+3^2] [10+3^2] [27+3^2] [74+3^2]
[1+4^2] [56+4^2] [20+4^2] [9+4^2] [10+4^2] [27+4^2] [74+4^2]
[1+9^2] [56+9^2] [20+9^2] [9+9^2] [10+9^2] [27+9^2] [74+9^2]
[1+12^2] [56+12^2][20+12^2] [9+12^2][10+12^2][27+12^2][74+12^2]
[1+13^2] [56+13^2][20+13^2] [9+13^2][10+13^2][27+13^2][74+13^2]
[1+16^2] [56+16^2][20+16^2] [9+16^2][10+16^2][27+16^2][74+16^2]
```
以上是采用平方探测方法解决冲突的散列表。用中括号括起来的数字表示该位置存储的关键字。
接下来,我们计算采用平方探测方法时成功查找的平均查找长度。
在本例中,采用平方探测方法的ASL计算公式如下:
ASL = (1+1+1+1+2+1+1+1+1+1+1+1+2+2+2+2+2+2+2)/12 = 26/12 ≈ 2.17
因此,采用平方探测方法时,成功查找的平均查找长度为2.17。
阅读全文