第七章查找 由于查找运算的使用频率很高,几乎 在任何一个计算机系统软件和应用软件中 都会涉及到,所以当问题所涉及的数据量 相当大时,查找方法的效率就显得格外重 要。在一些实时查询系统中尤其如此。因 此,本章将系统地讨论各种查找方法,并 通过对它们的效率分析来比较各种查找方 法的优劣。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 第七章 查找 由于查找运算的使用频率很高，几乎 在任何一个计算机系统软件和应用软件中 都会涉及到，所以当问题所涉及的数据量 相当大时，查找方法的效率就显得格外重 要。在一些实时查询系统中尤其如此。因 此，本章将系统地讨论各种查找方法，并 通过对它们的效率分析来比较各种查找方 法的优劣
71查找的基本概念 搜索关键 1、查找表和查找结果 一般,假定被查找的对象是由一组结点组成 的表( Table)或文件,而每个结点则由若干个 数据项组成。并假设每个结点都有一个能惟 标识该结点的关键字 查找( Searching)的定义是:给定一个值K, 在含有n个结点的表中找出关键字等于给定 值K的结点。若找到,则查找成功返回该结 点的信息或该结点在表中的位置;否则查找失 败,返回相关的指示信息。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 7.1 查找的基本概念 1、查找表和查找结果 一般，假定被查找的对象是由一组结点组成 的表( Table)或文件，而每个结点则由若干个 数据项组成。并假设每个结点都有一个能惟一 标识该结点的关键字。 查找(Searching)的定义是：给定一个值K, 在含有n个结点的表中找出关键字等于给定 值,K的结点。若找到，则查找成功,返回该结 点的信息或该结点在表中的位置;否则查找失 败，返回相关的指示信息。 搜索关键 字
2、查找方法分类 (1)动态查找和静态查找 若在查找的同时对相应的数据结构做修改操 作如插入和删除),则称之为动态查找。否则称 之为静态查找 (2)内查找和外查找 查找还有内查找和外查找之分的分类方法。若 整个查找过程都在内存中进行,则称之为内查找 反之,着查找过程中需要访问外存,则称之为外 2查找 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 （1）动态查找和静态查找 若在查找的同时对相应的数据结构做修改操 作(如插入和删除), 则称之为动态查找。否则称 之为静态查找 。 2、查找方法分类 （2）内查找和外查找 查找还有内查找和外查找之分的分类方法。若 整个查找过程都在内存中进行，则称之为内查找； 反之，若查找过程中需要访问外存，则称之为外 查找
3、平均查找长度ASL 查找运算的主要操作是关键字的比较,所以 通常把查找过程中对关键字需要执行的平均 比较次数(也称为平均查找长度作为衡量一个 查找算法效率优劣的标准 平均查找长度 ASL(Average Search Length定义 为 其中:ASL=∑PC;(1<==n) ①n是结点的个数; ②P是查找第个结点的概率。若不特别声明,认为每 个结点的查找概率相等,即pp2=P=1/m; ③c是找到第个结点所需进行的比较次数 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 3、平均查找长度ASL 查找运算的主要操作是关键字的比较，所以 通常把查找过程中对关键字需要执行的 平均 比较次数(也称为平均查找长度)作为衡量一个 查找算法效率优劣的标准。 平均查找长度 ASL(Average Search Length)定义 为： ASL=∑Pi*Ci 其中： (1<=i<=n) ①n是结点的个数； ②Pi是查找第i个结点的概率。若不特别声明，认 为每 个结点的查找概率相等，即pl=p2…=pn=1/n; ③ci是找到第i个结点所需进行的比较次数
7.2静态查找 (一)顺序查找( Sequential Search) 在表的组织方式中,线性表是最简单的一种。 顺序查找是一种最简单的查找方法。 1、顺序查找的基本思想 基本思想是:从表的一端开始,顺序扫描线性 表,依次将扫描到的结点关键宇和给定值K相比 较。若当前扫描到的结点关键字与K相等,则查 找成功若扫描结束后仍未找到关键字等于K的 结点,则查找失败 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 7.2 静态查找 在表的组织方式中，线性表是最简单的一种。 顺序查找是一种最简单的查找方法。 基本思想是：从表的一端开始, 顺序扫描线性 表，依次将扫描到的结点关键宇和给定值K相比 较。若当前扫描到的结点关键字与K相等，则查 找成功;若扫描结束后,仍未找到关键字等于K的 结点，则查找失败。 （一）顺序查找(Sequential Search) 1、顺序查找的基本思想