6、设散列表长度为11,散列函数H(k)=k MOD 11,若输入顺序为(2,4,18,23,26,7,12,33,66,34)。试用链地址法解决冲突构造散列表。
时间: 2024-05-30 07:08:25 浏览: 11
首先根据散列函数H(k)=k mod 11计算每个关键字的散列地址,得到以下结果:
2→0,4→4,18→7,23→1,26→4,7→7,12→1,33→0,66→0,34→1
然后按照散列地址将关键字分别存入对应的链表中,得到以下散列表:
0:2→33→66
1:23→12→34
2:
3:
4:4→26
5:
6:
7:18→7
8:
9:
10:
注:箭头→表示链表中的指针指向下一个元素。
最终得到的散列表如上所示,其中每个链表中的元素按照输入顺序依次存储。如果需要查询某个关键字对应的值,则可以先计算其散列地址,然后在对应的链表中进行查找。如果存在多个关键字映射到同一个散列地址,则需要在对应的链表中进行顺序查找,直到找到目标元素或者链表结束。
相关问题
设散列表的长度为8,散列函数h(k)=kmod7
散列表的长度为8意味着散列表中有8个存储位置。散列函数h(k)=kmod7表示对关键字k进行取模运算并将结果作为存储位置的索引值。
具体来说,当我们向散列表中插入一个关键字时,我们首先对关键字进行散列函数计算,得到的结果为k对7取模的值。例如,如果关键字k=15,那么h(k)=15mod7=1,意味着关键字15会被存储在散列表的第1个位置上。
散列表的长度为8,散列函数h(k)=kmod7,意味着散列表中的存储位置索引值的范围是0到7。实际上,对于当前的散列函数和散列表长度,任意关键字经过散列函数计算后得到的结果都在0到6之间,这样就可以保证插入时能够找到对应的存储位置。
在使用散列函数h(k)=kmod7时,需要注意关键字的选择和散列表的大小,以保证散列函数计算的结果能够均匀地分布在散列表中,从而避免发生过多的冲突。当发生冲突时,可以采用开放定址法、链地址法等方法进行解决。
总而言之,散列表的长度为8,散列函数h(k)=kmod7,通过合理的关键字选择和冲突解决方法,可以有效地进行散列表的插入、查找和删除等操作。
设散列表的地址区间为0~17,散列函数为H(K) =K mod 13,K为关键字。用线性探测法
来解决散列冲突,其中插入的关键字序列为{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
```
注意,在线性探测法中,如果散列表已经被占满,插入新的关键字将失败。因此,在设计散列表时,需要考虑预留一定的空间,以免发生这种情况。
相关推荐
![doc](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)
![](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)