数据结构 第8章 查找(作业)

1、第8章 查找 第第8章章 查找查找 8.1 查找的基本概念查找的基本概念8.2 静态查找表静态查找表 8.3 动态查找表动态查找表 8.4 哈希表哈希表 第8章 查找 8.1 查找的基本概念查找的基本概念 关键字关键字：数据元素的某个数据项的值，用它可以标识列表：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。如果一个关键字可以唯一标识列表中的一个或一组数据元素。如果一个关键字可以唯一标识列表中的一个数据元素，中的一个数据元素， 则称其为则称其为主关键字主关键字，否则为，否则为次关键字次关键字。当数据元素仅有一个数据项时，当数据元素仅有一个数据项时， 数据元素的值就是关键字。

2、数据元素的值就是关键字。 第8章 查找 查找查找：根据给定的关键字值，在查找表中确定一个其关键：根据给定的关键字值，在查找表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在查找表中的字与给定值相同的数据元素，并返回该数据元素在查找表中的位置。若找到相应的数据元素，则称查找是成功的，否则称查位置。若找到相应的数据元素，则称查找是成功的，否则称查找是失败的，此时应返回空地址及失败信息，并可根据要求插找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。入这个不存在的数据元素。 第8章 查找 8.2 静态查找表静态查找表 8.2.1 顺序查找法顺序查找法 顺序查找

3、法的过程是：从表中最后一个记录开始，逐个进顺序查找法的过程是：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，否则查找失败。存储结构通常为顺值比较相等，则查找成功，否则查找失败。存储结构通常为顺序结构，也可为链式结构。序结构，也可为链式结构。 第8章 查找 /静态查找表的顺序存储结构静态查找表的顺序存储结构typedef struct ElemType *elem; /数据元素存储空间基址，建数据元素存储空间基址，建 /表时按实际长度分配，表时按实际长度分配，0号单元留空号单元留空

4、 int length; /表长度表长度 SSTable; 第8章 查找 基于顺序结构的算法如下：基于顺序结构的算法如下： int Search_Seq(SSTable ST, KeyType key) / 在顺序表在顺序表ST中顺序查找其关键字等于中顺序查找其关键字等于key的数据元素。若的数据元素。若 找到，则函数值为该元素在表中的位置，否则为找到，则函数值为该元素在表中的位置，否则为0。算法。算法9.1 int i; ST.elem0.key=key; / 哨兵哨兵 for(i=ST.length;!EQ(ST.elemi.key,key);-i); / 从后往前找从后往前找 retur

5、n i; / 找不到时，找不到时，i为为0 其中其中ST.elem0称为监视哨，可以起到防止越界的作用。称为监视哨，可以起到防止越界的作用。第8章 查找 8.2.2 有序表的查找有序表的查找 折半查找法又称二分法查找法，这种方法适用于有序表。折半查找法又称二分法查找法，这种方法适用于有序表。其基本过程是其基本过程是：将表中间位置记录的关键字与查找关键字比较，：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，前、后两个子表，如果中间位置记录

6、的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。存在为止，此时查找不成功。 第8章 查找 图图8.1 折半查找示意图折半查找示意图 第8章 查找 折半查找的算法如下：折半查找的算法如下： int Search_Bin(SSTable ST, KeyType key) / 在有序表在有序表ST中折半查找其关键字等于中折半查找其关键字等于key的数据元素。若的数据元素。若找到，则函数

