已知一个列表长为12,关键字的线性序列为53 17 19 61 98 75 79 63 46 49,假定采用h(key)=key%11,若采用线性探测法处理冲突,构造出该散列表
时间: 2024-02-19 11:00:33 浏览: 117
选取哈西函数h(k)=k%11,用线性探测在散列方法处理冲突。是
5星 · 资源好评率100%
根据给定的哈希函数h(key)=key%11和线性探测法,可以按照以下步骤构造该散列表:
1. 创建一个长度为11的数组,用于存放关键字。
2. 将数组中所有元素初始化为空位(null)。
3. 依次将线性序列中的关键字插入到散列表中。对于每个关键字,计算其哈希值h(key),如果对应的数组位置为空,则将关键字插入到该位置;否则,按照线性探测法,依次检查下一个位置,直到找到一个空位。
4. 插入完所有关键字后,散列表的构造就完成了。
根据上述步骤,可以得到以下散列表(其中“-”表示空位):
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|53 |17 |46 |79 |98 |75 |19 |63 |- |- |49 |
其中,关键字53、17、46、79、98、75、19、63、和49分别对应数组下标0、1、2、3、4、5、6、7、10,而关键字61和关键字46都发生了冲突,需要按照线性探测法依次往后查找空位,最终关键字61插入到了下标8的位置。
阅读全文