设散列表的地址范围为0~17,散列函数为:H(K)=K MOD 13,K为关键字。用线性探测法(di=1,2,3,4,...)处理冲突,输入关键字序列:(10,24,32,17,31,30,46,47,40,63,49),试画出构造的散列表
时间: 2024-06-02 21:08:16 浏览: 19
根据散列函数 H(K) = K MOD 13,我们可以构造出以下的散列表:
|地址|关键字|
|----|----|
|0 |40 |
|1 |31 |
|2 |46 |
|3 |17 |
|4 |30 |
|5 |63 |
|6 |10 |
|7 |24 |
|8 |32 |
|9 |49 |
|10 |- |
|11 |- |
|12 |47 |
其中,10 和 11 是因为散列表的地址范围为 0~17,所以 10 和 11 也属于地址范围内。如果按照线性探测法处理冲突,当插入关键字 40 时,发现地址 0 已经被占用了,于是就顺着散列函数的规则往后找,找到了地址 1,发现地址 1 也被占用了,于是就继续往后找,直到找到了地址 12,发现地址 12 没有被占用,于是就将关键字 40 存储在了地址 12 上。当插入其他的关键字时,也是按照这个规则来处理冲突。如果所有的地址都被占用了,就说明散列表已经满了,无法再插入新的关键字。
相关问题
设散列表的地址区间为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
```
注意,在线性探测法中,如果散列表已经被占满,插入新的关键字将失败。因此,在设计散列表时,需要考虑预留一定的空间,以免发生这种情况。
设散列表的地址范围为0~17,散列函数为:h (k)=k mod 16, k为关键字,用线性探测法处理冲突,输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49)造出
这道题目给了我们一个散列函数h(k)=k mod 16,k为关键字。我们需要使用线性探测法来处理冲突,输入关键字序列(10,24,32,17,31,30,46,47,40,63,49)。
首先,我们需要创建一个长度为17的散列表,所有位置初始化为0。
接下来,我们将第一个关键字10插入散列表中,h(10)=10 mod 16=10,表中位置10处为0,因此把10放在位置10上。
接着,我们将24插入散列表。h(24)=24 mod 16=8,表中位置8处为0,因此把24放在位置8上。
再次插入32。h(32)=32 mod 16=0,表中位置0处为0,因此把32放在位置0上。
接下来是17。h(17)=17 mod 16=1,表中位置1处为0,因此把17放在位置1上。
再来是31。h(31)=31 mod 16=15,15处已经有关键字了(10),因此开始线性探测方案:向后找到位置0处为空,把31放在位置0上。
接下来是30。h(30)=30 mod 16=14,14处已经有关键字了(32),因此开始线性探测方案:向后找到位置15处为空,把30放在位置15上。
然后是46。h(46)=46 mod 16=14,14处已经有关键字了(32和30),因此开始线性探测方案:向后找到位置1处为空,把46放在位置1上。
再来是47。h(47)=47 mod 16=15,15处已经有关键字了(10和31),因此开始线性探测方案:向后找到位置2处为空,把47放在位置2上。
然后是40。h(40)=40 mod 16=8,8处已经有关键字了(24),因此开始线性探测方案:向后找到位置9处为空,把40放在位置9上。
接着是63。h(63)=63 mod 16=15,15处已经有关键字了(10、31和47),因此开始线性探测方案:向后找到位置3处为空,把63放在位置3上。
最后是49。h(49)=49 mod 16=1,1处已经有关键字了(17和47),因此开始线性探测方案:向后找到位置2处已经有关键字了(47),然后向后找到位置3处为空,把49放在位置3上。
现在散列表中存储的元素为:
0: 32
1: 17
2: 47
3: 49
4: 0
5: 0
6: 0
7: 0
8: 24
9: 40
10: 10
11: 0
12: 0
13: 0
14: 32
15: 30
因此,答案是:(32, 17, 47, 49, 24, 40, 10, 32, 30)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)