第9章查找 9.1查找的基本概念 9.2线性表的查找 提纲 9.3树表的查找 CONTENTS 9.4哈希表查找 作业 上机实验题 1/64
CONTENTS 提纲 1/64
查找的基本概念9.1一般情况下，被查找的对象称为查找表，查找表包含一组元素（或记录），每个元素由若干个数据项组成，并假设有能唯一标识元素的数据项，称为主关键字（默认按主关键字查找）。查找定义为：给定一个值k，在含有n个元素的查找表中找出关键字等于k的元素。若找到这样的元素，表示查找成功，返回该元素的信息或该元素在表中的位置；否则查找不成功或者查找失败，返回相应的指示信息。2/64
一般情况下，被查找的对象称为查找表，查找表包含一组元素（或记 录），每个元素由若干个数据项组成，并假设有能唯一标识元素的数据 项，称为主关键字（默认按主关键字查找）。 查找定义为：给定一个值k，在含有n个元素的查找表中找出关键字等于k 的元素。若找到这样的元素，表示查找成功，返回该元素的信息或该元 素在表中的位置；否则查找不成功或者查找失败，返回相应的指示信息。 2/64
查找表按照操作方式分为静态查找表和动态查找表两类。静态查找表是只作查找操作的查找表，主要操作有查询某个“特定的”数据元素是否在查找表中，检索某个“特定的”数据元素及其属性。动态查找表是在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。3/64
查找表按照操作方式分为静态查找表和动态查找表两类。 静态查找表是只作查找操作的查找表，主要操作有查询某个“特定的” 数据元素是否在查找表中，检索某个“特定的”数据元素及其属性。 动态查找表是在查找过程中同时插入查找表中不存在的数据元素，或 者从查找表中删除已经存在的某个数据元素。 3/64
查找有内查找和外查找之分。若整个查找过程都在内存进行，则称之为内查找反之，若查找过程中需要访问外存，则称之为外查找4/64
查找有内查找和外查找之分。 若整个查找过程都在内存进行，则称之为内查找。 反之，若查找过程中需要访问外存，则称之为外查找。 4/64
查找性能评价查找算法中的主要操作是关键字之间的比较，所以通常把查找过程中关键字平均比较次数也就是平均查找长度作为衡量一个查找算法效率优劣的依据。平均查找长度ASL（AverageSearchLength）定义为ASL =PiCii=1其中，n是查找表中元素的个数，p;是查找第个元素的概率，一般地，除特别指出外，均认为每个元素的查找概率相等，即pi=1/n（1≤i≤n），C;是查找到第i个元素所需的关键字比较次数。5/64
查找算法中的主要操作是关键字之间的比较，所以通常把查找过程中 关键字平均比较次数也就是平均查找长度作为衡量一个查找算法效率 优劣的依据。 平均查找长度ASL（Average Search Length）定义为 其中，n是查找表中元素的个数，pi是查找第i个元素的概率，一般 地，除特别指出外，均认为每个元素的查找概率相等，即pi=1/n （1≤i≤n），ci是查找到第i个元素所需的关键字比较次数。 查找性能评价 5/64