|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 > 查找 >
|
|
相关知识点：12个
|
|
|
|
|
查找表是指由同一类型的数据元素（或记录）构成的集合。由于“集合”这种数据结构中的数据元素之间存在着完全松散的关系，因此，查找表是一种非常灵活的数据结构，分为静态查找表和动态查找表，哈希表是一种动态查找表。
|
|
|
|
（1）静态查找表。对查找表经常要进行的两种操作如下：
|
|
|
|
|
|
|
|
|
|
（2）动态查找表。对查找表经常要进行的另外两种操作如下：
|
|
|
|
|
|
|
|
若在查找过程中还可能插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称相应的查找表为动态查找表。
|
|
|
|
（3）关键字。关键字是数据元素（或记录）的某个数据项的值，用它来识别（标识）这个数据元素（或记录）。主关键字是指能唯一标识一个数据元素的关键字；次关键字是指能标识多个数据元素的关键字。
|
|
|
|
（4）查找。根据给定的某个值，在查找表中确定是否存在一个其关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找成功，此时或者给出整个记录的信息，或者指出记录在查找表中的位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时的查找结果用一个“空记录”或“空指针”表示。
|
|
|
|
（5）平均查找长度。对于查找算法来说，其基本操作是“将记录的关键字与给定值进行比较”。因此，通常以“其关键字和给定值进行过比较的记录个数的平均值”作为衡量查找算法好坏的依据。
|
|
|
|
为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。
|
|
|
|
对于含有n个记录的表，查找成功时的平均查找长度定义为：
|
|
|
|
|
其中，Pi为对表中第i个记录进行查找的概率，且 ，一般情况下，均认为查找每个记录的概率是相等的，即Pi=1/n；Ci为找到表中其关键字与给定值相等的记录时（为第i个记录），和给定值已进行过比较的关键字个数。显然，Ci随查找方法的不同而不同。
|
|
|
