.
d2j?1=( d1-j*j) % m； j=1，2，... 其计算函数如下：
H(19)=19 % 13=6 H(01)=01 % 13=1 H(23)=23 % 13=10 H(14)=14 % 13=1 (冲突) H(14)=(1+1*1) % 19=2 H(55)=55 % 13=3 H(20)=20 % 13=7 H(84)=84 % 13=6 (冲突) H(84)=(6+1*1) % 19=7 (仍冲突) H(84)=(6-1*1) % 19=5 H(27)=27 % 13=1 (冲突)
H(27)=(1+1*1) % 19=2 (冲突) H(27)=(1-1) % 19=0 H(68)=68 % 13=3 (冲突) H(68)=(3+1*1) % 19=4 H(11)=11 % 13=11 H(10)=10 % 13=10 (冲突) H(10)=(10+1*1) % 19=11 (仍冲突) H(10)=(10-1*1) % 19=9 H(77)=77 % 13=12
因此：各关键字的记录对应的地址分配如下： addr(27)=0
addr(01)=1 addr(14)=2 addr(55)=3 addr(68)=4 addr(84)=5 addr(19)=6 addr(20)=7 addr(10)=9 addr(23)=10 addr(11)=11 addr(77)=12
其他地址为空。
Word 资料
.
综合题
1.设散列表为 T［0..12］，散列函数为 H（key）= key，给定键值序列是｛39，36，28，38，44，15，42，12，06，25｝，请画出分别用拉链法和线性探查法处理冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和查找失败时的平均查找长度。 解 用散列函数 H（key）= key% 13计算出键值序列的散列地址。并用探查次数表示待查键值需对散列表中键值比较次数。
键值序列：｛39，36，28，38，44，15，42，12，06，25｝ 散列地址： 0，10，2，12，5，2，3，12，6，12 （1）线性探查法处理冲突
用线性探查法处理冲突构造的散列表见表8-1所示。
表8-1 用线性探查法处理冲突构造的散列表
下标 T［0..12］ 查找成功探查次数 查找失败探查次数
0 1 9
1 3 8
2 1 7
3 2 6
4 42 2 5
5 44 1 4
6 1 3
7 9 2
8 1
9 1
10 36 1 2
11 1
12 38 1 10
39 12 28 15 06 25
在等概率的情况下，查找成功的平均查找长度 ASL=（1×6+2×2+3×1+9×1）/10=2.2
设待查键值 k不在散列表中：若 H（k）= k% 13= d，则从 i=d开始顺次与 T［i］位置的键值进行比较，直到遇到空位，才确定其查找失败，同时累计 k键值的比较次数，例如若 k% 13= 0，则必须将 k与 T［0］、T［1］、…、T［8］中的键值进行比较之后，发现 T［8］为空，比较次数为 9、类似地可对 k% 13=1，2，3，…，12进行分析可得查找失败的平均查找长度。
ASL =（9+8+7+6+5+4+3+2+1+1+10）/13 = 59/13 = 4.54 （2）拉链法处理冲突
用拉链法处理冲突构造的散列表见图8-2所示。
Word 资料
.
图8-2 拉链法处理冲突构造的散列表
在等概率的情况下查找成功的平均查找长度： ASL=（1×7+2×2+3×1）/10=1.4
设待查键值 k不在散列表中，若 k% 13= d。则需在 d链表中查找键值为 k的结点，直到表尾，若不存在则查找失败，设 d链表中有 i个结点，则 k需与表中键值比较 i次，查找失败的平均长度为：
ASL=（1+ 0+ 2+ 1+ 0+ 1+ 1+ 0+0+0+1+0+3）/13=10/13 = 0.77
2.线性表的关键字集合{87，25，310，08，27，132，68，95，187，123，70，63，7}，共有 13 个元素，已知散列函数为：H(k) = k % 13 ，采用拉链法处理冲突。设计出这种链表结构，并计算该表的成功查找的平均查找长度。 解：依题意，得到：
H(87)=87 % 13=9 H(25)=25 % 13=12 H(310)=310 % 13=11 H(08)=08 % 13=8 H(27)=27 % 13=1 H(132)=132 % 13=2 H(68)=68 % 13=3 H(95)=95 % 13=4 H(187)=187 % 13=5 H(123)=123 % 13=6 H(70)=70 % 13=5 H(63)=63 % 13=11
Word 资料
.
H(47)=47 % 13=8
Word 资料采用拉链法处理冲突的表如图8-3 所示。成功查找的平均查找长度： ASL=(1×10+2×3)/13=16/13=1
313 0
1 27 ^ 2 132 ^ 3
68 ^ 4 95 ^ 5 70 187 ^ 6 123 ^ 7 8 08 47 ^ 9
87 ^ 10 11 63 310 ^ 12
25 ^ 图8.3 处理冲突的链接表
相关推荐：
loading