软件技术基础查找.ppt

第二章 常用数据结构及其运算 * 查找与排序技术 第三章 内 容 3．1 基本的查找技术 3．2 哈希表技术 3．3 基本排序技术 3．4 二叉排序树 1. 定义 确定特定值 x（关键字）在给定数据结构中的位置的过程称为查找。 2. 查找算法的度量 用平均查找长度 ASL 来度量: 引言 查找的基本概念 其中，n：记录个数，Pi：查找第i个记录的查找概率， Ci：成功找到第i个记录的比较次数。 若Pi=1/n（等概），则 3.1 基本查找技术 1. 方法 从第一个记录开始，逐个比较记录值： 找到与k相等的记录，查找成功； 否则，查找失败。 3.1 基本查找技术 3.1.1 线性查找（顺序查找） 例： （5，13，17，42，55，70，94） 查找k=55，比较5次，查找成功， 查找12，则失败。 3.1.1 线性查找 2. 算法描述 SeqSearch(A[N+1],x){ A[N]=x; i=0; while (A[i]!=x) i++; return(i);}说明：若返回n表明查找不成功。 3. 性能分析 3.1 基本查找技术 －－又称二分查找、折半查找，属于有序表的查找。 1. 基本思想 先找到“中间记录”，比较其关键字，如果关键字与给定值K相等，则查找成功；否则中间结点将线性表分成两个子表，若关键字小于K，则在前半部分子表中查找；反之在后半部分子表中查找。这样把搜索区间缩小了一半。重复以上过程，直到找到与k相等的关键值。 （递增排列情况） 3.1.2 对分查找 3.1 基本查找技术 2. 方法 1）初始化：设顺序表A[1:n]，low－搜索范围下界，high－搜索范围上界，mid－中间位置(low+high)/2 3.1.2 对分查找 m h l l h=m-1 h l=m+1 2）A[mid]=x: 查找成功； A[mid]x: 令high=mid-1 继续查找； A[mid]x: 令low=mid+1 继续查找。 3）直到lowhigh，查找失败 3.1 基本查找技术 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(A[N],x){ low=0; hig=N-1; while (low=hig){ mid=(low+hig)/2; if (x==A[mid]) return mid; else if (xA[mid]) hig=mid-1; else low=mid+1; } return(0);} 3.1.2 对分查找 3.1 基本查找技术 3.1.2 对分查找 4. 算法分析 ? 等概率下的平均查找长度： 等概 n30时，对分查找的优势不明显 3.1 基本查找技术 ? 将数据分成若干块 ? 块与块间数据有序 ? 块内数据无序 1. 算法思想 ① 将各块中的最大关键字构成一个递增有序的索引表 ② 先查找索引表(采用对分或顺序查找),以确定所在块 ③ 在所在块中进行顺序查找 3.1.3 分块查找(索引顺序查找) 3.1 基本查找技术 3.1.3 分块查找 例: 11 9 30 4 38 40 60 65 84 70 75 66 65 84 0 4 8 第1块 第2块 第3块 索引表 最大关键字 起始地址 块表 3.1 基本查找技术 2. 算法分析 3.1.3 分块查找(索引顺序查找) 平均查找长度 索引表平均查找长度 块表平均查找长度 其中，r[1:n]