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

《数据结构-第8章-查找(作业).ppt》由会员分享，可在线阅读，更多相关《数据结构-第8章-查找(作业).ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、于顺序结构的算法如下：intSearch_Seq(SSTableST,KeyTypekey)/在顺序表在顺序表ST中顺序查找其关键字等于中顺序查找其关键字等于key的数据元素。若的数据元素。若找到，则函数值为该元素在表中的位置，否则为找到，则函数值为该元素在表中的位置，否则为0。算法。算法9.1inti;ST.elem0.key=key;/哨兵哨兵for(i=ST.length;!EQ(ST.elemi.key,key);-i);/从后往前找从后往前找returni;/找不到时，找不到时，i为为0其中其中ST.elem0称为监视哨，可以起到防止越界的作用。称为监视哨，可以起到防止越界的作用。第

5、8章 查找 8.2.2 有序表的查找有序表的查找 折折半半查查找找法法又又称称二二分分法法查查找找法法，这这种种方方法法适适用用于于有有序序表表。其其基基本本过过程程是是：将将表表中中间间位位置置记记录录的的关关键键字字与与查查找找关关键键字字比比较较，如如果果两两者者相相等等，则则查查找找成成功功；否否则则利利用用中中间间位位置置记记录录将将表表分分成成前前、后后两两个个子子表表，如如果果中中间间位位置置记记录录的的关关键键字字大大于于查查找找关关键键字字，则则进进一一步步查查找找前前一一子子表表，否否则则进进一一步步查查找找后后一一子子表表。重重复复以以上上过过程程，直直到到找找到到满满足

