给定输入{4317, 1323, 6173, 4199, 4344, 9679, 1989},散列表的长度为11,散列函数为H(x)=X mod 11,写出下列结果。 (1) 线性探测散列表。 (2) 二次探测散列表。 (3) 开散列表。
时间: 2023-07-14 11:14:05 浏览: 92
(1) 线性探测散列表:
散列函数:H(x)=X mod 11
插入顺序:4317, 1323, 6173, 4199, 4344, 9679, 1989
散列表:[4317, 9679, 1323, 6173, 4199, 4344, 0, 0, 0, 0, 1989]
解释:第一个数 4317 对应的散列地址为 4317 mod 11 = 8,散列表中该位置为空,因此直接插入该位置。同理,1323 对应的散列地址为 1323 mod 11 = 0,6173 对应的散列地址为 6173 mod 11 = 4,4199 对应的散列地址为 4199 mod 11 = 4,由于 4 号位置已经被占用,因此需要进行线性探测,即向后遍历散列表,直到找到一个空位置插入。最终散列表如上所示。
(2) 二次探测散列表:
散列函数:H(x)=X mod 11
插入顺序:4317, 1323, 6173, 4199, 4344, 9679, 1989
散列表:[4317, 9679, 1323, 6173, 4199, 4344, 0, 0, 0, 0, 1989]
解释:与线性探测散列表类似,不同之处在于二次探测需要按照一定公式计算跳跃的步长,具体实现可参考二次探测散列表的算法实现。
(3) 开散列表:
散列函数:H(x)=X mod 11
插入顺序:4317, 1323, 6173, 4199, 4344, 9679, 1989
散列表:[6173 -> 9679 -> 1989, 4317, 1323, 0, 0, 0, 0, 0, 0, 4199 -> 4344, 0]
解释:开散列表采用链表解决冲突,并且需要保证链表中的元素顺序与插入顺序相同。首先将 6173、9679、1989 三个数插入到散列地址为 6 的位置,由于 4199 对应的散列地址为 4199 mod 11 = 5,与 4344 对应的散列地址相同,因此将其插入到地址为 5 的位置,并且与 4344 组成链表。最终散列表如上所示。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)