数据结构(Java版)查找PPT课件

-,1,查找,-,2,查找,算法基本概念常用查找算法。顺序查找(也称线性查找)。折半查找。分块查找。哈希查找,-,3,查找也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素。关键字是数据元素中某个数据项的值，它可以标识一个数据元素。查找方法评价：平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的次数的期望值叫查找算法的。,查找,-,4,顺序查找是一种最基本和最简单的查找方法。它的思路是，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。对于表中记录的关键字是无序的表，只能采用这种方法。,顺序查找,-,5,顺序查找实例,-,6,顺序查找方法的ASL,-,7,课堂练习（例题7-1）,写一个方法实现顺序查找算法,若找到,返回该数所在的位置.找不到,返回-1.intlinearSearch(intdata,intkey)写一程序,给出10个整数,用调用上面的顺序查找方法查找一个数,并输出结果信息.,-,8,查找过程：每次将待查记录所在区间缩小一半。适用条件：采用顺序存储结构的有序表。算法实现：设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。初始时，令low=0,high=n-1,mid=(low+high)/2。让k与mid指向的记录比较若k=rmid.key，查找成功。若krmid.key，则low=mid+1。重复上述操作，直至lowhigh时，查找失败,折半(二分)查找,-,9,找21,折半查找实例,-,10,找70,折半查找实例,-,11,折半查找,-,12,算法评价,从折半查找的平均查找长度ASL来看，当表的长度n很大时，该方法非常有效。但由于折半查找的表仍是线性表，若经常要进行插入、删除操作，则元素排列费时太多，因此折半查找比较适合于一经建立就很少改动而又需要经常查找的线性表，较少查找而又经常需要改动的线性表可以采用链接存储，使用顺序查找。,-,13,课堂练习（例题7-2）,写一个方法实现折半查找算法,若找到,返回该数所在的位置.找不到,返回-1.intbinarySearch(intdata,intkey)写一程序,给出10个整数,用调用上面的顺序查找方法查找一个数,并输出结果信息.,-,14,分块查找,分块查找（blockingsearch）也称索引查找,是一种介于顺序查找和折半查找之间的查找方法。如果要处理的线性表既希望较快的查找速度又需要动态变化，则可以采用分块查找方法。此查找方法常用于词典的编排与查找。对与一本词典，把它按a,b,c,z的顺序进行分块，然后再在每个字母所确定的范围内，按照顺序进行查找，这就是一个分块查找的过程。,-,15,分块查找思想,把线性表分成若干块，在每一块中记录存放可以是无序的，但是块与块之间必须排序。假设这种排序按关键字递增排序，即后一块中的记录的关键字均大于前一块中记录的关键字。再需要建立一个索引表，把每一块中关键字最大的记录按块的顺序存放在一个辅助数组中，显然这个数组是按升序排序的。查找时首先通过索引表确定记录所在的块，然后再在块中进行查找。,-,16,分块查找过程举例,最大关键字起始地址,索引表,15个数据，分成3个块，查找24的过程为：先找到第2个块，再在第2个块中找到33,01234567891011121314,-,17,分块查找算法实现,先用折半查找法或顺序查找法找到块再用顺序查找法在块中查找,-,18,课堂实践（例题7-3）,写一方法，实现分块查找算法。若找到,返回该数所在的位置.找不到,返回-1.intblockSearch(intdata,intmax,intbeginintkey)写一程序，假设在一个一维数组中查找数据，要求数组中数据有50个整数。,-,19,-,20,哈希查找,基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。定义哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。哈希函数可写成：addr(ai)=H(ki)ai是表中的一个元素。addr(ai)是ai的存储地址。ki是ai的关键字。,-,21,哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。哈希查找又叫散列查找，利用哈希函数进行查找的过程叫哈希查找。,哈希查找,-,22,哈希查找实例,以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2,以地区作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19,-,23,哈希函数,从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。冲突：key1key2，但H(key1)=H(key2)的现象叫冲突。哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法。,-,24,哈希函数构造,直接定址法构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key或H(key)=akey+b特点直接定址法所得地址集合与关键字集合大小相等，不会发生冲突。实际中能用这种哈希函数的情况很少。,-,25,哈希函数构造,除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=keyMODp，pm。特点简单、常用，可与上述几种方法结合使用。p的选取很重要。平方取中法构造：取关键字平方后中间几位作哈希地址。适于不知道全部关键字情况。,-,26,处理冲突的方法,线性探测法方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置，将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MODm，i=1,2,k(km-1)其中：H(key)哈希函数m哈希表表长di增量序列,-,27,H(38)=38MOD11=5冲突H1=(5+1)MOD11=6冲突H2=(5+2)MOD11=7冲突H3=(5+3)MOD11=8不冲突,38,冲突解决,例1：表长为11的哈希表中已填有关键字为17，60，29的记录，H(key)=keyMOD11,现有第4个记录，其关键字为38，按处理冲突的方法，将它填入表中。,例2：已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=keyMOD13,哈希表长为m=16，设每个记录的查找概率相等。,要求：用线性探测再散列处理冲突，即Hi=(H(key)+di)MODm,H(55)=3冲突，H1=(3+1)MOD16=4冲突，H2=(3+2)MOD16=5,H(79)=1冲突，H1=(1+1)MOD16=2冲突，H2=(1+2)MOD16=3冲突，H3=(1+3)MOD16=4冲突，H4=(1+4)MOD16=5冲突，H5=(1+5)MOD16=6冲突，H6=(1+6)MOD16=7冲突，H7=(1+7)MOD16=8冲突，H8=(1+8)MOD16=9,14,1,68,27,55,19,20,84,79,23,11,10,H(19)=6,H(14)=1,H(23)=10,H(1)=1冲突，H1=(1+1)MOD16=2,H(68)=3,H(20)=7,H(84)=6冲突，H1=(6+1)MOD16=7冲突，H2=(6+2)MOD16=8,H(27)=1冲突，H1=(1+1)MOD16=2冲突，H2=(1+2)MOD16=3冲突，H3=(1+3)MOD16=4,H(11)=11,H(10)=10冲突，H1=(10+1)MOD16=11冲突，H2=