6、足条条件件的的记记录录，使使查查找找成成功功，或或直直到到子子表表不不存在为止，此时查找不成功。存在为止，此时查找不成功。第8章 查找 图图8.1折半查找示意图折半查找示意图第8章 查找 折半查找的算法如下：折半查找的算法如下：intSearch_Bin(SSTableST,KeyTypekey)/在有序表在有序表ST中折半查找其关键字等于中折半查找其关键字等于key的数据元素。若的数据元素。若找到，则函数值为该元素在表中的位置，否则为找到，则函数值为该元素在表中的位置，否则为0。算法。算法9.2low=1;high=ST.length;/置区间初值置区间初值while(lowlchild=N

7、ULL；free(p)；(2)若若p结结点点只只有有左左子子树树，或或只只有有右右子子树树，则则可可将将p的的左左子子树树或或右右子子树树直直接接改改为为其其双双亲亲结结点点f的的左左子子树树，即即：f-lchild=p-lchild（或（或f-lchild=p-rchild）；）；free(p)；(3)若若p既有左子树，既有左子树，又有右子树，又有右子树，如图如图8.6(a)所示。所示。此时有两种处理方法：此时有两种处理方法：第8章 查找 方方法法1:首首先先找找到到p结结点点在在中中序序序序列列中中的的直直接接前前驱驱s结结点点，如如图图8.6(b)所所示示，然然后后将将p的的左左子子树树

8、改改为为f的的左左子子树树，而而将将p的的右右子子树树改改为为s的的右右子子树树：f-lchild=p-lchild；s-rchild=p-rchild；free(p)；结果如图结果如图8.6(c)所示。所示。方方法法2:首首先先找找到到p结结点点在在中中序序序序列列中中的的直直接接前前驱驱s结结点点，如如图图8.6(b)所所示示，然然后后用用s结结点点的的值值替替代代p结结点点的的值值，再再将将s结结点点删删除除，原原s结结点点的的左左子子树树改改为为s的的双双亲亲结结点点q的的右右子子树树：p-data=s-data；q-rchild=s-lchild；free(s)；结结果果如如图图8.

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

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

11、一个个结结点点时时，有有可可能能导导致致失失衡衡，即即出出现现绝绝对对值值大大于于1的的平平衡衡因因子子，如如2、-2。图图8.7中中给给出出了了一一棵棵平平衡衡二二叉叉排排序序树树和和一一棵棵失失去去平平衡衡的二叉的二叉排序树。排序树。第8章 查找 图图8.7平衡与不平衡的二叉排序树平衡与不平衡的二叉排序树第8章 查找 u已已知知一一棵棵平平衡衡二二叉叉排排序序树树如如图图8.9（a）所所示示。在在A的的左左子子树树的的左左子子树树上上插插入入15后后，导导致致失失衡衡，如如图图8.9（b）所所示示。为为恢恢复复平平衡衡并并保保持持二二叉叉排排序序树树的的特特性性，可可将将A改改为为B的的右

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

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

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

15、改为为A的的右右子子，如如图图8.12（c）所所示示。这这相相当当于于对对B做了一次顺时针旋转，做了一次顺时针旋转，对对A做了一次逆时针旋转。做了一次逆时针旋转。第8章 查找 图8.12 不平衡二叉树的调整(4)第8章 查找 1）LL型型图图8.13二叉排序树的二叉排序树的LL型平衡旋转型平衡旋转第8章 查找 2）LR型型图8.14 二叉排序树的LR型平衡旋转 第8章 查找 图8.15 二叉排序树的RR型平衡旋转 3）RR型型第8章 查找 4）RL型型图8.16 二叉排序树的RL型平衡旋转 第8章 查找 8.4哈希表哈希表哈哈希希法法又又称称散散列列法法、杂杂凑凑法法或或关关键键字字地地址址计

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

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

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

19、如有有80个个记记录录，关关键键字字为为8位位十十进进制制整整数数d1d2d3d7d8，如如哈哈希希表表长长取取100，则则哈哈希希表表的的地地址址空空间间为为：0099。假假设设经经过过分分析析，各各关关键键字字中中d4和和d7的的取取值值分分布布较较均均匀匀，则则哈哈希希函函数数为为：H(key)=H(d1d2d3d7d8)=d4d7。例例如如，H(81346532)=43，H(81301367)=06。813465328137224281387422813013678132281781338967813541578136853781419355数字分布近乎随机数字分布近乎随机,可取其中任

20、意两位或取其中可取其中任意两位或取其中两位与另两位的叠加求和后两位与另两位的叠加求和后舍去进位作哈希地址舍去进位作哈希地址第8章 查找 3.平方取中法平方取中法当当无无法法确确定定关关键键字字中中哪哪几几位位分分布布较较均均匀匀时时，可可以以先先求求出出关关键键字字的的平平方方值值，然然后后按按需需要要取取平平方方值值的的中中间间几几位位作作为为哈哈希希地地址址。这这是是因因为为：平平方方后后中中间间几几位位和和关关键键字字中中每每一一位位都都相相关关，故故不不同同关关键键字会以较高的概率产生不同的哈希地址。字会以较高的概率产生不同的哈希地址。第8章 查找 例例：我我们们把把英英文文字字母母在

21、在字字母母表表中中的的位位置置序序号号作作为为该该英英文文字字母母的的内内部部编编码码。例例K的的内内部部编编码码为为11，E的的内内部部编编码码为为05，Y的的内内部部编编码码为为25，A的内部编码为的内部编码为01,B的内部编码为的内部编码为02。由由此此组组成成关关键键字字“KEYA”的的内内部部代代码码为为11052501，同同理理我我们们可可以以得得到到关关键键字字“KYAB”、“AKEY”、“BKEY”的的内内部部编编码码。之之后后对对关关键键字字进进行行平平方方运运算算后后，取取出出第第7到到第第9位位作作为为该该关关键键字字哈哈希希地址，地址，如表如表8-1所示。所示。第8章

22、查找 表表8-1平方取中法求得的哈希地址平方取中法求得的哈希地址关键字关键字内部编码内部编码内部编码的平方值内部编码的平方值H(k)关键字的哈希地址关键字的哈希地址KEYA11052501122157778355001778KYAB11250102126564795010404795AKEY01110525001233265775625265BKEY02110525004454315775625315第8章 查找 4.折叠法折叠法将关键字分割成位数相同的几部分将关键字分割成位数相同的几部分(最后一部分位数可不最后一部分位数可不同同)，然后取这几部分的叠加和，然后取这几部分的叠加和(舍去进位舍去

23、进位)作为哈希地址。作为哈希地址。图图8.23由叠加法求哈希地址由叠加法求哈希地址1236032471122020+)1105123306247211020+)907(a)移位叠加移位叠加(b)间界叠加间界叠加第8章 查找 5.除留余数法除留余数法假假设设哈哈希希表表长长为为m，p为为小小于于等等于于m的的最最大大素素数数，则则哈哈希希函函数为：数为：H(key)=key%p，其中其中%为模为模p取余运算。取余运算。例例如如，已已知知待待散散列列元元素素为为（18，75，60，43，54，90，46），表长），表长m=10，p=7，则有则有H(18)=18%7=4H(75)=75%7=5H(6

24、0)=60%7=4H(43)=43%7=1H(54)=54%7=5H(90)=90%7=6H(46)=46%7=4第8章 查找 图8.24 除留余数法求哈希地址 此时冲突较多。此时冲突较多。为减少冲突，为减少冲突，可取较大的可取较大的m值和值和p值，值，如如m=p=13，结果如下：结果如下：H(18)=18%13=5H(75)=75%13=10H(60)=60%13=8H(43)=43%13=4H(54)=54%13=2H(90)=90%13=12H(46)=46%13=7544318466075900 1 2 3 4 5 6 7 8 9 10 11 12 第8章 查找 6.随机数法随机数法采

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

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

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

