83 第9 章 查找 9 .1 知识点分析 1. 基本概念 （1）查找表 由同一类型的数据元素（或记录）构成的集合称为查找表。 （2）静态查找 在查找过程中仅查找某个特定元素是否存在或它的属性的，称为静态查找。 （3）动态查找 在查找过程中对查找表进行插入元素或删除元素操作的，称为动态查找。 （4）关键字 关键字是数据元素（或记录）中某个数据项的值，用它可以标识数据元素（或记录）。关键字分主关键字（唯一地标识一个记录的关键字）和次关键字（标识若干个记录的关键字）。 （5）查找 在查找表中确定是否存在一个数据元素的关键字等于给定值的操作，称为查找（也称为检索）。 （6）内查找、外查找 整个查找过程全部在内存进行，则称为内查找；若在查找过程中还需要访问外存，则称为外查找。 （7）平均查找长度 ASL 查找成功时平均查找长度： 其中：Pi为找到表中第i 个数据元素的概率，且有： Ci为查找表中第i 个数据元素所用到的比较次数。不同的查找方法有不同的Ci。 2．顺序查找 顺序查找又称线性查找，是最基本的查找方法之一。顺序查找既适用于顺序表，也适用于链表。顺序查找的基本思想：从表的一端开始，顺序扫描线性表，依次按给定值kx与关键字（Key）进行比较，若相等，则查找成功，并给出数据元素在表中的位置；若整个表查找完毕，仍未找到与 kx相同的关键字，则查找失败，给出失败信息。 3．二分查找 二分查找也叫折半查找，是一种效率较高的查找方法，但前提是表中元素必须按关键字有序（按关键字递增或递减）排列。二分查找的基本思想：在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定值大于中间元素的关键字，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。 4．分块查找 将具有 n个元素的主表分成m 个块（也称为子表），每块内的元素可以无序，但要求块niiiCPASL111niiP 84 与块之间必须有序，并建立索引表。索引表包括两个字段：关键字字段 (存放对应块中的最大关键字值) 和指针字段 (存放指向对应块的首地址) 。查找方法如下： （1）在索引表中检测关键字字段，以确定待找值kx 所处的分块（可用二分查找）位置； （2）根据索引表指示的首地址，在该块内进行顺序查找。 5．二叉排序树（Binary So...
