数据结构 第八章 查找表 下载本文

同义词的链表,具有上面③的优缺点;后者实际是静态链表,同义词存在同一地址向量空间(从最后向前找空闲单元),以指针相连。节省了空间,但易产生“堆积”,查找效率低。 (4)要在被删除结点的散列地址处作标记,不能物理的删除。否则,中断了查找通路。 (5)记录 负载因子

3.评价哈希函数优劣的因素有:能否将关键字均匀影射到哈希空间上,有无好的解决冲突的方法,计算哈希函数是否简单高效。由于哈希函数是压缩映像,冲突难以避免。 4.哈希方法的平均查找路长主要取决于负载因子(表中实有元素数与表长之比),它反映了哈希表的装满程度,该值一般取0.65~0.9。

5.不一定相邻。哈希地址为i(0≤i≤m-1)的关键字,和为解决冲突形成的探测序列i的同义词,都争夺哈希地址i。 6.

散列地址 0 关键字 14 1 01 1 2 9 1 3 23 2 4 84 5 27 6 55 1 7 20 2 8 9 比较次数 1 3 4 平均查找长度:ASLsucc=(1+1+1+2+3+4+1+2)/8=15/8

以关键字27为例:H(27)=27%7=6(冲突) H1=(6+1)=7(冲突) H2=(6+2)=0(冲突) H3=(6+3)=5 所以比较了4次。 7.由于装填因子为0.8,关键字有8个,所以表长为8/0.8=10。 (1)用除留余数法,哈希函数为H(key)=key % 7 (2)

散列地址 0 关键字 21 1 15 1 2 30 1 3 36 3 4 25 1 5 40 1 6 26 2 7 37 6 8 9 2

3

比较次数 1 (3)计算查找失败时的平均查找长度,必须计算不在表中的关键字,当其哈希地址为i(0≤i≤m-1)时的查找次数。本例中m=10。故查找失败时的平均查找长度为:

ASLunsucc=(9+8+7+6+5+4+3+2+1+1)/10=4.6 ASLsucc =16/8=2 (4)int Delete(int h[n],int k)

// 从哈希表h[n]中删除元素k,若删除成功返回1,否则返回0 {i=k%7;// 哈希函数用上面(1),即H(key)=key % 7

if(h[i]== maxint)//maxint解释成空地址

printf(“无关键字%d\\n”,k);return (0);}

if(h[i]==k){h[i]=-maxint ;return (1);} //被删元素换成最大机器数的负数

else // 采用线性探测再散列解决冲突 {j=i;

for(d=1;d≤n-1;d++)

{i=(j+d)%n; // n为表长,此处为10

if(h[i]== maxint)return (0); //maxint解释成空地址

if(h[i]==k){ h[i]=-maxint ;return (1);} }//for }

printf(“无关键字%d\\n”,k);return (0) } 8.

散列地址 关键字 比较次数 0 1 15 1 2 3 24 1 4 10 2 5 19 1 6 17 4 7 38 5 8 18 5 9 40 5 哈希表a: ASLsucc=24/8=3; 散列地址 关键字 比较次数 0 1 15 1 2 17 3 3 24 1 4 10 2 5 19 1 6 40 2 7 38 4 8 18 4 9 哈希表b: ASLsucc =18/8 9.(1)

散列地址 关键字 比较次数 0 1 2 3 53 1 4 1 2 5 6 41 1 7 67 2 8 46 1 9 10 51 1 11 12 30 1 13 22 1 1 (2)装填因子=9/13=0.7 (3)ASLsucc =11/9 (4)ASLunsucc =29/13 10.常用构造哈希函数的方法有:

(1)数字分析法 该法事先需知道关键字集合,且关键字位数比散列表地址位数多,应选数字分布均匀的位。

(2)平方取中法 将关键字值的平方取中间几位作哈希地址。

(3)除留余数法 H(key)=key%p,通常p取小于等于表长的最大素数。

(4)折叠法 将关键字分成长度相等(最后一段可不等)的几部分,进行移位叠加或间界叠加,其值作哈希地址。

(5)基数转换法 两基数要互素,且后一基数要大于前一基数。

在哈希表中删除一个记录,在拉链法情况下可以物理地删除。在开放定址法下,不能物理地删除,只能作删除标记。该地址可能是该记录的同义词查找路径上的地址,物理的删除就中断了查找路径。因为查找时碰到空地址就认为是查找失败。

散列地址 关键字 比较次数 11.(1)

散列地址 0 关键字 1 4 1 2 3 12 1 4 49 1 5 38 2 6 13 1 7 24 2 8 32 1 9 21 2 10 14 01 68 27 55 19 20 84 79 23 11 10 1 2 1 4 3 1 1 3 9 1 1 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 比较次数 ASLsucc =(1+1+1+2+1+2+1+2)/8=11/8

ASLunsucc=(1+2+1+8+7+6+5+4+3+2+1)/11=40/11

(2)ASLsucc =11/8 ASLunsucc=19/11 ASLsucc=13/8 ASLunsucc=19/11

值得指出,对用拉链法求查找失败时的平均查找长度有两种观点。其一,认为比较到空指针算失败。以本题为例,哈希地址0、2、5、7、9和10均为比较1次失败,而哈希地址1和3比较2次失败,其余哈希地址均为比较3次失败,因此,查找失败时的平均查找长度为19/11,我们持这种观点。还有另一种理解,他们认为只有和关键字比较才计算比较次数,而和空指针比较不计算。照这种观点,本题的ASLunsucc=(1+1+2+2+2)/11=8/11

12.由hashf(x)=x mod 11 可知,散列地址空间是0到10,由于有8个数据,装载因子取0.7。

(1)

散列地址 0 关键字 33 1 1 1 2 13 1 3 12 3 4 34 4 5 38 1 6 27 2 7 22 8 8 9 10 比较次数 1 ASLsucc=21/8 ASLunsucc=47/11 13.

(1)ASL=42/12

(2)a:ASLsucc=31/12 (2)b:ASLsucc=18/12 (注:本题[x]取小于等于x的最大整数)

14.ASLsucc =15/10 15.ASLsuss =16/11 16.

散列地址 0 关键字 1 2 3 4 5 6 7 8 9 10 11 231 89 79 25 47 16 38 82 51 39 151 1 1 1 2 1 2 3 2 4 3 比较次数 1 ASLsucc =21/11 17.

散列地址 0 关键字 22 1 33 2 2 46 1 3 13 2 4 01 4 5 67 5 6 7 8 41 1 9 53 1 10 30 3 比较次数 1 18. (1) 散列地址 关键字 比较次数 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 30 31 46 47 1 1 3 3 32 17 63 49 24 40 10 1 1 6 3 1 2 1 (2)查找关键字63,H(k)=63 MOD 16=15,依次与31,46,47,32,17,63比较。 (3)查找关键字60,H(k)=60 MOD 16=12,散列地址12内为空,查找失败。 (4)ASLsucc=23/11