设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为:H(key)=key % 17,采用线性测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表,并计算成功查找的平均查找度。手写过程
时间: 2023-06-23 12:10:26 浏览: 32
首先,我们需要创建一个长度为17的散列表,用于存储关键字。
| | | | | | | | | | | | | | | | | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| | | | | | | | | | | | | | | | | |
接下来,我们将每个关键字插入散列表中。如果出现冲突,则采用线性探测法依次往后查找空闲位置。
| 2 | 3 | | | | 6 | | | 9 | | | | | | | | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|29 |01 | | | |20 |13 |15 |69 | 9 |10 | | |56 |74 |27 |87 |
现在,我们可以计算成功查找的平均查找度。假设我们要查找关键字20,首先计算H(20) = 20 % 17 = 3,发现散列表的第3个位置存储的是空值,因此我们需要继续往后查找。下一个位置是4,但是它也是空的。最终,我们在第5个位置找到了关键字20。因此,平均查找度为(1+2+1+1+1)/17 = 0.35。
需要注意的是,平均查找度越小,散列表的性能就越好。因此,在实际应用中,我们需要根据数据集的特点来选择合适的散列函数和解决冲突的方法,以达到最小化平均查找度的目的。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)