常用查找算法

《常用查找算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录·1概念·2顺序查找·3二分查找·4分块查找·5哈希表查找·展开全部·1概念·2顺序查找·3二分查找·4分块查找·5哈希表查找·收起摘要请用一段简单的话描述该词条，马上添加摘要。查找算法-概念     查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。用关键字标识一个数据元素，查找时根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的。顺序查找也称为线形查找，从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点

2、关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。二分查找要求线形表中的结点按关键字值升序或降序排列，用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。分块查找也称为索引查找，把线形分成若干块，在每一块中的数据元素的存储顺序是任意的，但要求块与块之间须按关键字值的大小有序排列，还要建立一个按关键字值递增顺序排列的索引表，索引表中的一项对应线形

3、表中的一块，索引项包括两个内容：①键域存放相应块的最大关键字；②链域存放指向本块第一个结点的指针。分块查找分两步进行，先确定待查找的结点属于哪一块，然后在块内查找结点。哈希表查找是通过对记录的关键字值进行运算，直接求出结点的地址，是关键字到地址的直接转换方法，不用反复比较。假设f包含n个结点，Ri为其中某个结点（1≤i≤n），keyi是其关键字值，在keyi与Ri的地址之间建立某种函数关系，可以通过这个函数把关键字值转换成相应结点的地址，有：addr(Ri)=H(keyi)，addr(Ri)为哈希函数。   查找算法-顺序查找      顺序查找过程

4、：从表中的最后一个记录开始，逐个进行记录的关键字与给定值进行比较，若某个记录的关键字与给定值相等，则查找成功，找到所查的记录；反之，若直到第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查的记录，查找失败。算法描述为intSearch(intd,inta[],intn){   /*在数组a[]中查找等于d元素，若找到，则函数返回d在数组中的位置，否则为0。其中n为数组长度*/   inti；   /*从后往前查找*/   for(i=n-1;a[i]!=d;--i)   returni;   /*如果找不到，则i为0*/}  查找算法-二分

5、查找                                          二分查找又称折半查找，它是一种效率较高的查找方法。                                              【二分查找要求】：1.必须采用顺序存储结构2.必须按关键字大小有序排列。【优缺点】折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。【算法思想】首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则

6、利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。【算法复杂度】假设其数组长度为n，其算法复杂度为o（log（n））下面提供一段二分查找实现的伪代码:BinarySearch(max,min,des)mid-desthenmax=mid-1elsemin=mid+1returnmax折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(logn)完成

7、搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。  查找算法-分块查找      分块查找又称索引顺序查找，它是顺序查找的一种改进方法。方法描述：将n个数据元素"按块有序"划分为m块（m≤n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……。操作步骤：   step1先选取各块中的最大关

8、键字构成一个索引表；   step2查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块