扫码获取更多资源

●查找的基本概念

在查找和排序问题中，通常将数据元素称为记录(Record) o涉及的记录类型定义如下：

2、数据元素：数据元素是数据的基本单位，但不是最小单位。在程序中通常作为一个整体来进行考虑和处理，又称为记录。

查找表

查找表(Search Table)是由同一类型的记录构成的集合。由于“集合”中树记录之间的 关系进行限定，因此在实现时可以根据实际应用对查找操作的要求及记录附加各种约束关 系。对査找表经常进行的操作有：

•查询某个“特定的”记录是否在表中；

•检索某个“特定的”记录的各种属性；

•在查找表中插入一个记录；

•在查找表中删除某个记录。

查找分类

静态查找

不涉及插入和删除操作的查找称为静态查找(Static Search),静态查找在查找失败时 只返回一个不成功标志，查找的结果不改变查找表。

关键字

关键字(Key)又称关键码，是记录中某个数据项的值，用它可以标识一个记录。如果关 键字可以唯一标识一个记录，则称此关键字为主关键字(Primary Key);反之，用于识别若 干记录的关键字称为次关键字(Secondary Key) o

查找

査找(Searching)是根据给定的某个值，在查找表中确定一个其关键字等于给定值的记 录。如果表中存在这个记录，则称查找成功，此时查找结果会给岀整个记录的信息，或指示 其在查找表中的位置；如果表中不存在这个记录，则称查找失败，此时查找结果可以给出一 个“空”记录或“空”指针。

查找结构

一般而言，各种数据结构都会涉及查找操作，如前面介绍的线性表、树与图等。在这些 数据结构中，查找操作并没有作为主要操作考虑，其实现服从于数据结构。但在某些应用 中，査找操作是最主要的操作，为了提高查找效率，需要专门为查找操作设置数据结构，这种 面向査找操作的数据结构称为査找结构(Search Structure)。

平均查找长度

查找运算的主要操作是将记录的关键字与给定值进行比较，其执行时间通常取决于关 键字的比较次数。因此，常以关键字与给定值进行比较的平均次数作为衡量查找算法效率 优劣的标准。为了确定要查找的记录位置，与给定值进行比较的关键字个数的期望值称为 查找算法在查找成功时的平均查找长度(Average Search Length, ASL) o

静态查找表

静态查找表的特点是：表结构在查找之前已生成。如果表中存在关键字等于给定值的 记录，则查找成功并返回其在表中位置；否则给岀相应信息。静态查找可以采用顺序查找 技术、折半查找技术和分块查找技术。在表的组织方式中，静态査找表是最简单的一种。

联系我们：