毕业论文学年论文几种查找算法的比较与总结.doc

学 年 论 文题 目： 几种查找算法的比较与总结学 院： 计算机科学与工程 专 业： 计算机科学与技术班 级: 12级计师1班学生姓名： 马有华学 号： 201271030132指导教师： 曹素珍I摘 要查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中,查找是常用的基本运算。文中介绍四种查找算法分别是顺序查找、二分查找、二叉排序树查找和哈希查找。并用JAVA语言编写了相应程序代码，比较了查找同一个数据的时间复杂度和空间复杂度。关键词: 查找算法；时间复杂度；空间复杂度AbstractSearching is a commonly basic operation that can find a number of information in computer applications.In this paper,four tapyes of searching algorithm are introduced.They are squential earch,binary search tree,and bash search.The progarms codes based on java are complied. The time complexity and space complexity to look for the same data and compared.Key words: Searching Algorithm；Timecomplexity；Spacecomplexity目 录摘 要11 算法概述11.1引言11.2顺序查找21.3二分查找21.3.1二分查找要求21.3.2优缺点21.3.3算法思想21.3.4算法复杂度31.4分块查找31.4.1方法描述31.4.2操作步骤31.5哈希表查找41.5.1基本原理41.5.2函数构造41.5.3冲突处理41.5.4支持运算42 算法实现72.1顺序查找72.1.1方法分类72.2二分查找82.2.1算法要求82.2.2算法复杂度82.2.3代码示例92.2.4递归实现112.3分块查找162.3.1方法描述162.3.2操作步骤172.4哈希表查找182.4.1操作步骤182.4.2解决冲突193 比较与总结223.1分类查找的依据223.2效率比较22参考文献24261 算法概述1.1引言用关键字标识一个数据元素，查找时根据给定的某个值，在表中确定一个关键字的值等于给定值的记录或数据元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的。顺序查找也称为线形查找，从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。二分查找要求线形表中的结点按关键字值升序或降序排列，用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。分块查找也称为索引查找，把线形分成若干块，在每一块中的数据元素的存储顺序是任意的，但要求块与块之间须按关键字值的大小有序排列，还要建立一个按关键字值递增顺序排列的索引表，索引表中的一项对应线形表中的一块，索引项包括两个内容：1）键域存放相应块的最大关键字；2）链域存放指向本块第一个结点的指针。分块查找分两步进行，先确定待查找的结点属于哪一块，然后在块内查找结点。哈希表查找是通过对记录的关键字值进行运算，直接求出结点的地址，是关键字到地址的直接转换方法，不用反复比较。假设f包含n个结点，Ri为其中某个结点（1in），keyi是其关键字值，在keyi与Ri的地址之间建立某种函数关系，可以通过这个函数把关键字值转换成相应结点的地址，有：addr(Ri)=H(keyi)，addr(Ri)为哈希函数。1.2顺序查找 顺序查找过程：从表中的最后一个记录开始，逐个进行记录的关键字与给定值进行比较，若某个记录的关键字与给定值相等，则查找成功，找到所查的记录；反之，若直到第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查的记录，查找失败。算法描述为：int Search(int d,int a,int n) /*在数组a中查找等于D元素，若找到，则函数返回d在数组中的位置，否则为0。其中n为数组长度*/int i ； /*从后往前查找*/for(i=n-1;a!=d;-i) 此处程序正确吗？return i ； /*如果找不到，则i为0*/1.3二分查找二分查找又称折半查找，它是一种效率较高的查找方法。1.3.1二分查找要求1）必 须采用顺序存储结构。2）必须按关键字大小有序排列。1.3.2优缺点折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。1.3.3算法思想首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此 时查找不成功。1.3.4算法复杂度假设其数组长度为n，其算法复杂度为O(log(n)，下面提供一段二分查找实现的伪代码:BinarySearch(max,min,des)mid-des then 此处程序正确吗？ max=mid-1 else min=mid+1return max折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取an/2与欲查找的x作比较，如果x=an/2则找到x，算法终止。如 果xan/2，则我们只要在数组a的右 半部继续搜索x。1.4分块查找step1 先选取各块中的最大关键字构成一个索引表。step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。1.4.1方法描述将n个数据元素按块有序划分为m块（m n）。每一块中的结点不 必有序，但块与块之间必须按块有序；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，1.4.2操作步骤step1 先选取各块中的最大关键字构成一个索引表。step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。1.5哈希表查找1.5.1基本原理 从此处开始至正文最后一页的文字部分格式，按照如下格式设置：字体：正文宋体；字号：小四；段落中的格式为：正文：两端对齐；首行缩进：2字符；间距：段前段后均为：0行；行距：1.5倍行距。具体图示如下：代码部分请仔细检查正误。然后按照上述正文设置格式以及代码缩进格式调整。我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素分类，然后将这个元素存储在相应类所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了冲突，换句话说，就是把不同的元素分在了相同的类之中。后面我们将看到一种解决冲突的简便做法。总的来说，直接定址与解决冲突是哈希表的两大特点。1.5.2函数构造构造函数的常用方法（下面为了叙述简洁，设 h(k) 表示关键字为 k 的元素所对应的函数值）：1) 除余法选择一个适当的正整数 p ，令 h(k ) = k mod p这里， p 如果选取的是比较大的素数，效果比较好。而且此法非常容易实现，因此是最常用的方法。2) 数字选择法如果关键字的位数比较多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干位，所组成的新的值作为关键字或者直接作为函数值。1.5.3冲突处理线性重新散列技术易于实现且可以较好的达到目的。令数组元素个数为 S ，则当 h(k) 已经存储了元素的时候，依次探查 (h(k)+i) mod S , i=1,2,3 ，直到找到空的存储单元为止（或者从头到尾扫描一圈仍未发现空单元，这就是哈希表已经满了，发生了错误。当然这是可以通过扩大数组范围避免的）。1.5.4支持运算哈希表支持的运算主要有：初始化(makenull)、哈希函数值的运算(h(x)、插入元素(insert)、查找元素(member)。设插入的元素的关键字为 x ，A 为存储的数组。初始化比较容易，例如const empty=maxlongint; / 用非常大的整数代表这个位置没有存储元素p=9997; / 表的大小procedure makenull;var i:integer;beginfor i:=0 to p-1 doA:=empty;End;哈希函数值的运算根据函数的不同而变化，例如除余法的一个例子： function h(x:longint):Integer; begin h:= x mod p; end;我们注意到，插入和查找首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位置，因此加入一个定位的函数 locatefunction locate(x:longint):integer;var orig,i:integer;beginorig:=h(x);i:=0;while (ix)and(A(orig+i)mod Sempty) doinc(i);/当这个循环停下来时，要么找到一个空的存储单元，要么找到这个元/素存储的单元，要么表已经满了 locate:=(orig+i) mod S; end;插入元素 procedure insert(x:longint); var posi:integer; begin posi:=locate(x); /定位函数的返回值 if Aposi=empty then Aposi:=x else error; /error 即为发生了错误，当然这是可以避免的 end;查找元素是否已经在表中 procedure member(x:longint):boolean; var posi:integer; begin posi:=locate(x); if Aposi=x then member:=true else member:=false; end;2 算法实现2.1顺序查找在一个已知无(或有序）序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。2.1.1方法分类(1）Java实现方法package search;/*顺序查找* des 要查找的元素* i 保存当前元素的下标*/public class OrderSearch public static int ordersearch(int arry,int des)int i=0;for(;i=arry.length-1;i+)if(des=arryi)return i;return -1;public static void main(String args)int a=new int2,3,5,6,7,3,;System.out.println(ordersearch(a,3);(2) C实现算法int sq_search(keytype keyp,int n,keytype key)int i;for(i=0; in; i+)if(keyi = key)return i;/查找成功return -1;/查找失败3）C+实现方法int Seqsch(ElemType A ,int n,KeyType K)/从顺序表A的n个元素中顺序查找关键字为K的元素，若成功返回其下标，否则返回-1int i;for( i=0;in;i+)if(Ai.key=K)break;if(i=n-1) /查找成功返回下标，否则返回-1return i;elsereturn -1;4）php实现方法function seq_sch($array, $n, $k) for($i=0; $i$n; $i+) if( $array$i=$k)break;if ($i$n) return $i;elsereturn -1;2.2二分查找2.2.1算法要求1） 必须采用顺序存储结构2）必须按关键字大小有序排列。2.2.2算法复杂度假设其数组长度为n，其算法复杂度为o（log（n）下面提供一段二分查找实现的伪代码:BinarySearch(max,min,des)mid-(max+min)/2while(mindes thenmax=mid-1elsemin=mid+1return max折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取an/2与欲查找的x作比较，如果x=an/2则找到x，算法终止。如 果xan/2，则我们只要在数组a的右 半部继续搜索x。2.2.3代码示例1）Python源代码123456789101112131415161718192021defbinarySearch(lists,select):is_none=Falseiflists!=:cen_num=len(lists)/2tlag=listscen_numgt_list=lists0:cen_numlt_list=listscen_num+1:iftlag=select:is_none=Truereturnis_noneeliftlagselect:is_se=binarySearch(gt_list,select)ifnotis_se:returnbinarySearch(lt_list,select)returnis_noneeliftlagxthenbeginn:=j-1;j:=trunc(i+n)/2)endelseifaj=n);为什么是这个结束循环条件ifaj=xthenwriteln(查找成功！位置是：,j:3)elsewriteln(查找失败，数组中无此元素！)end.PHP代码实现3）C语言代码123456789101112131415161718192021222324252627282930313233343536373839404142434445intBinSearch(SeqList*R，intn,KeyTypeK)/在有序表R0.n-1中进行二分查找，成功时返回结点的位置，失败时返回-1intlow=0，high=n-1，mid；/置当前查找区间上、下界的初值while(low=high)if(Rlow.key=K)returnlow;if(Rhigh.key=k)returnhigh;/当前查找区间Rlow.high非空mid=low+(high-low)/2)；/使用(low+high)/2会有整数溢出的问题/（问题会出现在当low+high的结果大于表达式结果类型所能表示的最大值时，/产生溢出后再/2是不会产生正确结果的，而low+(high-low)/2)不存在这个问题if(Rmid.key=K)returnmid；/查找成功返回if(Rmid.keyhigh)return-1；/当lowhigh时表示所查找区间内没有结果，查找失败/BinSeareh-上面代码复杂难懂-intbsearchWithoutRecursion(intarray,intlow,inthigh,inttarget)while(lowtarget)high=mid-1;elseif(arraymidhigh)return-1;elseif(arrmid=key)returnmid;elseif(arrmidkey)returnbinary_search(arr,low,mid-1,key);elsereturnbinary_search(arr,mid+1,high,key);1）Java代码1234567891011121314151617publicstaticintbinarySearch(IntegersrcArray,intdes)intlow=0;inthigh=srcArray.length-1;while(low=high)&(low=srcArray.length-1)&(high1);if(des=srcArraymiddle)returnmiddle;elseif(dessrcArraymiddle)high=middle-1;elselow=middle+1;return-1;2）AAuto代码123456789101112131415161718192021222324252627282930/二分查找functionbinSearch(t,v)varp=#t;varp2;varb=0;dop2=p;p=b+math.floor(p-b)/2)/二分折半运算if(p=b)return;if(tpv)/判断上限returntp=v&p;/测试tab=/创建数组，每个元素都是随机数for(i=1;10;1)tabi=math.random(1,10000)/插入一个已知数table.push(tab,5632)/排序table.sort(tab)io.open()io.print(数组,table.tostring(tab)io.print(使用二分查找，找到5632在位置：,binSearch(tab,5632)3）PHP代码12345678910111213141516171819202122232425262728293031/递归版本functionbin_sch($array,$low,$high,$k)if($low=$high)$mid=intval($low+$high)/2);if($array$mid=$k)return$mid;elseif($k$array$mid)returnbin_sch($array,$low,$mid-1,$k);elsereturnbin_sch($array,$mid+1,$high,$k);return-1;/非递归版本functionbinsearch($x,$a)$c=count($a);$lower=0;$high=$c-1;while($lower$x)$high=$middle-1;elseif($a$middle$x)$lower=$middle+1;elsereturn$middle;return-1;4）C+代码1234567891011121314151617181920212223242526272829intbinSearch(constint*Array,intstart,intend,intkey)intleft,right;intmid;left=start;right=end;/注释中为递归算法，执行效率低，不推荐/*if(keyArraymid)return(binSearch(Array,mid+1,right,key);elsereturnmid;*/while(left=right)mid=(left+right)/2;if(key=Arraymid)returnmid;elseif(keyArraymid)left=mid+1;return-1;15）AS3代码123456789101112131415publicstaticfunctionbinSearch(list:Array,low:int,high:int,key:int):intif(lowhigh)return-1;varmid:int=low+int(high-low)/2);varindex:int=-1if(listmid=key)index=mid;elseif(listmidkey)low=mid+1;index=binSearch(list,low,high,key);elsehigh=mid-1;index=binSearch(list,low,high,key);returnindex;6）JavaScript代码12345678910111213141516171819varArr=3,5,6,7,9,12,15;functionbinary(find,arr,low,high)if(lowfind)returnbinary(find,arr,low,mid-1);elsereturnbinary(find,arr,mid+1,high);return-1;binary(15,Arr,0,Arr.length-1);7）PHP代码123456789101112131415161718192021/*二分查找：前提，该数组已经是一个有序数组，必须先排序，再查找。*/functionbinarySearch(&$array,$findVal,$leftIndex,$rightIndex)$middleIndex=round($rightIndex+$leftIndex)/2);if($leftIndex$rightIndex)echo查无此数;return;if($findVal$array$middleIndex)binarySearch($array,$findVal,$middleIndex+1,$rightIndex);elseif($findVal$array$middleIndex)binarySearch($array,$findVal,$leftIndex,$middleIndex-1);elseecho找到数据:index=$middleIndex;value=$array$middleIndex;if($array$middleIndex+1=$array$middleIndex&$leftIndex$rightIndex)binarySearch($array,$findVal,$middleIndex+1,$rightIndex);if($array$middleIndex-1=$array$middleIndex&$leftIndex$rightIndex)binarySearch($array,$findVal,$leftIndex,$middleIndex-1);2.3分块查找2.3.1方法描述分块查找要求把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的i，第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。此外，还要建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，显然这个辅助数组是按关键码值费递减排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找；然后，在相应的块中采用顺序查找，即可找到对应的节点。分块查找在现实生活中也很常用。例如，一个学校有很多个班级，每个班级有几十个学生。给定一个学生的学号，要求查找这个学生的相关资料。显然，每个班级的学生档案是分开存放的，没有任何两个班级的学生的学号是交叉重叠的，那么最好的查找方法实现确定这个学生所在的班级，然后再在这个学生所在班级的学生档案中查找这个学生的资料。上述查找学生资料的过程，实际上就是一个典型的分块查找。2.3.2操作步骤step1 先选取各块中的最大关键字构成一个索引表；1step2 查找分两个部分：先对索引表进行二分查找,顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。在C语言中其代码如下：#include struct index /*定义块的结构*/int key;int start;int end; index_table4; /*定义结构体数组*/int block_search(int key, int a) /*自定义实现分块查找*/int i, j;i = 1;while (i index_tablei.key) /*确定在那个块中*/i+;if (i 3) /*大于分得的块数，则返回0*/return 0;j = index_tablei.start; /*j等于块范围的起始值*/while (j index_tablei.end) /*如果大于块范围的结束值，则说明没有要查找的数,j置0*/j = 0;return j;main()int i, j = 0, k, key, a16;printf(please input the number:n);for (i = 1; i 16; i+)scanf(%d, &ai); /*输入由小到大的15个数*/for (i = 1; i = 3; i+)index_tablei.start = j + 1; /*确定每个块范围的起始值*/j = j + 1;index_tablei.end = j + 4; /*确定每个块范围的结束值*/j = j + 4;index_tablei.key = aj; /*确定每个块范围中元素的最大值*/printf(please input the number which do you want to search:n);scanf(%d, &key); /*输入要查询的数值*/k = block_search(key, a); /*调用