[工学]search.ppt

计算机软件技术基础 §3.1 查找 也称检索 从大量的数据中找出所需要的数据。 不是一种数据结构，而是一种辅助性运算，技术 关键字： 数据元素中可以唯一标识一个数据元素的数据项。 定义： 查找 就是根据给定的关键字值，在一组数据中确定一个 其关键字值等于给定值的数据元素。 若存在这样的数据元素，则称查找是成功的； 否则查找不成功。 查找的两个问题 １．查找的方法： 依赖于该组数据的组织方式。 为提高查找效率，要求数据元素采用某些特殊的组织方式。 查找的两个问题 2.查找算法的评价 ⑴空间复杂度： 一般只需要一个或几个辅助空间，不重要。 ⑵时间复杂度： 基本运算是给定值与关键字值的比较 平均查找长度ASL： 定义 对于含有 n 个数据元素的查找表， 查找成功的平均查找长度为 ASL = 常用的查找方法 依赖于该组数据的组织方式。 一、简单查找方法 适合于以向量或线性链表作存储结构的顺序表 １.顺序查找 ss 2.二分查找 bs 3.分块查找 二、哈希查找 三、树表查找 一 、简单查找 （一）顺序查找 1.从第一个元素开始逐个把数据元素的关键字值和给定值比较，直到两者符合，则查找成功；找不到，说明不存在满足条件的数据元素，查找失败。 顺序查找适合于顺序存储结构组织的查找表，也适合于链式存储结构组织的查找表 2.算法（略） 3. 顺序查找性能分析 （1）比较次数： 最好情况 i = 1, ci = 1 次； 最坏情况 i = n, ci = n 次 （2）平均查找长度: 设查找各元素为等概率 pi=1/n 第i个数据元素需比较 ci = i 次 ASLss=∑pi ci =(1+2+3+……+n)/n= (n+1)/2 约为线性表长度的一半，效率不高，适合于短表 （二）对分查找 1、折半查找 .查找表需要按关键字有序 I过程：先确定待查记录所在的范围（区间）， 然后逐步缩小范围，直到成功或失败为止 （二）对分查找 II步骤：设待查元素所在区域的下界为low，上界为high，则中间位置mid=(low+high) ①若此元素关键字值等于给定值，则查找成功 ②若大于给定值,则在区域 mid+1~high 内二分查找； ③若小于给定值,则在区域 low~ mid-－1 内二分查找，重复上述过程 对分查找函数 int B_search(SqList R,KeyType K) { int low=1;int high=n,mid; While(low=high) { mid=(low+high)/2; If(R[mid].key=K)return mid; If(R[mid].keyK)high=mid-1; else low=mid+11; } return 0; } （3）性能分析* 假设表长 n = 2h －1, 查找各元素为等概率 pi=1/n，此处h 是满二叉树的高度 第一层结点数 1=20 查找各元素需比较1 次 第二层结点数 2=21 需比较2 次 第三层结点数 4=22 需比较3 次 第j层结点数 2j-1 需比较j 次 第h层结点数 2h-1 需比较h 次 平均查找长度 当n足够大时，可以得到它的近似值： ASLbs≈ Log2(n+1)－1 （三）分块查找 1、索引顺序查找 ⑴ 基本思想 ① 将数据元素均匀的分成几块， 各块之间按大小排序， 块内元素不排序 ②建立一个块的最大（或最小）索引关键字表，有序 ③查找分为两步： 第一步：先用待查关键字对索引关键字表进行二分查找 或顺序查找，确定待查数据元素可能在哪一块。 第二步：在已经确定的那一块中进行顺序查找。 整个过程由上述两步查找合成 （2）性能分析 分块查找的平均查找长度 ASL = ASLbs + ASLss 设每块有S个数据元素，比较 分块查找 ASL = Log2(n/S + 1) + S/2