7、值为该元素在表中的位置，否则为找到，则函数值为该元素在表中的位置，否则为0。算法。算法9.2 low=1 ; high=ST.length; / 置区间初值置区间初值 while(lowlchild=NULL； free(p)； (2) 若若p结点只有左子树，或只有右子树，则可将结点只有左子树，或只有右子树，则可将p的左的左子树或右子树直接改为其双亲结点子树或右子树直接改为其双亲结点f的左子树，即：的左子树，即：f-lchild=p-lchild（或（或f-lchild=p-rchild）；）； free(p)； (3) 若若p既有左子树，既有左子树， 又有右子树，又有右子树， 如图如图8.6

8、 (a) 所示。所示。 此时有两种处理方法：此时有两种处理方法： 第8章 查找 方法方法1: 首先找到首先找到p结点在中序序列中的直接前驱结点在中序序列中的直接前驱s结点，结点，如图如图8.6 (b) 所示，然后将所示，然后将p的左子树改为的左子树改为f的左子树，而将的左子树，而将p的右子树改为的右子树改为s的右子树：的右子树：f-lchild=p-lchild；s-rchild= p-rchild； free(p)；结果如图；结果如图8.6 (c) 所示。所示。 方法方法2 : 首先找到首先找到p结点在中序序列中的直接前驱结点在中序序列中的直接前驱s结点，结点， 如图如图8.6 (b) 所示

9、，然后用所示，然后用s结点的值替代结点的值替代p结点的值，再将结点的值，再将s结结点删除，原点删除，原s结点的左子树改为结点的左子树改为s的双亲结点的双亲结点q的右子树：的右子树：p-data=s-data；q-rchild= s-lchild；free(s)；结果如图；结果如图8.6 (d) 所示。所示。 第8章 查找 fPLPRPFfp(a) P的左右子树均不空QLSLCFfp(d) 将原P结点的值改为S结点的值，删除原S结点 并将原S的左子树改为Q的右子树QqCLSPRcSLPRCf(c) 将P的 左子树改为F的左子树，将P的右子树改为S的右子树SCLFcQLSLCFpQqCLPPRcS

10、s(b) S为P的直接前驱 图图8.6 二叉排序树删除示意二叉排序树删除示意 第8章 查找 3. 二叉排序树的查找二叉排序树的查找 因为二叉排序树可看作是一个有序表，所以在二叉排因为二叉排序树可看作是一个有序表，所以在二叉排序树上进行查找与折半查找类似，也是一个逐步缩小查找序树上进行查找与折半查找类似，也是一个逐步缩小查找范围的过程。范围的过程。 根据二叉排序树的特点，首先将待查关键字根据二叉排序树的特点，首先将待查关键字k与根结点关键字与根结点关键字t进行比较，如果：进行比较，如果： (1） k=t， 则返回根结点地址；则返回根结点地址； (2） kt， 则进一步查右子树。则进一步查右子树。

11、 第8章 查找 8.3.2 平衡二叉树平衡二叉树 平衡二叉树又称为平衡二叉树又称为AVL树树。一棵平衡二叉树或者是空树，。一棵平衡二叉树或者是空树，或者具有下列性质的二叉排序树：或者具有下列性质的二叉排序树： 左子树与右子树的高度之左子树与右子树的高度之差的绝对值小于等于差的绝对值小于等于1； 左子树和右子树也是平衡二叉树。左子树和右子树也是平衡二叉树。 平衡因子平衡因子：结点的左子树深度与右子树深度之差。：结点的左子树深度与右子树深度之差。 显然，对一棵平衡二叉排序树而言，显然，对一棵平衡二叉排序树而言， 其所有结点的平衡因其所有结点的平衡因子只能是子只能是-1、 0，或，或1。当我们在一个

12、平衡二叉排序树上插入一。当我们在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现绝对值大于个结点时，有可能导致失衡，即出现绝对值大于1的平衡因子，的平衡因子，如如2、-2。图。图8.7中给出了一棵平衡二叉排序树和一棵失去平衡中给出了一棵平衡二叉排序树和一棵失去平衡的二叉排序树。的二叉排序树。 第8章 查找 图图8.7 平衡与不平衡的二叉排序树平衡与不平衡的二叉排序树 208070302560405011110006030255040120058100(a) 一棵平衡二叉排序树(b) 一棵失去平衡的二叉排序树第8章 查找 u 已知一棵平衡二叉排序树如图已知一棵平衡二叉排序树如图8.9（

13、a）所示。在）所示。在A的左子树的左子树的左子树上插入的左子树上插入15后，导致失衡，如图后，导致失衡，如图8.9（b）所示。为恢复）所示。为恢复平衡并保持二叉排序树的特性，可将平衡并保持二叉排序树的特性，可将A改为改为B的右子，的右子，B原来原来的右子改为的右子改为A的左子，如图的左子，如图8.9（c）所示。这相当于以）所示。这相当于以B为轴，为轴，对对A做了一次顺时针旋转。做了一次顺时针旋转。 图图8.9 不平衡二叉树的调整不平衡二叉树的调整(1) 6015302025604010000AB(a) 一棵平衡二叉排序树(b) 插入15后 失去平衡302025604020110AB030152

14、040250000BA01(c) 调整后的二叉排序树第8章 查找 u 已知一棵平衡二叉排序树如图已知一棵平衡二叉排序树如图8.10（a）所示。在）所示。在A的右子树的右子树B的右子树上插入的右子树上插入70后，导致失衡，如图后，导致失衡，如图8.10（b）所示。为恢复）所示。为恢复平衡并保持二叉排序树的特性，平衡并保持二叉排序树的特性， 可将可将A改为改为B的左子，的左子，B原来的原来的左子改为左子改为A的右子，如图的右子，如图8.10（c）所示。这相当于以）所示。这相当于以B为轴，为轴， 对对A做了一次逆时针旋转。做了一次逆时针旋转。 图图8.10 不平衡二叉树的调整不平衡二叉树的调整(2)

15、 30607060302040251000AB(a) 一棵平衡二叉排序树(b) 插入70后失去平衡204025200AB0202560400000BA0(c) 调整后的二叉排序树70111300第8章 查找 u 已知一棵平衡二叉排序树如图已知一棵平衡二叉排序树如图8.11（a）所示。）所示。 在在A的的左子树左子树B的右子树上插入的右子树上插入45后，导致失衡，如图后，导致失衡，如图8.11（b）所示。为恢复平衡并保持二叉排序树的特性，可所示。为恢复平衡并保持二叉排序树的特性，可首先将首先将B改为改为C的左子，而的左子，而C原来的左子改为原来的左子改为B的右子；然后将的右子；然后将A改改为为C

16、的右子，的右子， C原来的右子改为原来的右子改为A的左子，的左子， 如图如图8.11（c）所示。所示。这相当于对这相当于对B做了一次逆时针旋转，做了一次逆时针旋转， 对对A做了一次做了一次顺时针旋转。顺时针旋转。 第8章 查找 图图8.11 不平衡二叉树的调整不平衡二叉树的调整(3) (a) 一棵平衡二叉排序树507000103095204090801000B06085AC0000(b) 插入45后失去平衡507010103095204090802101B06085AC00000458595(c) 调整后的二叉排序树45103090204080600001B05070C00001A00第8章

17、查找 u 已知一棵平衡二叉排序树如图已知一棵平衡二叉排序树如图8.12（a）所示。）所示。 在在A的右的右子树的左子树上插入子树的左子树上插入55后，导致失衡，如图后，导致失衡，如图8.12（b）所示。）所示。 为恢复平衡并保持二叉排序树的特性，可首先将为恢复平衡并保持二叉排序树的特性，可首先将B改为改为C的的右子，右子， 而而C原来的右子改为原来的右子改为B的左子；然后将的左子；然后将A改为改为C的左子，的左子，C原来的左子改为原来的左子改为A的右子，如图的右子，如图8.12（c）所示。这相当于）所示。这相当于对对B做了一次顺时针旋转，做了一次顺时针旋转， 对对A做了一次逆时针旋转。做了一次

18、逆时针旋转。 第8章 查找 图8.12 不平衡二叉树的调整(4) (c) 调整后的二叉排序树(a) 一棵平衡二叉排序树(b) 插入55后失去平衡859550709010208040100003060A00B0000C859550709010208040200003060A11B000C15508595551030902040806000A05070C0001B00100第8章 查找 1） LL型型 图图8.13 二叉排序树的二叉排序树的LL型平衡旋转型平衡旋转 (a) 插入新结点S后 失去平衡(b) 调整后恢复平衡ABBLBRARS21BABLARBRS00第8章 查找 2） LR型型 图8.

19、14 二叉排序树的LR型平衡旋转 (a) 插入新结点 S后失去平衡(b) 调整后恢复平衡ABCLARS2 1CCR1BLCACLARCRS0 1B0BL第8章 查找 图8.15 二叉排序树的RR型平衡旋转 (a) 插入新结点 S后失去平衡(b) 调整后恢复平衡ABBRBLALS 2 1BABRALBLS003） RR型型第8章 查找 4） RL型型 图8.16 二叉排序树的RL型平衡旋转 (b) 调整后恢复平衡(a) 插入新结点 S后失去平衡ABBRCRS 2 1CCL1ALCACRALCLS01B0BR第8章 查找 8.4 哈希表哈希表 哈希法又称散列法、杂凑法或关键字地址计算法哈希法又称散

20、列法、杂凑法或关键字地址计算法等，相应等，相应的表称为哈希表。这种方法的基本思想：首先在元素的关键字的表称为哈希表。这种方法的基本思想：首先在元素的关键字k和元素的存储位置和元素的存储位置p之间建立一个对应关系之间建立一个对应关系H，使得，使得p=H(k)，H称为哈希函数。创建哈希表时，把关键字为称为哈希函数。创建哈希表时，把关键字为k的元素直接存的元素直接存入地址为入地址为H(k)的单元；以后当查找关键字为的单元；以后当查找关键字为k的元素时，再利的元素时，再利用哈希函数计算出该元素的存储位置用哈希函数计算出该元素的存储位置p=H(k)，从而达到按关，从而达到按关键字直接存取元素的目的。键字

21、直接存取元素的目的。 第8章 查找 当关键字集合很大时，关键字值不同的元素可能会映象当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，到哈希表的同一地址上，即即 k1k2，但，但 H（k1）=H（k2），），这种现象称为冲突，此时称这种现象称为冲突，此时称k1和和k2为同义词。为同义词。实际中，冲突实际中，冲突是不可避免的，是不可避免的， 只能通过改进哈希函数的性能来减少冲突。只能通过改进哈希函数的性能来减少冲突。 综上所述，综上所述， 哈希法主要包括以下两方面的内容：哈希法主要包括以下两方面的内容： (1） 如何构造哈希函数；如何构造哈希函数； (2） 如何处理冲突。如何

22、处理冲突。 第8章 查找 8.4.1 哈希函数的构造方法哈希函数的构造方法 1. 直接定址法直接定址法 哈希函数为关键字的线性函数，即哈希函数为关键字的线性函数，即H(key)=key或者或者H(key)=akey+b (a和和b为常数为常数)。 此方法适合于此方法适合于地址集合的大小地址集合的大小=关键字集合的大小关键字集合的大小。 例：例：P253 解放后出生的人口调查表解放后出生的人口调查表第8章 查找 2. 数字分析法数字分析法 如果事先知道关键字集合，并且每个关键字的位数比哈希如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干表的

23、地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。位，构成哈希地址。第8章 查找 例如有例如有80个记录，关键字为个记录，关键字为8位十进制整数位十进制整数d1d2d3d7d8，如哈，如哈希表长取希表长取100，则哈希表的地址空间为：，则哈希表的地址空间为： 0099。假设经过分。假设经过分析，各关键字中析，各关键字中d4和和d7的取值分布较均匀，的取值分布较均匀， 则哈希函数为：则哈希函数为：H(key)=H(d1d2d3d7d8)=d4d7。例如，。例如， H(81346532)=43，H(81301367)=06。 8 1 3 4 6 5 3 28 1 3 7 2 2

24、4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 78 1 3 3 8 9 6 78 1 3 5 4 1 5 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5 数字分布近乎随机数字分布近乎随机,可取其中任意两位或取其中可取其中任意两位或取其中两位与另两位的叠加求和后两位与另两位的叠加求和后舍去进位作哈希地址舍去进位作哈希地址第8章 查找 3. 平方取中法平方取中法 当无法确定关键字中哪几位分布较均匀时，当无法确定关键字中哪几位分布较均匀时， 可以先求出关键可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。字的平方值，然

25、后按需要取平方值的中间几位作为哈希地址。这这是因为：平方后中间几位和关键字中每一位都相关，故不同关键是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。字会以较高的概率产生不同的哈希地址。 第8章 查找 例：我们把英文字母在字母表中的位置序号作为该英文字母的内例：我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例部编码。例K的内部编码为的内部编码为11，E的内部编码为的内部编码为05，Y的内部编的内部编码为码为25，A的内部编码为的内部编码为01, B的内部编码为的内部编码为02。 由此组成关键字由此组成关键字“KEYA”的内部代码为的内部代

26、码为11052501，同理我，同理我们可以得到关键字们可以得到关键字“KYAB”、“AKEY”、 “BKEY”的内部编的内部编码。之后对关键字进行平方运算后，取出第码。之后对关键字进行平方运算后，取出第7到第到第9位作为该关键位作为该关键字哈希地址，字哈希地址， 如表如表8 - 1所示。所示。 第8章 查找 表表8-1 平方取中法求得的哈希地址平方取中法求得的哈希地址 关键字关键字 内部编码内部编码 内部编码的平方值内部编码的平方值 H(k)关键字的哈希地址关键字的哈希地址 KEYA 11052501 122157778355001 778 KYAB 11250102 126564795010

27、404 795AKEY 01110525 001233265775625 265BKEY 02110525 004454315775625 315第8章 查找 4. 折叠法折叠法 将关键字分割成位数相同的几部分将关键字分割成位数相同的几部分(最后一部分位数可不最后一部分位数可不同同)，然后取这几部分的叠加和，然后取这几部分的叠加和(舍去进位舍去进位)作为哈希地址。作为哈希地址。图图8.23 由叠加法求哈希地址由叠加法求哈希地址 2 30 34 71 20 2 0+)1 1 0 52 33 0 64 72 1 10 2 0+) 9 0 7(a) 移位叠加移位叠加 (b) 间界叠加间界叠加 第8章

28、 查找 5. 除留余数法除留余数法 假设哈希表长为假设哈希表长为m，p为小于等于为小于等于m的最大素数，则哈希函的最大素数，则哈希函数为：数为： H(key)= key % p， 其中其中%为模为模p取余运算。取余运算。 例如，已知待散列元素为（例如，已知待散列元素为（18，75，60，43，54，90，46），表长），表长m=10， p=7， 则有则有H(18)=18 % 7=4 H(75)=75 % 7=5 H(60)=60 % 7=4 H(43)=43 % 7=1 H(54)=54 % 7=5 H(90)=90 % 7=6 H(46)=46 % 7=4 第8章 查找 图8.24 除留余数

29、法求哈希地址 此时冲突较多。此时冲突较多。 为减少冲突，为减少冲突， 可取较大的可取较大的m值和值和p值，值， 如如m=p=13， 结果如下：结果如下： H(18)=18 % 13=5 H(75)=75 % 13=10 H(60)=60 % 13=8 H(43)=43 % 13=4 H(54)=54 % 13=2 H(90)=90 % 13=12 H(46)=46 % 13=7 544318466075900 1 2 3 4 5 6 7 8 9 10 11 12 第8章 查找 6. 随机数法随机数法 采用一个随机函数作哈希函数，即采用一个随机函数作哈希函数，即H(key)=random(key

30、)。 在实际应用中，在实际应用中， 应根据具体情况，采用不同的哈希函数。应根据具体情况，采用不同的哈希函数。通常应考虑以下五个因素：通常应考虑以下五个因素： 计算哈希函数所需的时间计算哈希函数所需的时间 关键字的长度。关键字的长度。 哈希表的大小。哈希表的大小。 关键字的分布情况。关键字的分布情况。 记录查找的频率。记录查找的频率。 第8章 查找 8.4.2 处理冲突的方法处理冲突的方法 1. 开放定址法开放定址法 这种方法也称再散列法，其基本思想是：当关键字这种方法也称再散列法，其基本思想是：当关键字key的的哈希地址哈希地址p= H（key）出现冲突时，以）出现冲突时，以p为基础，产生另一

31、个为基础，产生另一个哈希地址哈希地址p1，如果，如果p1仍然冲突，再以仍然冲突，再以p为基础，产生另一个哈为基础，产生另一个哈希地址希地址p2，直到找出一个不冲突的哈希地址，直到找出一个不冲突的哈希地址pi，将相应，将相应元素存入其中。这种方法有一个通用的再散列函数形式：元素存入其中。这种方法有一个通用的再散列函数形式： ,)%)(mdkeyHHiii=1， 2， ， n 第8章 查找 其中其中H(key)为哈希函数，为哈希函数，m为表长，为表长，di称为增量序列。增量称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三序列的取值方式不同，相应的再散列方式也不同。主要有以

32、下三种：种： 线性探测再散列线性探测再散列 di=1，2，3， m-1 这种方法的特点这种方法的特点是：是： 冲突发生时，顺序查看表中下一单元，冲突发生时，顺序查看表中下一单元， 直到找出一个空单元或查遍全表。直到找出一个空单元或查遍全表。 二次探测再散列二次探测再散列 di= 12，-12， 22，-22，k2，-k2 (km/2) 这种方法的特点这种方法的特点是：冲突发生时，在表的左右进行跳跃式探是：冲突发生时，在表的左右进行跳跃式探测，测， 比较灵活。比较灵活。 第8章 查找 伪随机探测再散列伪随机探测再散列 di=伪随机数序列。伪随机数序列。 具体实现时，应建立一个伪随机数发生器，（如

33、具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），）， 并给定一个随机数做起点。并给定一个随机数做起点。 第8章 查找 例，已知哈希表长度例，已知哈希表长度m=11，哈希函数为：，哈希函数为：H(key)= key % 11， 则则H(47)=3，H(26)=4，H(60)=5，假设下一个关键字为，假设下一个关键字为69，则，则H(69)=3，与，与47冲突。如果用线性探测再散列处理冲突，冲突。如果用线性探测再散列处理冲突，下一个哈希地址为下一个哈希地址为H1=（3+1）% 11=4， 仍然冲突，再找下一仍然冲突，再找下一个哈希地址为个哈希地址为H2=(3+2）% 11=5，

34、还是冲突，继续找下一个哈，还是冲突，继续找下一个哈希地址为希地址为H3=（3+3）% 11=6，此时不再冲突，将，此时不再冲突，将69填入填入6号单号单元，参见图元，参见图8.25(a)。 第8章 查找 如果用二次探测再散列处理冲突，下一个哈希地址为如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3+12）% 11=4， 仍然冲突，再找下一个哈希地址为仍然冲突，再找下一个哈希地址为H2=（3-12）% 11=2，此时不再冲突，将，此时不再冲突，将69填入填入2号单元，参号单元，参见图见图8.25(b)。 如果用伪随机探测再散列处理冲突，且伪随机如果用伪随机探测再散列处理冲突，且伪随机数序列为：数序列为：2，5，9则下一个哈希地址为则下一个哈希地址为H1=（3+2）% 11=5，仍然冲突，再找下一个哈希地址为，仍然冲突，再找下一个哈希地址为H2=（3+5）% 11=8，此时