{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为:h(key)=key % 17,采用平方5.6测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表。平方探测法
时间: 2023-06-20 13:07:50 浏览: 53
首先,我们需要创建一个长度为 19 的散列表(0 到 18 共 19 个地址),并初始化为空。然后,我们依次将关键字序列插入散列表中,遇到冲突时采用平方探测法解决冲突。
具体地,对于关键字 key,我们计算它的散列地址 h(key) = key % 17,如果该地址空间已经被占用,则使用平方探测法查找下一个可用的地址。假设当前散列地址为 h,平方探测步长为 i,则下一个探测地址为:
h' = (h + i^2) % 19
其中,i 的初始值为 1,每次冲突时增加 1,直到找到一个空闲的地址。
下面是具体的插入过程:
1. 插入关键字 29,计算散列地址 h(29) = 12,该地址空间为空,直接插入。
散列表:[ , , , , , , , , , , , 29, , , , , , , ]
2. 插入关键字 01,计算散列地址 h(01) = 1,该地址空间为空,直接插入。
散列表:[ , 1, , , , , , , , , , 29, , , , , , , ]
3. 插入关键字 13,计算散列地址 h(13) = 13,该地址空间为空,直接插入。
散列表:[ , 1, , , , , , , , , , 29, , 13, , , , , ]
4. 插入关键字 15,计算散列地址 h(15) = 15,该地址空间为空,直接插入。
散列表:[ , 1, , , , , , , , , , 29, , 13, 15, , , , ]
5. 插入关键字 56,计算散列地址 h(56) = 5,该地址空间为空,直接插入。
散列表:[ , 1, , , , 56, , , , , , 29, , 13, 15, , , , ]
6. 插入关键字 20,计算散列地址 h(20) = 3,该地址空间为空,直接插入。
散列表:[ , 1, , 20, , 56, , , , , , 29, , 13, 15, , , , ]
7. 插入关键字 87,计算散列地址 h(87) = 4,该地址空间为空,直接插入。
散列表:[ , 1, , 20, 87, 56, , , , , , 29, , 13, 15, , , , ]
8. 插入关键字 27,计算散列地址 h(27) = 10,该地址空间为空,直接插入。
散列表:[ , 1, , 20, 87, 56, , , , , 27, 29, , 13, 15, , , , ]
9. 插入关键字 69,计算散列地址 h(69) = 4,该地址空间被占用,进行平方探测。
探测地址为 h' = (h + i^2) % 19,其中 i = 1,得到 h' = 5。
探测地址 h' 空闲,将关键字 69 插入。
散列表:[ , 1, , 20, 87, 56, 69, , , , 27, 29, , 13, 15, , , , ]
10. 插入关键字 9,计算散列地址 h(9) = 9,该地址空间为空,直接插入。
散列表:[ , 1, , 20, 87, 56, 69, , , 9, 27, 29, , 13, 15, , , , ]
11. 插入关键字 10,计算散列地址 h(10) = 10,该地址空间被占用,进行平方探测。
探测地址为 h' = (h + i^2) % 19,其中 i = 1,得到 h' = 11。
探测地址 h' 空闲,将关键字 10 插入。
散列表:[ , 1, , 20, 87, 56, 69, , , 9, 27, 29, 10, 13, 15, , , , ]
12. 插入关键字 74,计算散列地址 h(74) = 8,该地址空间被占用,进行平方探测。
探测地址为 h' = (h + i^2) % 19,其中 i = 1,得到 h' = 9。
探测地址 h' 被占用,继续探测,i = 2,得到 h' = 14。
探测地址 h' 被占用,继续探测,i = 3,得到 h' = 2。
探测地址 h' 空闲,将关键字 74 插入。
散列表:[ , 1, 74, 20, 87, 56, 69, , , 9, 27, 29, 10, 13, 15, , , , ]
最终的散列表为:[ , 1, 74, 20, 87, 56, 69, , , 9, 27, 29, 10, 13, 15, , , , ]。
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)