数据结构（Java语言版）课件 第九章 查找

数据结构（Java语言版）09查找【知识目标】

掌握查找的相关概念；

掌握顺序查找法、二分查找法的算法原理及程序实现；

理解二叉排序树法的应用及平衡二叉排序树的实现过程；

掌握哈希查找法的原理；

掌握哈希函数构造方式及冲突解决方法。【能力目标】

能够进行无序表的顺序查找；

能够进行有序表的折半查找；

能够进行哈希表的快速查找。实例引入查找是指在给定的由同一数据类型构成的整体范围（如一篇文章、一个数据库等）内，寻找用户需要的数据的过程。若满足条件的数据存在，则查找成功，否则查找失败。查找的过程要依据用于识别某元素的字段，该字段可唯一识别数据元素，称其为查找关键字。查找的方法主要有顺序查找法、二分查找法（折半查找法）、二叉排序树法、哈希查找法等。查找的概念与方法顺序查找法算法描述将序列A用数组表示，将数字X和序列A中的每个元素进行比较，若相等，则表示X在序列A中存在，查找成功，否则查找失败。顺序查找法publicclassOrderSearch{publicvoidsearch(inta[],intx){inti=0;while(i<=a.length-1&&a[i]!=x)i++;if(i>=a.length)System.out.println("查找失败！");elseSystem.out.println("查找成功！");}publicstaticvoidmain(String[]args){int[]b={12,25,6,95,76,55,124,32,9,73};OrderSearchc1=newOrderSearch();c1.search(b,25);}}算法分析顺序查找法算法复杂度与序列表的长度有直接关系，若查找成功，则比较次数小于或者等于n；若查找不成功，则查找的次数永远为n。顺序查找法的时间复杂度为O(n)，n为序列中元素的个数。在n比较小，或者所查找的元素比较靠前时，顺序查找法较优。顺序查找法适用于查找表无序的情况。折半查找法算法描述

首先将待查找数据与被查找的有序序列的中间元素进行比较，若相等，则查找成功，并确定查找数据的位置；若不相等，则将被查找的有序序列分成两部分，并确定待查找的数据可能在哪一部分，在确定的部分中继续进行折半查找……重复以上折半查找操作，直至查找成功，或无数据可查找则失败。

折半查找法每次将被查找序列分成两部分，又称为二分查找法，其前提是被查找的序列必须是有序的。publicclassHalfSearch{publicintBinary_Search(inta[],intk){intlow,high,mid,pos=0;low=0;high=a.length-1;while(low<=high){mid=(low+high)/2;if(k<a[mid])high=mid-1;elseif(k>a[mid])low=mid+1;elsereturnmid;}}publicstaticvoidmain(String[]args){int[]b={6,9,12,25,32,55,73,76,95,124};HalfSearchc1=newHalfSearch();System.out.println(c1.Binary_Search(b,25));}}折半查找法算法分析

折半查找法的算法分析比较复杂，对于有序序列来说，每次范围减少一半，该算法比顺序查找算法要优一些，其时间复杂度为O(log2n)。折半查找法适用于有序序列。。二叉排序树法算法描述对于给定的序列A={55,25,6,95,76,12,124,32,9,73}，建立二叉排序树并完成查找过程。（1）建立二叉排序树根据二叉排序树性质，将第一个元素作为根节点，将其余元素和根节点比较，若比它小，则进入左子树，否则进入右子树，依次类推，完成二叉排序树的建立。二叉排序树法算法描述对于给定的序列A={55,25,6,95,76,12,124,32,9,73}，建立二叉排序树并完成查找过程。二叉排序树法（2）查找过程在按照前面过程所建立的二叉排序树中，欲查找X=95是否在这个序列中，即判断这两个数据是否在上述的二叉排序树中出现，其过程如下。对于X=95的情况：将X=95和根节点比较（95>55），查找在右子树中进行；将X=95和右子树根节点比较（95=95），查找成功。publicclassBinTreeSearch{publicvoidBinTree_Search(BinTreeNode3root,intx){if(root==null){System.out.println("查找失败："+x);return;}if(x>root.getData()){BinTree_Search(root.getRight(),x);}elseif(x<root.getData()){BinTree_Search(root.getLeft(),x);}else{System.out.println("查找成功："+root.getData());return;}}publicstaticvoidmain(String[]args){BinTreeMainbm=newBinTreeMain();BinSearchTreetree=bm.createSortTree();bm.BinTree_Search(tree.getRoot(),32);bm.BinTree_Search(tree.getRoot(),73);}}二叉排序树法算法分析

