信息学奥赛辅导.pptVIP

信息学奥赛辅导 * * §9.1 查找 ? 查找也称检索，就是在一组给定的数据中查找满足某种条件的数据，查找通常需要根据某一关键字进行。例如，在c盘中查找文件名为“cgf.txt”的文件。根据算法思想的不同，查找主要分为顺序查找和二分查找。 1.顺序查找 顺序查找是最基本的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，一一将扫描到的结点关键字和给定值K比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。 A[i] x 23 25 3 5 138 200 110 89 17 20 【例9-1】 输入一个整数X，在已存在的一个整数数组中顺序查找X是否存在，若找到，输出X在整数数组中所对应的位置，否则输出找不到的信息。（假设数组中没有重复数据） 算法分析： （1）?????? 先输入待查的值K （2）?????? 令i=1，让k与a[i]比较 （3）?????? 若a[i]k,则i:=i+1，如果i=n然后转（3）继续进行比较，如果i.n，则退出循环，输出找不到的信息；若a[i]=k，则退出循环，输出找到的信息。 参考程序: Program ex9_1; Const n=10 var x,k,i:integer; a:array[1..n] of integer; found:Boolean; begin for i:=1 to n do read(a[i]);readln; readln(x) i:=1;found:=false; while (i=n)and not(found) do if a[i]=x then found:=true else i:=i+1; if found then writeln(‘k at’,i:6) else writeln(‘not found’); end. 参考程序: Program ex9_1; Const n=8 var x,k,i:integer; a:array[1..n] of integer; begin for i:=1 to n do read(a[i]);readln; readln(x) i:=1; For I:=1 to n do if a[i]=x then begin writeln(‘k at’,i:6);exit;end else if I=n then writeln(‘not found’); end. 2.二分查找 顺序查找要逐个比较表中元素，当表中元素非常多时,顺序查找的效率是很低的。二分查找是一种效率较高的查找方法，基于分治算法的思想，但二分查找要求线性表必须是有序的.我们不防设有序表是递增有序的。 二分查找的基本思想是：（设R[low..high]是当前的查找区间） (1)??? 首先确定该区间的中点位置:mid = [(low + high)/2] (2)??? 然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,具体方法如下: 1若R[mid].keyk,则由表的有序性可知R[mid..n].keys均大于K,因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R[1..mid-1k]中,故新的查找区间是左边的子表R[1..mid-1]。 2类似地，若R[mid].keyK，则要查找的K必在mid的右子表r[mid+1..n]中，即新的查找区间R[1..n]开始，每间经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空（即查找失败）时为止。 130 125 120 112 103 98 90 88 84 79 72 68 56 42 35 25 A[i] f h mid 130 125 120 112 103 98 90 88 84 79 72 68 56 42 35 25 130 125 120 112 103 98 90 88 84 79 72 68 56 42 35 25 130 125 120 112 103 98 90 88 84 79 72 68 56 42 35 25 X=95 f f f h h h mid mid mid 【例9-2】输入一整数X，在已存的一个有序整数数组中二分查找X是否存在，若找到，输出X在整数数组中所对应的位置，否则输出找不到的信息。（已知数组中没有重复数据） 参考程序： Program