28、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，还还是是冲冲突突，继继续续找找下下一一个个哈哈希希地地址址为为H3=（3+3）%11=6，此

29、此时时不不再再冲冲突突，将将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，仍仍然然冲冲突突，再再找找下下一一个

30、个哈哈希希地地址址为为H2=（3+5）%11=8，此此时时不再冲突，将不再冲突，将69填入填入8号单号单元，参见图元，参见图8.25(c)。第8章 查找 图图8.25开放定址法处理冲突开放定址法处理冲突472660690 1 2 3 4 5 6 7 8 9 10694726600 1 2 3 4 5 6 7 8 9 10472660690 1 2 3 4 5 6 7 8 9 10第8章 查找 2.再哈希法再哈希法这种方法是同时构造多个不同的哈希函数：这种方法是同时构造多个不同的哈希函数：Hi=RHi（key），），i=1，2，kRHi均均是是不不同同的的哈哈希希函函数数。当当哈哈希希地地址址H

31、i=RH1（key）发发生生冲冲突突时时，再再计计算算Hi=RH2（key）直直到到冲冲突突不不再再产产生生。这种方法不易产生聚集，但增加了计算时间。这种方法不易产生聚集，但增加了计算时间。第8章 查找 3.链地址法链地址法基基本本思思想想是是将将所所有有哈哈希希地地址址为为i的的元元素素构构成成一一个个称称为为同同义义词词链链的的单单链链表表，并并将将单单链链表表的的头头指指针针存存在在哈哈希希表表的的第第i个个单单元元中中，因因而而查查找找、插插入入和和删删除除主主要要在在同同义义词词链链中中进进行行。链链地地址址法法适适用用于于经常进行插入和删除的情况。经常进行插入和删除的情况。第8章

32、查找 图图8.26链地址法处理冲突时的哈希表链地址法处理冲突时的哈希表例如，已知一组关键字例如，已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），），哈哈希表长度为希表长度为13，哈希函，哈希函数为：数为：H（key）=key%13，则用链地址法处理冲突则用链地址法处理冲突的结果如图的结果如图8.26所示。所示。第8章 查找 4.建立公共溢出区建立公共溢出区这这种种方方法法的的基基本本思思想想是是将将哈哈希希表表分分为为基基本本表表和和溢溢出出表表两部分，两部分，凡是与基本表发生冲突的元素一律填入溢出表。凡是与基本表发生冲突的元素一律填入溢出表。第8章 查找 作业作业:设设有有一一组组关关键键字字19，01，23，14，55，20，84，27，68，11，10，77，采采 用用 哈哈 希希 函函 数数：H（key）=key%13采采用用开开放放地地址址法法的的线线性性探探测测再再散散列列方方法法解解决决冲冲突突，试试在在018的散列地址空间中对该关键字序列构造哈希表。的散列地址空间中对该关键字序列构造哈希表。