4.1 查找基本概念

查找基本概念

查找是数据结构与算法中的基本操作。

查找表

定义：由同一类型的数据元素构成的集合。

对查找表可以进行多种操作：

1. 查询某个特定数据元素是否在表内
2. 检索某个特定数据元素的各种属性
3. 插入一个数据元素
4. 删去一个数据元素

查找的分类

分类依据	类别	说明
查找方法	基于关键字比较	顺序查找、折半查找、分块查找、BST等
查找方法	基于关键字存储位置	散列法（哈希）
存储位置	内查找	整个过程在内存中进行
存储位置	外查找	需要访问外存
是否改变集合	静态查找	数据集合固定不变
是否改变集合	动态查找	数据集合会变化，需要频繁插入删除查找

概念

1. 主关键字：可以识别唯一的一个记录的数据项（一对一）
2. 次关键字：可以识别若干记录的数据项（一对多）
3. 查找：根据某个指定值，在查找表中确定关键字等于给定值的数据元素
4. 查找成功：查找表中存在满足条件的记录
5. 查找失败：查找表中不存在满足条件的记录

链接到

• 上一个知识点：无（本章第一个知识点）
• 下一个知识点：4.2 静态查找表