软件基础-2-08查找

《软件基础-2-08查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.7查找§2.7.1查找的基本概念♣关键字1）主关键字：在数据处理中，被查找的元素通常是以记录形式出现的，即每一个数据元素（记录）由若干个数据项组成，其中能用来唯一标识该记录的数据项称为主关键字。2）次关键字：用来标识若干记录的数据项称为次关键字。♣查找给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如果找到则输出该记录，否则输出查找不成功的信息。数据结构-08查找2013/10/1012.7查找§2.7.1查找的基本概念♣平均查找长度由于待查记录在文件中的位置随意性很大，因此通常用比较次数的平均值，即

2、统计意义上的数学期望值来评估查找算法，称为平均查找长度（ASL）：nASL=∑PiCii=1其中，n是文件中记录的个数，P是查找第i个i记录的查找概率，通常我们认为每个记录的查找概率相等，即P=1/n；C是找到第i个记录时ii所经历的比较次数。数据结构-08查找2013/10/102§2.7.2顺序查找查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较算法描述找6401234567891011例64513192137566475808892iiiii监视哨比较次数：比较次数=5查找第n个元素：1查找第n-1个元素：2……

3、….查找第1个元素：n查找第i个元素：n+1-iCh7_1.c查找失败：n+1数据结构-08查找2013/10/103顺序查找方法的ASLn对含有n个记录的表，ASL=∑picii=11设表中每个元素的查找概率相等p=innn11n(n+1)n+1则ASL=∑pici=∑i=⋅=i=1ni=1n22数据结构-08查找2013/10/104§2.7.3折半查找查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的有序表算法实现设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给

4、定值初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k==r[mid].key，查找成功若kr[mid].key，则low=mid+1重复上述操作，直至low>high时，查找失败数据结构-08查找2013/10/105算法描述找211234567891011例513192137566475808892lowmidhigh1234567891011513192137566475808892lowmidhigh1234

5、567891011513192137566475808892lowmidhighCh7_2.c数据结构-08查找2013/10/106找701234567891011例513192137566475808892lowmidhigh1234567891011513192137566475808892lowmidhigh1234567891011513192137566475808892lowmidhigh1234567891011513192137566475808892lowhighmid数据结构-08查找2013/10/10712

6、34567891011513192137566475808892highlow1234567891011513192137566475808892判定树：6391471025811数据结构-08查找2013/10/108算法评价判定树：描述查找过程的二叉树叫~有n个结点的判定树的深度为log2n+1折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度折半查找的ASLh设表长n=2−1,h=log(n+1),即判定树是深度为h的满二叉树21设表中每个记录的查找概率相等p=innnh11j−1n+1则：ASL=∑p

7、ici=∑ci=∑j⋅2=log2(n+1)−1≈log2(n+1)−1i=1ni=1nj=1n数据结构-08查找2013/10/1092.7查找§2.7.4分块查找♣概念分块查找又称索引顺序查找，把关键字分成若干块，且后一块中的所有关键字均大于前一块中最大的关键字。而每一块中的关键字则不一定有序。♣基本思想先将各块中的最大关键字构成一个递增有序的索引表，查找分两步：①对索引表对分或顺序查找,以确定所在块。②在所在块中进行顺序查找。数据结构-08查找2013/10/10102.7查找§2.7.4分块查找索引表224886查38171

8、31234567891011121314151617182212138920334244382448605874578653数据结构-08查找2013/10/10112.7查找§2.7.5二叉排序树查找以上讨论的三种查找方法，其记录均