(1)自动生成包含数十、数百、数千正整数的若干集合,作为构建不同规模查找表的基础; (2)根据(1)中生成的正整数集合构造散列表,采用除留余数法H(key) = key % p (p<m) 作为散列函数,采用开放地址法处理冲突,测量不同规模散列表的查找平均查找长度; (3)基于散列表的工作原理,采用除留余数法H(key) = key % p (p<m) 作为散列函数,采用链地址法处理冲突,采用控制变量的原理设计实验并观测实验结果,探明散列表的长度m、散列函数的除数p,散列表的装填因子对散列函数平均查找长度的影响规律,形成结论。
时间: 2023-07-14 14:14:02 浏览: 223
python 判断输入的正整数是不是回文数 示例
5星 · 资源好评率100%
这是一个基于散列表的实验,主要涉及散列函数、冲突处理方式、散列表长度、装填因子等概念。具体步骤如下:
1. 自动生成包含数十、数百、数千正整数的若干集合,作为构建不同规模查找表的基础。
2. 根据生成的正整数集合构造散列表。采用除留余数法H(key) = key % p (p<m) 作为散列函数,采用开放地址法处理冲突。测量不同规模散列表的查找平均查找长度。可以通过计算实际查找次数除以总查找次数来得到平均查找长度。
3. 基于散列表的工作原理,采用除留余数法H(key) = key % p (p<m) 作为散列函数,采用链地址法处理冲突。采用控制变量的原理设计实验并观测实验结果,探明散列表的长度m、散列函数的除数p,散列表的装填因子对散列函数平均查找长度的影响规律,形成结论。
在实验过程中,需要注意以下几点:
1. 生成的正整数集合应该尽可能地具有随机性,可以利用随机数生成器来生成。
2. 开放地址法的处理方式有很多种,如线性探测、二次探测、双重散列等,需要按照要求选择一种合适的方式。
3. 实验中应该控制变量,只改变一个参数,如散列表长度、散列函数的除数、装填因子等,来观测其对平均查找长度的影响。同时,应该进行多组实验,取平均值来减小误差。
4. 实验结果应该进行统计分析,如绘制图表、计算相关系数等,来验证结论的可靠性。
阅读全文