河池学院：《数据结构》课程电子教案（PPT教学课件）第9章 查找 9.1 查找的基本概念 9.2 线性表的查找

第9章查找 9.1查找的基本概念 9.2线性表的查找 提纲 9.3树表的查找 CONTENTS 9.4哈希表查找 作业 上机实验题 1/64

CONTENTS 提纲 1/64

一般情况下，被查找的对象称为查找表，查找表包含一组元素（或记 录），每个元素由若干个数据项组成，并假设有能唯一标识元素的数据 项，称为主关键字（默认按主关键字查找）。 查找定义为：给定一个值k，在含有n个元素的查找表中找出关键字等于k 的元素。若找到这样的元素，表示查找成功，返回该元素的信息或该元 素在表中的位置；否则查找不成功或者查找失败，返回相应的指示信息。 2/64

查找表按照操作方式分为静态查找表和动态查找表两类。 静态查找表是只作查找操作的查找表，主要操作有查询某个“特定的” 数据元素是否在查找表中，检索某个“特定的”数据元素及其属性。 动态查找表是在查找过程中同时插入查找表中不存在的数据元素，或 者从查找表中删除已经存在的某个数据元素。 3/64

查找有内查找和外查找之分。 若整个查找过程都在内存进行，则称之为内查找。 反之，若查找过程中需要访问外存，则称之为外查找。 4/64

查找算法中的主要操作是关键字之间的比较，所以通常把查找过程中 关键字平均比较次数也就是平均查找长度作为衡量一个查找算法效率 优劣的依据。 平均查找长度ASL（Average Search Length）定义为 其中，n是查找表中元素的个数，pi是查找第i个元素的概率，一般 地，除特别指出外，均认为每个元素的查找概率相等，即pi=1/n （1≤i≤n），ci是查找到第i个元素所需的关键字比较次数。 查找性能评价 5/64

由于查找的结果有查找成功和不成功两种情况，所以平均查找长度也 分为成功情况下的平均查找长度和不成功情况下的平均查找长度。 成功情况下的平均查找长度指在查找表中找到指定关键字k的元素平 均所需关键字比较的次数。 不成功情况下的平均查找长度指在查找表中确定找不到关键字k的元 素平均所需关键字比较的次数。 6/64

查找表T：含有n个记录。 成功情况下（概率相等）的平均查找长度ASL成功是指找到T中任一记录平均 需要的关键字比较次数。 关键字 5 1 4 8 7 9 2 4 3 找到时的比较 次数 1 2 3 4 5 6 7 8 9 ASL成功= 1+2+3+4+5+6+7+8+9 9 = 5 例如： 7/64

查找表T：含有n个记录。 不成功情况下的平均查找长度ASL不成功是指查找失败（在T中未查找到）平均 需要的关键字比较次数。 x  T 通过关键字比较后确定不在T中 平均关键字比较次数 8/64

线性表采用顺序表存储，由于顺序表不适合数据修改操作（插入和删除 元素几乎需要移动一半的元素） 顺序表是一种静态查找表。 三种线性表查找方法，即顺序查找、折半查找和分块查找算法。 9/64

顺序表中元素的类型 class RecType //顺序表元素类型 { int key; //存放关键字，假设关键字为int类型 String data; //存放其他数据，假设为String类型 public RecType(int d) //构造方法 { key=d; } } 10/64