.

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 处理冲突的链接表