|
|
| 查找是一种常用的基本运算。查找表是指由同一类型的数据元素构成的集合。
|
|
|
| .静态查找表。对查找表经常要进行的两种操作是查询和检索。
|
|
|
| .动态查找表。对查找表经常要进行的操作是插入和删除。
|
|
|
| .关键字。数据元素的某个数据项的值，用它来识别这个数据元素。
|
|
|
|
|
|
|
| .查找。根据给定的某个值，在查找表中确定是否存在一个其关键字等于给定值的记录或数据元素的过程称为查找。
|
|
|
|
|
| 通常以"其关键字和给定值进行过比较的记录个数的平均值"作为衡量查找算法好坏的依据。
|
|
|
| 平均查找长度：为确定记录在查找表中的位置，须与给定关键字值进行比较的次数的数学期望称为查找算法在查找成功时的平均查找长度。
|
|
|
|
|
|
|
式中，pi为对表中第i个记录进行查找的概率，且 。一般情况下，均认为查找每个记录的概率是相等的，即pi=1/n。
|
|
|
