第九章 查找（精品）

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,第九章 查找,9.1,何谓查找,查找（又称检索、搜索）无论是在日常生活中，还是在计算机的系统软件和应用软件中都会广泛的涉及到。,这一章我们要讨论一些常用的数据查找方法。,1.,线性查找,2.,折半查找,3.,费氏查找,4.,插补查找,5.,杂凑查找,6.,二叉查找树,9.2,线性查找,线性查找法,(Linear Searching),又称为循序式查找,(Sequential Searching),，是从数据中的第一笔数据开始查找比较，如果找到则返回该值或该位置，如果没有找到则往下一笔数据查找比较，直到查找到最后一笔数据为止，如果表中无任何一个记录的关键字与给定值相等，则查找失败。,int,Linear_Search(int,Key),int,Index=0;/*,计数变量*,/,while(Index 20),if(Key=,DataIndex,)/*,查找到数据时*,/,printf(Data%d,=%d,n,Index,Key,);,return 1;,Index+;,Counter+;,return 0;,查找成功时的平均查找长度,从线性查找的过程得知，对于有,n,个记录的查找表，,C,i,取决于所查记录在表中的位置。如查找表中最后一个记录时需比较,n,次，查找表中第一个记录时需比较,1,次。因此，线性查找成功时的平均查找长度为,ASL=P,1,+2P,2,+(n-1)P,n-1,+nP,n,假设每个记录的查找概率相等，即,P,i,=1/n,，则在等概率情况下线性查找成功时的平均查找长度为,ASL=,=,9.2,线性查找,查找不成功时的平均查找长度,对于线性查找，不论给定值为何值，查找不成功时和给定值进行比较的关键字次数均为,n+1,。而该给定值可能位于表中第一个元素之前，最后元素之后以及任意两个相邻元素之间，总共,n+1,种可能，假设每一种查找不成功事件发生的概率都相等，则其概率为,1/,（,n+1,）。于是，可得到在查找不成功时的平均查找长度为,uASL,=,=n+1,9.2,线性查找,线性查找法的最佳状态时间复杂度为,B(n,)=O(1),。表示第一次就找到数据。而最坏状态的时间复杂度为,W(n,)=,O(n,),。表示未能找到数据或数据出现在最后一笔。,其平均状态的时间复杂度为,A(n,)=(1+2+n)/n=(n+1)/2=,O(n,),9.2,线性查找,9.3,折半查找,(,有序表的查找,),有序表是一种记录的关键字有序（以升序为例）的查找表。有序表也可以使用线性查找，但折半查找用于有序表的查找，效率更高。,9.3,折半查找,(,有序表的查找,),欲查找值先与该数据,(,KeyValue,),的中位数,(middle),比较，假设数据的内容为,Data0,到,Datan,，则,middle=n/2,，左边界,left=0,，右边界,right=n,。其原理可归纳为下列,3,点：,1.,若,KeyValue,小于,Datamiddle,：,表示,KeyValue,可能出现在,Datamiddle,之前，所以查找,Data0,到,Datamiddle-1,之间的数据。,这时,left=,left,，,right=middle-1,，而,middle=(left+right)/2,2.,若,KeyValue,大于,Datamiddle,：,表示,KeyValue,可能出现在,Datamiddle,之后，所以查找,Datamiddle+1,到,Datan,之间的数据。,这时,left=middle+1,，,right=,right,，而,middle=(left+right)/2,3.,若,KeyValue,等于,Datamiddle,：,表示已查找到数据。,重复执行上述,3,个步骤直到,left,right,或者找到欲查找数据为止。,int,Binary_Search(int,Key),int,Left;/*,左边界变量*,/,int,Right;/*,右边界变量*,/,int,Middle;/*,中位数变量*,/,Left=0;,Right=Max-1;,while(Left=Right),Middle=(Left+Right)/2;,if(Key,DataMiddle,)/*,欲查找值较大*,/,Left=Middle+1;/*,查找后半段*,/,else if(Key=,DataMiddle,)/*,查找到数据*,/,printf,(,Data%d,=%,dn,Middle,DataMiddle,);,return 1;,Counter+;,return 0;,运用递归方式设计折半查找法的程序,int,Binary_Search(int,Left,int,Right,int,Key),int,Middle;/*,中位数变量*,/,Counter+;,if(Left Right),return 0;,else,Middle=(Left+Right)/2;,if(Key,DataMiddle,)/*,欲查找值较大*,/,return,Binary_Search(Middle,+1,Right,Key);/*,查找后半段*,/,else if(Key=,DataMiddle,)/*,查找到数据*,/,printf,(,Data%d,=%,dn,Middle,DataMiddle,);,return 1;,return 0;,判定树,折半查找的过程可以用二叉树来表示。判定树即描述查找过程的二叉树，树中每个节点表示表中一个记录，节点的值为该记录在表中的位置。,查找表中任一记录成功的过程就是走了一条从根节点到与该记录相应节点的路径。,比较的次数恰好为该节点在判定树上的层次树。由于具有,n,个节点的判定树的高度为,log,2,n,+1,，所以折半查找时与给定值进行比较的次数最多为,log,2,n,+1,次。,折半查找判定树,9.4,费氏查找,与 折半查找相同，费氏查找也是在有序的待查找序列上实施查找，并且要对序列范围进行分割。不同的是费氏查找法以费氏级数的方式分割待查找序列。,9.4,费氏查找,根据二叉树的特性建立一棵费氏树。全部树节点值是一组从,1,开始到,n,的自然数。这样，每个费氏树节点值就表示一个特定元在原待查找序列中的索引值。,全部节点值也都是费氏数或其加减运算的结果,。树根之值则表示为待查找序列中首个被选中的特定元的索引值，相当于从树根这个费氏数开始对序列进行首次分割。随后按其子节点值再分割序列。,费氏树的特性,特性一,:,通常费氏树为一个包含,F(a)-1,个节点的二叉树。根下左子树节点共有,F(a-1)-1,个；根下右子树节点共有,F(a-2)-1,个。,F(a-1),为根节点之值。其中“,a-1”,表示为费氏树的高度。,特性二：费氏树的左干节点均为费氏数，由表示根值开始的费氏数及其在费氏级数中的所有前驱依序组成。最左叶子节点值为费氏数“,1”,，是费氏树最小的节点。,特性三：,费氏树节点间差值的绝对值均为费氏数。,任一个非终端节点的左子节点值为该节点值减去一个费氏数，右子节点值则为该节点值加上同样一个费氏数。从树根起，节点间差值的排列趋势为向叶端减小。,特性四：费氏树的左子树及右子树也是一种低阶费氏树。设,a-1=k,则称根为,F(k),的费氏树为,k,阶费氏树。其左子树根为,“,F(k)-F(k-2),”,，即,F(k-1),，称为,k-1,阶费氏树；右子树根为,“,F(k)+F(k-2),”,，称为,k-2,阶费氏树。,下面来介绍一下,Fibonacci,查找的具体过程：,(1),假设数据共有,n,笔，则先在,Fibonacci,数列中找到最小的,a,使满足,F(a,)=n+1,，然后令,root=F(a-1),distance_1=F(a-2),distance_2=F(a-3),(2),如果欲查找的数据,x,dataroot,，表示,x,出现在,dataroot,之后，此时令,root=root+distance_2,，,distance_1=distance_1-distance_2,，,distance_2=distance_2-distance_1,。,(4),如果,x=,dataroot,，表示已查到数据。,重复,(2)(3)(4),，直到找到相应数据，或直到,distance_2,为负则表示,x,不在数据范围内。,int,Fibonacci_Search(int,n,int,Key),Root=Fib(n-1);,Distance_1=Fib(n-2);,Distance_2=Fib(n-3);,do,if(Key DataRoot-1)/*,欲查找值较大*,/,/*,查找后半段*,/,Root=,Root,+Distance_2;,Distance_1=,Distance_1,-Distance_2;,Distance_2=,Distance_2,-Distance_1;,else if(Key=DataRoot-1)/*,查找到数据*,/,printf,(,Data%d,=%dn,Root-1,DataRoot-1);,return 1;,Counter+;,while(Distance_2=0);,return 0;,9.5,插补查找,插补查找是一种类似折半查找的查找方法，,不同于折半查找每次找出位于中间的元素作为比较元素，插补查找是通过假设待查找序列的元素均匀分布，,以,内插法按照比例所选出来一项作为比较元素,。,1.,若,KeyValue,小于,Datamiddle,：,表示,KeyValue,可能出现在,Datamiddle,之前，必须查找,Data0,到,Datamiddle-1,之间的数据。,2.,若,KeyValue,大于,Datamiddle,：,表示,KeyValue,可能出现在,Datamiddle,之后，所以查找,Datamiddle+1,到,Datan,之间的数据。,3.,若,low,小于,high,，表示数据未查找完成，重新产生新的,middle,值。,4.,若,middle,小于,low,，则令,middle=low,5.,若,middle,大于,high,，则令,middle=high,重复执行上述,5,个步骤，直到找到欲查找数据或,low,大于,high,为止。,int,Interpolation_Search(int,Key),Low=0;,High=Max-1;,Middle=Low+(Key-,DataLow,)*(High-Low)/(,DataHigh,-,DataLow,);,if(Middle High),Middle=High;,while(Low=High),if(Key,DataMiddle,)/*,欲查找值较大*,/,Low=Middle+1;/*,查找后半段*,/,else if(Key=,DataMiddle,)/*,查找到数据*,/,printf,(,Data%d,=%,dn,Middle,DataMiddle,);,return 1;,if(Low High),Middle=Low+(Key-,DataLow,)*(High-Low),/(,DataHigh,-,DataLow,);,if(Middle High),Middle=High;,Counter+;,return 0;,插补查找法对于平均分布的数据效率很高，其时间复杂度为,O(log,2,log,2,n),，比折半查找法还要好，不过对于不平均分布的数据效率却不好，其最坏状况时的时间复杂度可能达到,O(n,),。,加强型插补查找法,(Robust Interpolation Searching),。,对于不平均分布的数据，采用插补查找法，不但无法增快查找速度，反而让最差状况的时间复杂度达到,O(n,),。,改良后的加强型插补查找法，是取,1.num1=,lo