ch2-7数据结构_查找.pptVIP

第二章 常用数据结构及其运算 * * 2.7 查找（检索） 1. 定义 确定给定值 k 在含有 n 个记录的文件中的位置的过程称为查找。 2. 查找算法的度量 用平均查找长度 ASL 来度量: 2.7.1 查找的基本概念 其中，n：记录个数，Pi：查找第i个记录的查找概率， Ci：找到第i个记录的比较次数。 若Pi=1/n（等概），则 1. 方法 从第一个记录开始，逐个比较记录值： 找到与k相等的记录，查找成功； 否则，查找失败。 2.7 查找 2.7.2 线性查找（顺序查找） 例： （5，13，17，42，55，70，94） 查找k=55，比较5次，查找成功， 查找12，则失败。 2.7.2 线性查找 2. 算法描述 SeqSearch(r[],n,k){ r[n].key=k; i=0; while (r[i].keyk) i++; return(i);}说明：若返回n表明查找不成功。 3. 性能分析 2.7 查找 等概 －－又称二分查找、折半查找，属于有序表的查找。 1. 基本思想 先找到“中间记录”，比较其关键字，如果关键字与给定值K相等，则查找成功；否则中间结点将线性表分成两个子表，若关键字小于K，则在前半部分子表中查找；反之在后半部分子表中查找。这样把有哪些信誉好的足球投注网站区间缩小了一半。重复以上过程，直到找到与k相等的关键值。 （递增排列情况） 2.7 查找 2.7.3 对分查找 2. 方法 1）初始化：设顺序表r[1:n]，low－有哪些信誉好的足球投注网站范围下界，high－有哪些信誉好的足球投注网站范围上界，mid－中间位置(low+high)/2 2.7 查找 2.7.3 对分查找 m h l l h=m-1 h l=m+1 2）r[mid].key=k: 查找成功； r[mid].keyk: 令high=mid-1 继续查找； r[mid].keyk: 令low=mid+1 继续查找。 3）直到lowhigh，查找失败 5 13 17 42 46 55 70 94 low mid hig k=55 5 13 17 42 46 55 70 94 low mid hig 查找成功 5 13 17 42 46 55 70 94 low mid hig 5 13 17 42 46 55 70 94 low mid hig k=12 5 13 17 42 46 55 70 94 low mid hig 5 13 17 42 46 55 70 94 hig low 查找失败 例： 3. 算法描述 BinSearch(r[],n,k){ low-0; hig-n-1; while (lowhig){ mid=(low+hig)/2; if (k==r[mid].key) return(1); if (kr[mid].key) hig=mid-1; if (kr[mid].key) low=mid+1; } return(0);} 2.7 查找 2.7.3 对分查找 2.7.3 对分查找 4. 算法分析 ? 对分查找的判定树：把比较次数相同的记录放在同一层次，各层次之间用分支相连，可得到一棵二叉树，称为判定树。对分查找恰好是一条从判定树根到被查结点的一条路径，而比较次数恰好是树的深度。 42 94 55 70 46 13 17 5 序列：5,13,17,42,46,55,70,94的判定树 2.7 查找 2.7.3 对分查找 4. 算法分析 ? 等概率下的平均查找长度： 2.7 查找 等概 n30时，对分查找的优势不明显 ? 将数据分成若干块 ? 块与块间数据有序 ? 块内数据无序 1. 算法思想 ① 将各块中的最大关键字构成一个递增有序的索引表 ② 先查找索引表(采用对分或顺序查找),以确定所在块 ③ 在所在块中进行顺序查找 2.7 查找 2.7.4 分块查找(索引顺序查找) 2.7.4 分块查找 例: 2.7 查找 11 9 30 4 38 40 60 65 84 70 75 66 65 84 0 4 8 第1块 第2块 第3块 索引表 最大关