对于利用二叉排序树法进行查找，其时间复杂度受二叉排序树的深度影响，假设给定序列为有序序列，则构造的二叉排序树只有左子树或者只有右子树，则该算法退化为顺序查找算法；而当给定序列构造的二叉排序树的左、右子树分布比较均匀时，每次查找可减少一半左右的节点数，则查找效率较高。

因此，建立均匀的二叉排序树是提高此算法效率的重要因素。哈希查找法算法描述

哈希函数的构造方法在哈希查找法中作用非常大，将直接影响数据与存储地址之间的关系，同时也会影响查找的效率。下面介绍常用哈希函数的构造方法。哈希查找法1．直接法直接法是关键字的一个简单哈希函数，该函数在关键字和存储地址之间建立一一对应关系。对于关键字序列

A={1,5,9,13,17,…,81}，建立哈希函数，可在关键字和存储地址之间建立一个线性函数，即公式y=k·x+d，可以得到y=4·x+1。其中x是存储地址，y是关键字序列对应的值。通过直接法可在关键字和存储地址之间建立关系，利用对应关系，一次就可得知查找是成功还是失败。直接法对建立对应关系的关键字要求比较高，因此，可用直接法的关键字序列比较少。哈希查找法2．余数法余数法是针对数值型序列进行哈希查找的有效方法，其主要思路是针对给出的有序序列，通过求序列值的余数进行存储地址（或数组下标）的分配。利用公式y=xmodp

实现余数法哈希函数的构造。序号123456789关键字24151931227311039对应关系y=xmod11余数2483159106数组下标012345678910关键字

12243152739

193110当求得的余数相同时，在分配存储地址时就会出现将多个数据放到同一存储地址的现象，称该现象为哈希查找的冲突现象。哈希查找中的冲突现象是普遍存在的，需要合理解决该冲突，才能有效地使用哈希查找法处理查找问题。哈希冲突（1）顺序查找法顺序查找法是指当该存储地址已有数据元素存在时，就按照某种原则寻找其他空闲的存储地址，直到将所有元素存放位置全部确定为止。（2）链表法链表法解决冲突的思想是将发生冲突的记录构成一个链，都连接在以该记录为头节点的链表中，这样，既实现了地址的分配，同时还保留了记录的关键字与存储地址之间的对应关系。哈希冲突序列A={24,15,18,3,12,27,29,10,45}，当利用余数法建立关键字与存储地址之间的关系后，出现的冲突，对其采用链表法解决冲突后所得到的结果。假设一个班级有40名学生，根据某一学期的成绩，将其划分为5档，即90分以上、80分～90分、70分～80分、60分～70分、60分以下，且每个分数段的学生人数分别为3、7、11、14、5，对于某分数，查找是否有学生得此分数并给出得此分数的学生的人数。分析：可先确定其分数段（用折半法），然后在内部进行查找。将所有学生成绩按照分数段分成若干组，先在这些组之间建立相应的索引表，该索引表应该是有序的。查找时先确定某学生的成绩在哪个组内，然后在组内实现查找。例题classFindScore{intcount=0;int[][]score=newint[5][];publicFindScore(){score[0]=newint[]{98,90,95};score[1]=newint[]{87,82,88,89,85,84,80};score[2]=newint[]{76,75,74,72,73,71,79,77,70,75,70};score[3]=newint[]{61,63,67,68,69,60,65,65,64,63,62,68,69,64};score[4]=newint[]{45,34,23,34,54};}privateintfindScore(ints){intg=getGroup(s);int[]sc=score[g];intcount=0;for(inti=0;i<sc.length;i++){if(sc[i]==s){count++;}}returncount;}

例题intgetGroup(intx){intlow,high,mid,flag=0;low=0;high=4;x=9-x/10; //变换x便于查找分组if(x<0)x=0;if(x>4)x=4;while(low<=high){ //查找x所在分组mid=(low+high)/2;if(x<mid)