第九章 查找.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,第九章 查找,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,92,线性查找,线性查找法的最佳状态时间复杂度为,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)/2if(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=,low+gap,2.num2=high-gap,3.num3=,其中：,取,3,数中的中间数作为,middle,值,这样就对不平均分布的数据做出了一定的修正。,/*,找出加强型插补查找的中间值 *,/,int,FindRobust(int,Low,int,High,int,Key),int,Gap;/*,差值 *,/,int,Num1;/*,数值,1*/,int,Num2;/*,数值,2*/,int,Num3;/*,数值,3*/,Gap=ceil(,sqrt,(float)High-(float)Low+1.0);,Num1=Low+Gap;/*,计算数值,1*/,Num2=High-Gap;/*,计算数值,2*/,Num3=Low+(Key-,DataLow,)*(High-Low),/(,DataHigh,-,DataLow,);/*,计算数值,3*/,if(Num1=Num2),if(Num2=Num3),return Num2;/*Num1=Num2=Num3*/,else if(Num1=Num3),return Num3;/*Num1=Num3=Num2*/,else,return Num1;/*Num3=Num1=Num2*/,else if(Num2=Num1),if(Num1=Num3),return Num1;/*Num2=Num1=Num3*/,else if(Num3=Num1),return Num3;/*Num2=Num3=Num1*/,else,return Num2;/*Num3=Num2=Num1*/,return 0;,int,Interpolation_Search(int,Key),int,Low;/*,插补查找法左边界变量*,/,int,High;/*,插补查找法右边界变量*,/,int,Middle;/*,插补查找法中间数*,/,Low=0;,High=Max-1;,Middle=,FindRobust(Low,High,Key,);,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=,FindRobust(Low,High,Key,);,if(Middle High),Middle=High;,Counter+;,return 0;,9.6,杂凑查找,(Hash Searching),前,面,讨论的查找,方法中,，记录,的位置,和记录的关键字之间不存在确定的关系，即记录在表中的相对位置是随机的。因此，在表中查找记录时需要进行一系列和关键字的比较。查找的效率取决于查找过程中所进行的比较次数。,若期望不经过任何比较，一次存取就能得到待查记录，那就必须使每个关键字和表中一个唯一的存储位置相对应，即必须使记录在表中的存储位置和其关键字存在一种确定的关系。,9.6,杂凑查找,(Hash Searching),杂凑查找,(Hash Searching),就是一种可以让数据的比较次数减少到每次查找只需一次即能找出数据的方法。,因为杂凑表中关键字存储的位置是通过特定的杂凑函数（哈希函数）,H(key,),运算而来的。所有的关键字都是通过杂凑函数运算后存储于杂凑表（哈希表）中，当我们进行杂凑查找时，只需将关键字再通过杂凑函数的计算后，便可求得关键字的位置，即可进行一次的关键字的比较即找到欲查找数据。,哈希函数,H(key,),将关键字的集合映射到某个地址集合上，其中，记录的关键字为自变量，记录的存储位置为因变量。,这样建立的表称为,哈希表,。,这一映象过程称为哈希，所得的存储位置称为,哈希地址,。,举一个哈希表中最简单的例子。假设为某学院的,60,名教师建立一张基本信息查找表，每名教师的信息为一个记录，记录的各数据项为：,显然，可以用一个一维数组,array60,来存放着张表，其中,arrayi,是编号,i,的教师的基本信息。编号,i,便为记录的关键字，由它唯一确定记录的存储位置,arrayi,。假如把这个数组看成哈希表，则哈希函数,H,(key,)=key,。,在上例中以编号为关键字，若改为以教师姓名为关键字，其中教师姓名以汉语拼音的字符表示。下面给出两种不同的哈希函数：（,1,）取关键字中第一个字母在字母表中的序号作为哈希函数。例如：,ZhaoWei,的哈希函数为字母,Z,在字母表中的序号,26,；（,2,）求关键字的第一个和最后一个字母在字母表中的序号之和。上述教师信息表中部分关键字在这两种不同的哈希函数下的哈希函数值如下表所列。,同时在这个例子中，在第一种哈希函数的情况下，,f,1,(ChenKun)=f,1,(ChengHong)=3,而,array3,只能存放一个记录，这种由不同关键字而得到同一哈希地址，即,key1,不等于,key2,，而,H(key1)=H(key2),的现象，称为,冲突,(,碰撞,),。具有相同函数值的关键字对该哈希函数来说称做,同义词,。,由于关键字的结构和分布不同，可构造出不同的哈希函数。其中“好”的哈希函数是指对于关键字集合中的任一关键字，经哈希函数映射得到的哈希地址尽可能均匀分布在整个地址区间中，从而减少冲突；同时，使计算过程尽可能简单，以达到较高的查找效率。常用的哈希函数构造方法有以下几种。,9.6.1,杂凑函数,1.,直接法,(Direct method),直接法就是每一个键值对应一个存储空间，而不经过任何的数学运算动作。,2.,减去法,(Subtraction method),减去法就是数据的键值减去一个特定的数值，以求得数据存储的位置。,采用上述两种方法，关键字与哈希地址一一对应，对于不同的关键字，不会产生冲突，一般用于地址集合和关键字集合大小相同的情况。,3.,余数法,(Modulo-Division method),取关键字被某一数,p,（其中,p,的值不大于表长,m,）除后所得余数作为哈希地址。即,H(key,)=key MOD p(p=m),。,p,的取值对冲突影响很大,4.,数值抽出法,(Digit-Extraction method),数值抽出法就是将数据的键值中的某几位数取出后作为数据存储的位置。,这种方法需要预先知道关键字中每一位上所有可能数字的出现频率，以确定分布均匀的有那些。,5.,中间平方法,(,Midsquare,method),中间平方法就是将数据的关键值中的前几位数取出后平方产生一个新的数值，以通过“平方”来扩大差别，减少数字重复出现的频率。尽可能地达到平均分布，减少冲突的可能性；,再从新产生的数值中取出中间某几位数作为数据存储的位置。,9.6.1,杂凑函数,6.,折迭法,(Folding method),若关键字的位数很多，而且关键字中每一位上数字分布大致均匀时，可将其分割成几部分，然后相加后取其结果作为数据存储的位置。,7.,旋转法,(Rotation method),旋转法是将数据的键值中进行旋转。旋转法通常并不直接使用在杂凑函数上，而是搭配着其它杂凑函数使用。,8.,伪随机数法,(Pseudo-random method),伪随机数法是将利用数据的键值经过伪随机数法的运算后的结果作为数据存储的位置。,9.6.2,杂凑碰撞解决法,由于均匀的哈希函数可以减少冲突，但不能避免冲突。因此处理冲突是哈希法的另一个关键问题。所谓处理冲突，指发生冲突时，将待插入记录存入另一个不产生冲突的地址中，从而解决冲突。,常用的处理冲突的方法有以下几种,：,9.6.2,杂凑碰撞解决法,假设哈希表长为,m,，当某一关键字,key,经哈希函数映射得到的地址,H,0,产生冲突，则在,H,0,的基础上加上一个增量,d1,求得另一个地址,H,1,，若,H,1,位置上无记录存在，则将以,key,为关键字的记录插到,H,1,位置上，任务完成；若,H,1,位置上有记录存在，则在的,H,0,基础上加上增量,d2,，并检查该地址是否存在记录,直至找到一个可用的地址为止。,1.,线性开放寻址法,：,线性探索法：往下一笔数据位置寻找可用空间。,二次方探索法：现有的数据地址加上碰撞次数的平方，当数据地址超出数组大小时，则让数据地址采取循环的方式处理（即对数组大小取余数）。,2.,差值解决法,差值解决法,：现有的数据地址加上一个固定的差值，当数据地址超出数组大小时，则让数据地址采取循环的方式处理（即对数组大小取余数）。,9.6.2,杂凑碰撞解决法,3.,链表解决法,链表解决法：以现在的数据地址再串连一个新的链表来存储数据。,4.,分桶杂凑法将数据分为几个大类，称之为桶，每个大类中可放置相同大类的数据多笔，当经哈希函数运算后属于同一大类的数据，即放在同一大类中，直到这一大类的数据全填满才往下一大类存储数据。,int,Create_Hash(int,Key),int,HashTime,;/*,杂凑次数*,/,int,CollisionTime,;/*,碰撞次数*,/,int,Address;/*,数据地址*,/,int,i;,HashTime,=0;,CollisionTime,=0;,Address=,Hash_Mod(Key,);/*,调用杂凑函数*,/,while(,HashTime,Address%,dn,Key,Address,);,for(i=0;i Address%,dn,CollisionTime,Address,);,Address=,Collision_Offset(Address,);/*,调用碰撞解决法*,/,HashTime,+;,return 0;,9.7,二叉查找树,先将所输入的数据建立成一根二叉查找树。,欲查找值,KeyValue,与根部父节点,Root,比较：,1.,KeyValue,小于,Root,时：,Root=,左侧子树的根部节点。,2.,KeyValue,大于,Root,时：,Root=,右侧子树的根部节点。,重复执行上述两个步骤直到找到欲查找数据或子树已达底部，而没有根部父节点为止。,int,Tree_Search(int,Key),BTree,Pointer;,Pointer=Root;/*,查找节点为根节点*,/,Counter=0;,while(Pointer!=NULL),Counter+;,/*,查找节点的数据小于欲查找数据*,/,if(Pointer-Key Right;/*,往右子树*,/,/*,查找节点的数据大于欲查找数据*,/,else if(Pointer-Key,Key,),Pointer=,Pointer,-Left;/*,往左子树*,/,/*,查找节点的数据等于欲查找数据*,/,else if(Pointer-Key=,Key,),return 1;/*,找到数据*,/,return 0;/*,未能查找到数据*,/,作业,第八章 排序,二、应用,2,，,5,第九章 查找,一、复习,1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,，,9,二、应用,1,：将“费氏查找”改为“折半查找”,2,，,3,，,5,