S
socool_100
Unregistered / Unconfirmed
GUEST, unregistred user!
数据结构大作业
题目：散列表综合实验
要求：
1）分别编制开散列表和闭散列表的建表和查找算法
2）散列函数都用除余法，开散列表的散列函数取成与闭散列表相同。
3）对闭散列表，分别用线性探查、二次探查解决冲突。
4）用随机函数生成关键字。
5）分别改变关键字的个数n＝10，100，1000和装填因子α＝0.6、0.8、0.95，计算出等概率情况下查找成功和不成功时的平均查找长度（不是用理论公式计算！），填写如下3个表格：
α＝0.6
n＝10 n＝100 n＝1000
成功 不成功 成功 不成功 成功 不成功
线性探查
二次探查
随机探查
双散列函数探查
拉链法
α＝0.8
n＝10 n＝100 n＝1000
成功 不成功 成功 不成功 成功 不成功
线性探查
二次探查
随机探查
双散列函数探查
拉链法
α＝0.95
n＝10 n＝100 n＝1000
成功 不成功 成功 不成功 成功 不成功
线性探查
二次探查
随机探查
双散列函数探查
拉链法
提示：各种散列表不要各自单独作为1个程序，否则实验起来会很繁琐。可以将各种散列方法写在一个程序里，这样程序每运行一次就得到一组结果，整个作业只需运行9次程序就可以了。
另外，如果能补充其它α和n值的实验结果，可以考虑加分(但不作特别要求)。
6）结果分析(包括与理论公式的比较)。
7）作业上交形式：文档＋盘
注意：（a）文档不是程序的简单打印，也不是程序的使用说明书！而应有比较详细的原理和算法说明、结果分析等等。其中的一些细节、技巧、改进等对成绩有重要影响。
（b）不能互相抄袭，否则计0分(可以互相探讨、借鉴)
（c）不要在同一张盘上存放其它作业！（如操作系统、数据库等）
（d）下学期开学第2周交。
（e）文档开头写明：
教学点：
学号：
姓名：
email：
附：
例：对关键字序列{11,78,10,1,3,2,4,21}设计散列表。
这里n=8，尚需决定散列表长度m和散列函数的除数P。在闭散列表中一般令装填因子 <1以减少冲突，现初步取 =0.75，则散列表长度 ，即散列表为HT[11]，即HT[0..10]。此时实际装填因子为 =8/11=0.727，与预设值差别不大。用除余法构造散列函数，因m=11，故选P=11(取m长度范围内的最大素数)，即散列函数为H(key)=key％11。
首先求出散列地址，见下图(a)，据此得到闭散列表和开散列表分别见下图(b)和(c)。
注意：线性探查法构造的散列表为闭散列表，拉链法则为开散列表。
对线性探查法构造的闭散列表，查找成功的平均比较次数为：
ASL＝(1＋1＋2＋1＋3＋2＋8＋l)／8＝2.375
查找不成功的平均查找长度为：
ASLunsucc＝(8＋7＋6＋5＋4＋3＋2＋1＋1＋1＋9)／11≈4.273
闭散列表装填因子α=8/11=0.727，若用公式计算，则
ASL≈ ＝2.333
ASLunsucc＝ =7.222
对拉链法构造的开散列表，查找成功的平均比较次数为：
ASL＝(1×6＋2×2)／8＝l.25
查找不成功的平均查找长度为：
ASLunsucc＝(1＋2＋1＋1＋1＋0＋0＋0＋0＋0＋2)／11≈0.727
开散列表装填因子α=8/11=0.727，若用公式计算，则
ASL≈ ＝1.364
ASLunsucc＝ =1.210
题目：散列表综合实验
要求：
1）分别编制开散列表和闭散列表的建表和查找算法
2）散列函数都用除余法，开散列表的散列函数取成与闭散列表相同。
3）对闭散列表，分别用线性探查、二次探查解决冲突。
4）用随机函数生成关键字。
5）分别改变关键字的个数n＝10，100，1000和装填因子α＝0.6、0.8、0.95，计算出等概率情况下查找成功和不成功时的平均查找长度（不是用理论公式计算！），填写如下3个表格：
α＝0.6
n＝10 n＝100 n＝1000
成功 不成功 成功 不成功 成功 不成功
线性探查
二次探查
随机探查
双散列函数探查
拉链法
α＝0.8
n＝10 n＝100 n＝1000
成功 不成功 成功 不成功 成功 不成功
线性探查
二次探查
随机探查
双散列函数探查
拉链法
α＝0.95
n＝10 n＝100 n＝1000
成功 不成功 成功 不成功 成功 不成功
线性探查
二次探查
随机探查
双散列函数探查
拉链法
提示：各种散列表不要各自单独作为1个程序，否则实验起来会很繁琐。可以将各种散列方法写在一个程序里，这样程序每运行一次就得到一组结果，整个作业只需运行9次程序就可以了。
另外，如果能补充其它α和n值的实验结果，可以考虑加分(但不作特别要求)。
6）结果分析(包括与理论公式的比较)。
7）作业上交形式：文档＋盘
注意：（a）文档不是程序的简单打印，也不是程序的使用说明书！而应有比较详细的原理和算法说明、结果分析等等。其中的一些细节、技巧、改进等对成绩有重要影响。
（b）不能互相抄袭，否则计0分(可以互相探讨、借鉴)
（c）不要在同一张盘上存放其它作业！（如操作系统、数据库等）
（d）下学期开学第2周交。
（e）文档开头写明：
教学点：
学号：
姓名：
email：
附：
例：对关键字序列{11,78,10,1,3,2,4,21}设计散列表。
这里n=8，尚需决定散列表长度m和散列函数的除数P。在闭散列表中一般令装填因子 <1以减少冲突，现初步取 =0.75，则散列表长度 ，即散列表为HT[11]，即HT[0..10]。此时实际装填因子为 =8/11=0.727，与预设值差别不大。用除余法构造散列函数，因m=11，故选P=11(取m长度范围内的最大素数)，即散列函数为H(key)=key％11。
首先求出散列地址，见下图(a)，据此得到闭散列表和开散列表分别见下图(b)和(c)。
注意：线性探查法构造的散列表为闭散列表，拉链法则为开散列表。
对线性探查法构造的闭散列表，查找成功的平均比较次数为：
ASL＝(1＋1＋2＋1＋3＋2＋8＋l)／8＝2.375
查找不成功的平均查找长度为：
ASLunsucc＝(8＋7＋6＋5＋4＋3＋2＋1＋1＋1＋9)／11≈4.273
闭散列表装填因子α=8/11=0.727，若用公式计算，则
ASL≈ ＝2.333
ASLunsucc＝ =7.222
对拉链法构造的开散列表，查找成功的平均比较次数为：
ASL＝(1×6＋2×2)／8＝l.25
查找不成功的平均查找长度为：
ASLunsucc＝(1＋2＋1＋1＋1＋0＋0＋0＋0＋0＋2)／11≈0.727
开散列表装填因子α=8/11=0.727，若用公式计算，则
ASL≈ ＝1.364
ASLunsucc＝ =1.210