除留取余法将11,13,20,21,50,5放在长度为10的顺序表,最后计算该散列上查找成功的平均比较次数
时间: 2024-06-13 12:08:37 浏览: 59
顺序表二叉树和删除查找,计算平均查找长度的功能
4星 · 用户满意度95%
根据引用[1]中的要求,我们需要使用除留余数法和线性探测法来设计散列表。具体步骤如下:
1. 创建一个长度为n的散列表,初始化所有元素为空。
2. 对于每个关键字key,计算其散列值hash(key) = key % n。
3. 如果散列表中hash(key)位置为空,则将key插入该位置。
4. 如果散列表中hash(key)位置已经被占用,则使用线性探测法,依次检查hash(key)+1, hash(key)+2, ...,直到找到一个空位置插入key。
5. 查找关键字key时,计算其散列值hash(key),依次检查散列表中hash(key), hash(key)+1, hash(key)+2, ...,直到找到key或者遇到一个空位置。
根据题目中的数据,我们可以将11,13,20,21,50,5插入长度为10的散列表中,具体过程如下:
1. 创建一个长度为10的散列表,初始化所有元素为空。
2. 对于每个关键字key,计算其散列值hash(key) = key % 10。
- 11的散列值为1
- 13的散列值为3
- 20的散列值为0
- 21的散列值为1
- 50的散列值为0
- 5的散列值为5
3. 将关键字插入散列表中,如果位置已经被占用,则使用线性探测法。
- 20插入位置0
- 11插入位置1
- 21插入位置2
- 13插入位置3
- 50插入位置4
- 5插入位置5
4. 计算查找成功的平均比较次数。根据题目中的数据,我们需要查找的关键字为13,其散列值为3。依次检查散列表中位置3,4,5,6,7,8,9,0,1,2,直到找到13或者遇到一个空位置。因为13在位置3上,所以查找成功,比较次数为3。同理,我们可以计算出查找11,20,21,50,5的比较次数分别为1,1,2,1,1。因此,查找成功的平均比较次数为(3+1+1+2+1+1)/6=1.5。
阅读全文