资源描述：
《最新数据结构(Java版)查找课件PPT.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构(Java版)查找查找算法基本概念常用查找算法。顺序查找(也称线性查找)。折半查找。分块查找。哈希查找查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素。关键字——是数据元素中某个数据项的值，它可以标识一个数据元素。查找方法评价：平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的次数的期望值叫查找算法的。查找课堂练习（例题7-1）写一个方法实现顺序查找算法,若找到,返回该数所在的位置.找不到,返回-1.intlinearSearch(intdata[]
2、,intkey)写一程序,给出10个整数,用调用上面的顺序查找方法查找一个数,并输出结果信息.查找过程：每次将待查记录所在区间缩小一半。适用条件：采用顺序存储结构的有序表。算法实现：设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。初始时，令low=0,high=n-1,mid=(low+high)/2。让k与mid指向的记录比较若k==r[mid].key，查找成功。若kr[mid].key，则low=mid+1。重复上述操作，直至low>high时，查找失败
3、折半(二分)查找mid例：1234567891011513192137566475808892找2112345678910115131921375664758088921234567891011513192137566475808892折半查找实例lowhighhighmidlowhighmidlow例1234567891011513192137566475808892找7012345678910115131921375664758088921234567891011513192137566475808892折半查找实例midlowhighhighmidl
4、owhighmidlow折半查找1234567891011513192137566475808892highmidlow1234567891011513192137566475808892highlow算法评价从折半查找的平均查找长度ASL来看，当表的长度n很大时，该方法非常有效。但由于折半查找的表仍是线性表，若经常要进行插入、删除操作，则元素排列费时太多，因此折半查找比较适合于一经建立就很少改动而又需要经常查找的线性表，较少查找而又经常需要改动的线性表可以采用链接存储，使用顺序查找。课堂练习（例题7-2）写一个方法实现折半查找算法,若找到,返回该数所在的
5、位置.找不到,返回-1.intbinarySearch(intdata[],intkey)写一程序,给出10个整数,用调用上面的顺序查找方法查找一个数,并输出结果信息.分块查找分块查找（blockingsearch）也称索引查找,是一种介于顺序查找和折半查找之间的查找方法。如果要处理的线性表既希望较快的查找速度又需要动态变化，则可以采用分块查找方法。此查找方法常用于词典的编排与查找。对与一本词典，把它按a,b,c,…z的顺序进行分块，然后再在每个字母所确定的范围内，按照顺序进行查找，这就是一个分块查找的过程。分块查找思想把线性表分成若干块，在每一块中记录存
6、放可以是无序的，但是块与块之间必须排序。假设这种排序按关键字递增排序，即后一块中的记录的关键字均大于前一块中记录的关键字。再需要建立一个索引表，把每一块中关键字最大的记录按块的顺序存放在一个辅助数组中，显然这个数组是按升序排序的。查找时首先通过索引表确定记录所在的块，然后再在块中进行查找。分块查找过程举例22488606112212138920333844482460867449最大关键字起始地址索引表15个数据，分成3个块，查找24的过程为：先找到第2个块，再在第2个块中找到3301234567891011121314分块查找算法实现先用折半查找法或顺序
7、查找法找到块再用顺序查找法在块中查找课堂实践（例题7-3）写一方法，实现分块查找算法。若找到,返回该数所在的位置.找不到,返回-1.intblockSearch(intdata[],int[]max,int[]beginintkey)写一程序，假设在一个一维数组中查找数据，要求数组中数据有50个整数。ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找关键字集合存储地址集合hash哈希查找基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这
8、样，不经过比较，一次存取就能得到所查元素的查找方法。定义哈希函数—
