1、第九章 查找9.1 何谓查找l 查找（又称检索、搜索）无论是在日常生活中，查找（又称检索、搜索）无论是在日常生活中，还是在计算机的系统软件和应用软件中都会广泛还是在计算机的系统软件和应用软件中都会广泛的涉及到。的涉及到。l 这一章我们要讨论一些常用的数据查找方法。1.线性查找2.折半查找3.费氏查找4.插补查找5.杂凑查找6.二叉查找树9.2 线性查找l 线性查找法(Linear Searching)又称为循序式查找(Sequential Searching)，是从数据中的第一笔数据开始查找比较，如果找到则返回该值或该位置，如果没有找到则往下一笔数据查找比较，直到查找到最后一笔数据为止，如果表
2、中无任何一个记录的关键字与给定值相等，则查找失败。l intLinear_Search(int Key)l lintIndex=0;/*计数变量*/lwhile(Index 20)llif(Key=DataIndex)/*查找到数据时*/llprintf(Data%d=%d n,Index,Key);lreturn 1;llIndex+;lCounter+;llreturn 0;l l查找成功时的平均查找长度l从线性查找的过程得知，对于有n个记录的查找表，Ci取决于所查记录在表中的位置。如查找表中最后一个记录时需比较n次，查找表中第一个记录时需比较1次。因此，线性查找成功时的平均查找长度为lA
3、SL=P1+2P2+(n-1)Pn-1+nPnl 假设每个记录的查找概率相等，即Pi=1/n，则在等概率情况下线性查找成功时的平均查找长度为l ASL=l =9.2 线性查找l查找不成功时的平均查找长度l 对于线性查找，不论给定值为何值，查找不成功时和给定值进行比较的关键字次数均为n+1。而该给定值可能位于表中第一个元素之前，最后元素之后以及任意两个相邻元素之间，总共n+1种可能，假设每一种查找不成功事件发生的概率都相等，则其概率为1/（n+1）。于是，可得到在查找不成功时的平均查找长度为l uASL=l =n+1l 9.2 线性查找l线性查找法的最佳状态时间复杂度为B(n)=O(1)。表示第
4、一次就找到数据。而最坏状态的时间复杂度为W(n)=O(n)。表示未能找到数据或数据出现在最后一笔。l其平均状态的时间复杂度为A(n)=(1+2+n)/n=(n+1)/2=O(n)9.2 线性查找9.3 折半查找(有序表的查找)l有序表是一种记录的关键字有序（以升序为例）的查找表。有序表也可以使用线性查找，但折半查找用于有序表的查找，效率更高。9.3 折半查找(有序表的查找)l 欲查找值先与该数据(KeyValue)的中位数(middle)比较，假设数据的内容为Data0到Datan，则middle=n/2，左边界left=0，右边界right=n。其原理可归纳为下列3点：l 1.若KeyVal
5、ue小于Datamiddle：表示KeyValue可能出现在Datamiddle之前，所以查找Data0到Datamiddle-1之间的数据。这时left=left，right=middle-1，而middle=(left+right)/2l 2.若KeyValue大于Datamiddle：表示KeyValue可能出现在Datamiddle之后，所以查找Datamiddle+1到Datan之间的数据。这时left=middle+1，right=right，而middle=(left+right)/2l 3.若KeyValue等于Datamiddle：表示已查找到数据。重复执行上述3个步骤直到l
6、eft right或者找到欲查找数据为止。lintBinary_Search(int Key)llintLeft;/*左边界变量左边界变量*/lintRight;/*右边界变量右边界变量*/lintMiddle;/*中位数变量中位数变量*/lLeft=0;lRight=Max-1;lwhile(Left=Right)llMiddle=(Left+Right)/2;lif(Key DataMiddle)/*欲查找值较大欲查找值较大*/lLeft=Middle+1;/*查找后半段查找后半段*/lelse if(Key=DataMiddle)/*查找到数据查找到数据*/llprintf(Data%d
7、=%dn,Middle,DataMiddle);lreturn 1;llCounter+;llreturn 0;l 运用递归方式设计折半查找法的程序 lintBinary_Search(int Left,int Right,int Key)llintMiddle;/*中位数变量中位数变量*/lCounter+;lif(Left Right)lreturn 0;lelsellMiddle=(Left+Right)/2;lif(Key DataMiddle)/*欲查找值较大欲查找值较大*/lreturn Binary_Search(Middle+1,Right,Key);/*查找后半段查找后半段*
8、/lelse if(Key=DataMiddle)/*查找到数据查找到数据*/llprintf(Data%d=%dn,Middle,DataMiddle);lreturn 1;lllreturn 0;l判定树l 折半查找的过程可以用二叉树来表示。判定树即描述查找过程的二叉树，树中每个节点表示表中一个记录，节点的值为该记录在表中的位置。l 查找表中任一记录成功的过程就是走了一条从根节点到与该记录相应节点的路径。l 比较的次数恰好为该节点在判定树上的层次树。由于具有n个节点的判定树的高度为log2n+1，所以折半查找时与给定值进行比较的次数最多为log2n+1次。折半查找判定树9.4 费氏查找l与
9、 折半查找相同，费氏查找也是在有序的待查找序列上实施查找，并且要对序列范围进行分割。不同的是费氏查找法以费氏级数的方式分割待查找序列。9.4 费氏查找l根据二叉树的特性建立一棵费氏树。全部树节点值是一组从1 开始到n 的自然数。这样，每个费氏树节点值就表示一个特定元在原待查找序列中的索引值。全部节点值全部节点值也都是费氏数或其加减运算的结果也都是费氏数或其加减运算的结果。树根之值则表示为待查找序列中首个被选中的特定元的索引值，相当于从树根这个费氏数开始对序列进行首次分割。随后按其子节点值再分割序列。费氏树的特性l 特性一:通常费氏树为一个包含F(a)-1 个节点的二叉树。根下左子树节点共有F(
10、a-1)-1个；根下右子树节点共有F(a-2)-1 个。F(a-1)为根节点之值。其中“a-1”表示为费氏树的高度。l 特性二：费氏树的左干节点均为费氏数，由表示根值开始的费氏数及其在费氏级数中的所有前驱依序组成。最左叶子节点值为费氏数“1”，是费氏树最小的节点。l 特性三：费氏树节点间差值的绝对值均为费氏数。费氏树节点间差值的绝对值均为费氏数。任一个非终端节点的左子节点值为该节点值减去一个费氏数，右子节点值则为该节点值加上同样一个费氏数。从树根起，节点间差值的排列趋势为向叶端减小。l 特性四：费氏树的左子树及右子树也是一种低阶费氏树。设a-1=k,则称根为F(k)的费氏树为k 阶费氏树。其左
11、子树根为“F(k)-F(k-2)”，即F(k-1)，称为k-1 阶费氏树；右子树根为“F(k)+F(k-2)”，称为k-2 阶费氏树。l 下面来介绍一下Fibonacci查找的具体过程：l (1)假设数据共有n笔，则先在Fibonacci数列中找到最小的a使满足F(a)=n+1，然后令l root=F(a-1)l distance_1=F(a-2)l distance_2=F(a-3)l (2)如果欲查找的数据xdataroot，表示x出现在dataroot之后，此时令root=root+distance_2，l distance_1=distance_1-distance_2，l dista
12、nce_2=distance_2-distance_1。l (4)如果x=dataroot，表示已查到数据。l 重复(2)(3)(4)，直到找到相应数据，或直到distance_2为负则表示x不在数据范围内。lint Fibonacci_Search(int n,int Key)llRoot=Fib(n-1);lDistance_1=Fib(n-2);lDistance_2=Fib(n-3);ldollif(Key DataRoot-1)/*欲查找值较大欲查找值较大*/l /*查找后半段查找后半段*/lRoot=Root+Distance_2;lDistance_1=Distance_1-Di
13、stance_2;lDistance_2=Distance_2-Distance_1;llelse if(Key=DataRoot-1)/*查找到数据查找到数据*/llprintf(Data%d=%dn,Root-1,DataRoot-1);lreturn 1;llCounter+;lwhile(Distance_2=0);lreturn 0;l9.5 插补查找l插补查找是一种类似折半查找的查找方法，不同于折半查找每次找出位于中间的元素作为比较元素，插补查找是通过假设待查找序列的元素均匀分布，以内插法按照比内插法按照比例所选出来一项作为比较元素例所选出来一项作为比较元素。l 1.若KeyVal
14、ue小于Datamiddle：表示KeyValue可能出现在Datamiddle之前，必须查找Data0到Datamiddle-1之间的数据。l 2.若KeyValue大于Datamiddle：表示KeyValue可能出现在Datamiddle之后，所以查找Datamiddle+1到Datan之间的数据。l 3.若low小于high，表示数据未查找完成，重新产生新的middle值。l 4.若middle小于low，则令middle=lowl 5.若middle大于high，则令middle=highl 重复执行上述5个步骤，直到找到欲查找数据或low大于high为止。)()(lowdatahi
15、ghdatalowhighlowdatakeyvaluelowmiddlelint Interpolation_Search(int Key)llLow=0;lHigh=Max-1;lMiddle=Low+(Key-DataLow)*(High-Low)/(DataHigh-DataLow);lif(Middle High)lMiddle=High;lwhile(Low=High)llif(Key DataMiddle)/*欲查找值较大欲查找值较大*/lLow=Middle+1;/*查找后半段查找后半段*/lelse if(Key=DataMiddle)/*查找到数据查找到数据*/llprin
16、tf(Data%d=%dn,Middle,DataMiddle);lreturn 1;llif(Low High)lMiddle=Low+(Key-DataLow)*(High-Low)l/(DataHigh-DataLow);lif(Middle High)lMiddle=High;lCounter+;llreturn 0;ll插补查找法对于平均分布的数据效率很高，其时间复杂度为O(log2log2n)，比折半查找法还要好，不过对于不平均分布的数据效率却不好，其最坏状况时的时间复杂度可能达到O(n)。l加强型插补查找法(Robust Interpolation Searching)。l对于不
17、平均分布的数据，采用插补查找法，不但无法增快查找速度，反而让最差状况的时间复杂度达到O(n)。l 改良后的加强型插补查找法，是取1.num1=low+gap2.num2=high-gap3.num3=其中：取3数中的中间数作为middle值l 这样就对不平均分布的数据做出了一定的修正。)()(lowdatahighdatalowhighlowdatakeyvaluelow1lowhighgapl/*找出加强型插补查找的中间值找出加强型插补查找的中间值 */lintFindRobust(int Low,int High,int Key)llintGap;/*差值差值 */lintNum1;/*数
18、值数值1*/lintNum2;/*数值数值2*/lintNum3;/*数值数值3*/lGap=ceil(sqrt(float)High-(float)Low+1.0);lNum1=Low+Gap;/*计算数值计算数值1*/lNum2=High-Gap;/*计算数值计算数值2*/lNum3=Low+(Key-DataLow)*(High-Low)l/(DataHigh-DataLow);/*计算数值计算数值3*/lif(Num1=Num2)lif(Num2=Num3)lreturn Num2;/*Num1=Num2=Num3*/lelse if(Num1=Num3)lreturn Num3;/*
19、Num1=Num3=Num2*/lelselreturn Num1;/*Num3=Num1=Num2*/lelse if(Num2=Num1)lif(Num1=Num3)lreturn Num1;/*Num2=Num1=Num3*/lelse if(Num3=Num1)lreturn Num3;/*Num2=Num3=Num1*/lelselreturn Num2;/*Num3=Num2=Num1*/lreturn 0;llint Interpolation_Search(int Key)llintLow;/*插补查找法左边界变量插补查找法左边界变量*/lintHigh;/*插补查找法右边界变
20、量插补查找法右边界变量*/lintMiddle;/*插补查找法中间数插补查找法中间数*/lLow=0;lHigh=Max-1;lMiddle=FindRobust(Low,High,Key);lif(Middle High)Middle=High;lwhile(Low=High)llif(Key DataMiddle)/*欲查找值较大欲查找值较大*/lLow=Middle+1;/*查找后半段查找后半段*/lelse if(Key=DataMiddle)/*查找到数据查找到数据*/llprintf(Data%d=%dn,Middle,DataMiddle);lreturn 1;llif(Low
21、High)lMiddle=FindRobust(Low,High,Key);lif(Middle High)lMiddle=High;lCounter+;llreturn 0;l9.6 杂凑查找(Hash Searching)l 前前面面讨论的查找讨论的查找方法中方法中，记录，记录的位置的位置和记录的关和记录的关键字之间不存在确定的关系，即记录在表中的相键字之间不存在确定的关系，即记录在表中的相对位置是随机的。因此，在表中查找记录时需要对位置是随机的。因此，在表中查找记录时需要进行一系列和关键字的比较。查找的效率取决于进行一系列和关键字的比较。查找的效率取决于查找过程中所进行的比较次数。查找过
22、程中所进行的比较次数。l 若期望不经过任何比较，一次存取就能得到待查若期望不经过任何比较，一次存取就能得到待查记录，那就必须使每个关键字和表中一个唯一的记录，那就必须使每个关键字和表中一个唯一的存储位置相对应，即必须使记录在表中的存储位存储位置相对应，即必须使记录在表中的存储位置和其关键字存在一种确定的关系。置和其关键字存在一种确定的关系。9.6 杂凑查找(Hash Searching)l 杂凑查找(Hash Searching)就是一种可以让数据的比较次数减少到每次查找只需一次即能找出数据的方法。l 因为杂凑表中关键字存储的位置是通过特定的杂凑函数（哈希函数）H(key)运算而来的。所有的关
23、键字都是通过杂凑函数运算后存储于杂凑表（哈希表）中，当我们进行杂凑查找时，只需将关键字再通过杂凑函数的计算后，便可求得关键字的位置，即可进行一次的关键字的比较即找到欲查找数据。l哈希函数哈希函数H(key)将关键字的集合映射到某个地址集合上，其中，记录的关键字为自变量，记录的存储位置为因变量。l这样建立的表称为哈希表哈希表。l这一映象过程称为哈希，所得的存储位置称为哈希地址哈希地址。l举一个哈希表中最简单的例子。假设为某学院的60名教师建立一张基本信息查找表，每名教师的信息为一个记录，记录的各数据项为：l显然，可以用一个一维数组array60来存放着张表，其中arrayi是编号i的教师的基本信
24、息。编号i便为记录的关键字，由它唯一确定记录的存储位置arrayi。假如把这个数组看成哈希表，则哈希函数H(key)=key。l在上例中以编号为关键字，若改为以教师姓名为关键字，其中教师姓名以汉语拼音的字符表示。下面给出两种不同的哈希函数：（1）取关键字中第一个字母在字母表中的序号作为哈希函数。例如：ZhaoWei的哈希函数为字母Z在字母表中的序号26；（2）求关键字的第一个和最后一个字母在字母表中的序号之和。上述教师信息表中部分关键字在这两种不同的哈希函数下的哈希函数值如下表所列。l同时在这个例子中，在第一种哈希函数的情况下，f1(ChenKun)=f1(ChengHong)=3,而arra
25、y3只能存放一个记录，这种由不同关键字而得到同一哈希地址，即key1不等于key2，而H(key1)=H(key2)的现象，称为冲突冲突(碰撞碰撞)。具有相同函数值的关键字对该哈希函数来说称做同义词同义词。l由于关键字的结构和分布不同，可构造出不同的哈希函数。其中“好”的哈希函数是指对于关键字集合中的任一关键字，经哈希函数映射得到的哈希地址尽可能均匀分布在整个地址区间中，从而减少冲突；同时，使计算过程尽可能简单，以达到较高的查找效率。常用的哈希函数构造方法有以下几种。9.6.1 杂凑函数l 1.直接法(Direct method)直接法就是每一个键值对应一个存储空间，而不经过任何的数学运算动作
26、。l 2.减去法(Subtraction method)减去法就是数据的键值减去一个特定的数值，以求得数据存储的位置。l 采用上述两种方法，关键字与哈希地址一一对应，对于不同的关键字，不会产生冲突，一般用于地址集合和关键字集合大小相同的情况。l 3.余数法(Modulo-Division method)取关键字被某一数p（其中p的值不大于表长m）除后所得余数作为哈希地址。即H(key)=key MOD p(p=m)。p的取值对冲突影响很大l 4.数值抽出法(Digit-Extraction method)数值抽出法就是将数据的键值中的某几位数取出后作为数据存储的位置。这种方法需要预先知道关键字
27、中每一位上所有可能数字的出现频率，以确定分布均匀的有那些。l 5.中间平方法(Midsquare method)中间平方法就是将数据的关键值中的前几位数取出后平方产生一个新的数值，以通过“平方”来扩大差别，减少数字重复出现的频率。尽可能地达到平均分布，减少冲突的可能性；再从新产生的数值中取出中间某几位数作为数据存储的位置。9.6.1 杂凑函数l 6.折迭法(Folding method)若关键字的位数很多，而且关键字中每一位上数字分布大致均匀时，可将其分割成几部分，然后相加后取其结果作为数据存储的位置。l 7.旋转法(Rotation method)旋转法是将数据的键值中进行旋转。旋转法通常并
28、不直接使用在杂凑函数上，而是搭配着其它杂凑函数使用。l 8.伪随机数法(Pseudo-random method)伪随机数法是将利用数据的键值经过伪随机数法的运算后的结果作为数据存储的位置。9.6.2 杂凑碰撞解决法l 由于均匀的哈希函数可以减少冲突，但不能避免冲突。因此处理冲突是哈希法的另一个关键问题。所谓处理冲突，指发生冲突时，将待插入记录存入另一个不产生冲突的地址中，从而解决冲突。l 常用的处理冲突的方法有以下几种：9.6.2 杂凑碰撞解决法l 假设哈希表长为m，当某一关键字key经哈希函数映射得到的地址H0产生冲突，则在H0的基础上加上一个增量d1求得另一个地址H1，若H1位置上无记录
29、存在，则将以key为关键字的记录插到H1位置上，任务完成；若H1位置上有记录存在，则在的H0基础上加上增量d2，并检查该地址是否存在记录直至找到一个可用的地址为止。l 1.线性开放寻址法线性开放寻址法：线性探索法：往下一笔数据位置寻找可用空间。二次方探索法：现有的数据地址加上碰撞次数的平方，当数据地址超出数组大小时，则让数据地址采取循环的方式处理（即对数组大小取余数）。l 2.差值解决法差值解决法差值解决法：现有的数据地址加上一个固定的差值，当数据地址超出数组大小时，则让数据地址采取循环的方式处理（即对数组大小取余数）。9.6.2 杂凑碰撞解决法l3.链表解决法链表解决法 链表解决法：以现在的
30、数据地址再串连一个新的链表来存储数据。l4.分桶杂凑法分桶杂凑法将数据分为几个大类，称之为桶，每个大类中可放置相同大类的数据多笔，当经哈希函数运算后属于同一大类的数据，即放在同一大类中，直到这一大类的数据全填满才往下一大类存储数据。lint Create_Hash(int Key)llintHashTime;/*杂凑次数杂凑次数*/lintCollisionTime;/*碰撞次数碰撞次数*/lintAddress;/*数据地址数据地址*/linti;lHashTime=0;lCollisionTime=0;lAddress=Hash_Mod(Key);/*调用杂凑函数调用杂凑函数*/lwhil
31、e(HashTime Address%dn,Key,Address);lfor(i=0;i Address%dn,CollisionTime,Address);lAddress=Collision_Offset(Address);/*调用碰撞解决法调用碰撞解决法*/llHashTime+;llreturn 0;l9.7 二叉查找树l先将所输入的数据建立成一根二叉查找树。l欲查找值KeyValue与根部父节点Root比较：1.KeyValue小于Root时：l Root=左侧子树的根部节点。2.KeyValue大于Root时：l Root=右侧子树的根部节点。重复执行上述两个步骤直到找到欲查找数
32、据或子树已达底部，而没有根部父节点为止。lint Tree_Search(int Key)llBTreePointer;lPointer=Root;/*查找节点为根节点查找节点为根节点*/lCounter=0;lwhile(Pointer!=NULL)llCounter+;l/*查找节点的数据小于欲查找数据查找节点的数据小于欲查找数据*/lif(Pointer-Key Right;/*往右子树往右子树*/l/*查找节点的数据大于欲查找数据查找节点的数据大于欲查找数据*/lelse if(Pointer-Key Key)lPointer=Pointer-Left;/*往左子树往左子树*/l/*查找节点的数据等于欲查找数据查找节点的数据等于欲查找数据*/lelse if(Pointer-Key=Key)lreturn 1;/*找到数据找到数据*/llreturn 0;/*未能查找到数据未能查找到数据*/l作业l第八章 排序二、应用l2，5l第九章 查找一、复习l1，2，3，4，5，6，7，8，9二、应用l1：将“费氏查找”改为“折半查找”l2，3，5
