设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为:H(key)=key 00000000% 17,采用线性测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表,并计算成功查找的平均查找度。手写过程在0到18的散列地址空间中
时间: 2023-06-23 14:09:45 浏览: 197
首先,我们需要创建一个长度为 19 的散列表,以便能够存储所有的关键字。
在进行散列时,我们需要使用散列函数 H(key) = key % 17,将每个关键字映射到 0 到 16 的散列地址空间中。
关键字 29 映射到散列地址 12,存储在散列表中的第 12 个位置。关键字 01 映射到散列地址 1,存储在散列表中的第 1 个位置。接下来,我们按照相同的方式处理每个关键字。
当出现冲突时,我们使用线性探测法解决。也就是说,如果散列函数计算出的地址已经被占用,则我们检查下一个地址,直到找到一个空闲的位置为止。
例如,当我们处理关键字 15 时,散列函数计算出的地址为 15 % 17 = 15,但该位置已经被关键字 01 占用了。因此,我们检查下一个位置,即散列地址 16。这个位置也被占用了,所以我们继续检查下一个位置,即散列地址 0。这个位置是空闲的,所以我们将关键字 15 存储在散列表的第 0 个位置。
下面是根据上述方法构造的散列表:
| 索引 | 关键字 |
|------|--------|
| 0 | 15 |
| 1 | 01 |
| 2 | 13 |
| 3 | 74 |
| 4 | 56 |
| 5 | 20 |
| 6 | 87 |
| 7 | 27 |
| 8 | 69 |
| 9 | 9 |
| 10 | 10 |
| 11 | 29 |
| 12 | 空 |
| 13 | 空 |
| 14 | 空 |
| 15 | 空 |
| 16 | 空 |
| 17 | 空 |
| 18 | 空 |
现在,我们计算成功查找的平均查找长度。这可以通过将每个关键字的查找长度相加,然后除以关键字总数来完成。
在这个例子中,共有 12 个关键字。下面是每个关键字的查找长度:
| 关键字 | 查找长度 |
|--------|----------|
| 29 | 0 |
| 01 | 0 |
| 13 | 0 |
| 15 | 0 |
| 56 | 0 |
| 20 | 0 |
| 87 | 0 |
| 27 | 0 |
| 69 | 0 |
| 9 | 0 |
| 10 | 0 |
| 74 | 0 |
因为每个关键字都直接存储在散列表中,所以每个关键字的查找长度都是 0。
因此,所有关键字的查找长度之和为 0,平均查找长度也为 0。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)