Ch.9查找 §9.2线性表的查找 59.1基本抵志 查找和掉序是两个量要的运算 ●对像，用战性囊作为表的组织形式。 蓝差森登气紧被的岛，〈记录)由多个数排项构成。服设每个 ●分类：静态查找、内部查找 年方式：顺序查找、二分查找、分块查找 蜜款珍产装备的婆老鞋奖莽于曾气生金类 败)，题回相关指示省意。 #define n 100// ■分类： ◆查找过耀中是香修政衰？动态查找、静志查找 59.21顺序查找 ◆查线过鞭是香热在内存中进行？内部查找、外部查找 ·基本思短 。效事：与存储结构、文件状态（有序、无序）有关 平均查找长建(ASL山，即平均的比较次数，作为衡量查找效率的标准 灭美挂老，男营曾 冕指未站，实服 AS=∑PC,C童拉第个销点的比敏次照 P:壹找第个结点的颜率 ■适用范园：原序表、链衰 ■算法： 设P,=1/n,1≤i运n 的定typedef int KeyType: §9.2.1顺序查找 §9.2.1顺序查找 typedef struct{ ■哨兵的作用 KeyType key: InfoType otherinfo;l应用相关 fo中省略了下标越界>=1判定，节约了约一半时间 )NodeType,,SeqList[n+1：小0号单元作为晴兵 量时间分析 int SeqSearch(SeqList R,KeyType K){ 成功：ASL=(n+1)/2,k©y的平均比较次数约为表长的一半 在R风1可中壹找，成功时运回结点位里，失敢时远回0 失败：叶1次比较 intn; ■优缺点 R0]key=K:I设里喇兵 for(nR们key=K;i-片从后往前找 优点：简单，对存情结构、Ky之间的关系均无特殊要求 return士嗜为0，则失敢 缺点：效率低，当n较大时不宜用 §9.2.2二分（折半）查找 §922二分（折半）查找 ■算法： ■适用范园：顺序表、有序 int BinSearch(SeqList R,KeyType K){ 基本思想（分治法） int mid,low=1,high=n; (1)设Row.high)是当前查找区间，首先确定该区间的中点 while(Iow<high)(I当前查找区间RIow.high]非空 位量：mid(low+high)/2度障 mid=(low+high)/2:整障 (2)将待查的K值与Rmid比较， 许(Rmid.key=K)return mid;∥成功返回位置mid @K一Rmid.key:查找成功，返回位置mid if(K<R[mid.key)l两个子问题求解其中的一个 @K<Rmid.key:则左子表R[Iow..mid-1]是新的查找区间 high=mid-1;在左区间中童找 图K>R[mid],key:剩右子表Rmid+1.high是新的查找区间 else low=mid+1:1l在右区间中查找 初始的查找区间是R[1.n可，每次查找比较K和中间点元囊， }∥endwhile 若查找成功则返回：否则当前查我区间缩小一半，直至当前查找 区间为空时查找失败。 return0;∥当前查找区间为空时失败 11 1 Ch.9 查找 §9.1 基本概念 查找和排序是两个重要的运算 „ 对象：表、文件等。其中每个结点（记录）由多个数据项构成，假设每个 结点有1个能唯一标识该结点的key。 „ 定义：给定1个值K，在含有n个结点的表中找出关键字等于K的结点，若找 到（查找成功），则返回该结点信息或它在表中的位置；否则（查找失 败），返回相关指示信息。 „ 分类： ™ 查找过程中是否修改表？动态查找、静态查找 ™ 查找过程是否均在内存中进行？内部查找、外部查找 „ 效率：与存储结构、文件状态（有序、无序）有关 平均查找长度(ASL)，即平均的比较次数，作为衡量查找效率的标准： Pi ：查找第i个结点的概率 Ci ：查找第i个结点的比较次数 设Pi ＝1/n, 1≤i≤n „ 约定：typedef int KeyType; ∑ = = n i ASL Pi Ci 1 2 § 9.2 线性表的查找 „ 对象：用线性表作为表的组织形式。 „ 分类：静态查找、内部查找 „ 方式：顺序查找、二分查找、分块查找 ＃define n 100// §9.2.1 顺序查找 „ 基本思想 从表的一端开始，顺序扫描线性表，依次将扫描到的结点的Key与给 定值K进行比较，若当前扫描到结点Key＝K，则查找成功返回；若扫描 完整个表后，仍未找到，则查找失败。 „ 适用范围：顺序表、链表 „ 算法： 3 §9.2.1 顺序查找 typedef struct{ KeyType key; InfoType otherinfo; //应用相关 }NodeType, SeqList[n+1]; //0号单元作为哨兵 int SeqSearch( SeqList R, KeyType K) { //在R[1..n]中查找，成功时返回结点位置，失败时返回0 int n; R[0].key=K; //设置哨兵 for ( i=n; R[i].key != K; i-- ); //从后往前找 return i; //若i为0，则失败 } 4 §9.2.1 顺序查找 „ 哨兵的作用 for中省略了下标越界i>=1判定,节约了约一半时间 „ 时间分析 成功：ASLss=(n+1)/2，key的平均比较次数约为表长的一半 失败：n+1次比较 „ 优缺点 优点：简单，对存储结构、Key之间的关系均无特殊要求 缺点：效率低，当n较大时不宜用 5 § 9.2.2 二分（折半）查找 „ 适用范围：顺序表、有序 „ 基本思想（分治法） （1）设R[low..high] 是当前查找区间，首先确定该区间的中点 位置：mid= (low+high)/2 //整除 （2）将待查的K值与R[mid]比较， ① K＝R[mid].key：查找成功，返回位置mid ② K＜R[mid].key：则左子表R[low..mid-1]是新的查找区间 ③ K＞R[mid],key：则右子表R[mid+1..high]是新的查找区间 初始的查找区间是R[1..n]，每次查找比较K和中间点元素， 若查找成功则返回；否则当前查找区间缩小一半，直至当前查找 区间为空时查找失败。 6 § 9.2.2 二分（折半）查找 „ 算法： int BinSearch( SeqList R, KeyType K ) { int mid, low=1, high=n; while ( low < high ) { //当前查找区间R[low..high]非空 mid= (low+high)/2； //整除 if ( R[mid].key==K ）return mid; //成功返回位置mid if ( K＜R[mid].key ) //两个子问题求解其中的一个 high=mid-1; //在左区间中查找 else low=mid+1；//在右区间中查找 } // endwhile return 0; //当前查找区间为空时失败 }