设散列表的地址区间为0~17,散列函数为H(K) =K mod 13,K为关键字。用线性探测法
时间: 2023-05-26 22:03:30 浏览: 91
来解决散列冲突,其中插入的关键字序列为{16, 25, 20, 36, 14, 23, 8, 18},请画出插入后的散列表。
首先,根据散列函数H(K) =K mod 13,我们可以算出每个关键字的散列地址:
- 16 -> H(16) = 3
- 25 -> H(25) = 12
- 20 -> H(20) = 7
- 36 -> H(36) = 10
- 14 -> H(14) = 1
- 23 -> H(23) = 10(冲突)
- 8 -> H(8) = 8
- 18 -> H(18) = 5
发现23和36的散列地址相同,因此需要使用线性探测法来处理冲突。具体来说,就是从冲突地址开始,依次往后查找下一个空闲位置,直到找到可以插入的位置。在这个例子中,我们可以按照以下步骤来插入关键字:
- 16 -> 3 -> 空 -> 空 -> 16
- 25 -> 12 -> 空 -> 空 -> 25
- 20 -> 7 -> 空 -> 空 -> 20
- 36 -> 10 -> 空 -> 空 -> 36
- 14 -> 1 -> 空 -> 空 -> 14
- 23 -> 10 -> 空 -> 1 -> 23
- 8 -> 8 -> 空 -> 空 -> 8
- 18 -> 5 -> 空 -> 空 -> 18
最终的散列表如下图所示:
```
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 16 | | | 25 | | | 20 | 36 | | 14 | 23 | 8 | 18 | | | | | |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
```
注意,在线性探测法中,如果散列表已经被占满,插入新的关键字将失败。因此,在设计散列表时,需要考虑预留一定的空间,以免发生这种情况。