3.(10分)线性表的关键字集合key = { 37,12,28,55,20,39,9 },构造哈希表,表长为7(范围0~6),选取哈希函数的方法为“除留余数法”:H ( key ) = key % 7,解决冲突方法为“线性探测再散列”,请按上述条件: (1)求出key中各值的地址,画出相应的哈希表;(4分)2)求出key中各值查找成功时的查找次数;(4分)
时间: 2024-04-04 10:34:28 浏览: 18
(1) 求出key中各值的地址,画出相应的哈希表:
|地址|0|1|2|3|4|5|6|
|---|---|---|---|---|---|---|---|
|值| 37 | 12 | 28 | 55 | 20 | 39 | 9 |
通过除留余数法,计算出各值的地址如下:
H(37) = 2
H(12) = 5
H(28) = 0
H(55) = 6
H(20) = 6
H(39) = 4
H(9) = 2
由于20和55的哈希地址都是6,发生了冲突,因此需要进行线性探测再散列。具体过程如下:
H'(20) = (H(20) + 1) % 7 = 0
H'(55) = (H(55) + 1) % 7 = 0
H''(20) = (H'(20) + 1) % 7 = 1
H''(55) = (H'(55) + 1) % 7 = 1
因此,最终的哈希表如下:
|地址|0|1|2|3|4|5|6|
|---|---|---|---|---|---|---|---|
|值| 28 | 39 | 37, 9 | | 20, 55 | 12 | |
(2) 求出key中各值查找成功时的查找次数:
37的哈希地址为2,查找1次即可找到。
12的哈希地址为5,查找1次即可找到。
28的哈希地址为0,查找1次即可找到。
55的哈希地址为6,发生冲突,需要进行线性探测再散列。经过2次探测,查找3次即可找到。
20的哈希地址为6,发生冲突,需要进行线性探测再散列。经过1次探测,查找2次即可找到。
39的哈希地址为4,查找1次即可找到。
9的哈希地址为2,发生冲突,需要进行线性探测再散列。经过1次探测,查找2次即可找到。
因此,各值查找成功时的查找次数如下:
37:1次
12:1次
28:1次
55:3次
20:2次
39:1次
9:2次
相关推荐
![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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)