|
|
|
对查找表经常要进行两种操作：查询某个特定的数据元素是否在查找表中；检索某个特定的数据元素的各种属性。通常只进行这两种操作的查找表称为静态查找表。静态查找表主要有顺序查找、折半查找和分块查找。
|
|
|
|
|
|
顺序查找，又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。
|
|
|
|
|
|
|
|
|
|
折半查找是一种采用顺序存储结构的线性表进行查找的方法，也称二分查找。在进行折半查找之前，线性表中的数据元素必须按照关键字的值升序或降序排列。
|
|
|
|
折半查找的过程是先将给定值与有序线性表中间位置上的元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。平均查找长度为：
|
|
|
|
|
|
|
|
分块查找又称索引顺序查找，是顺序查找的一种改进方法。在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块，然后在块中顺序查找。
|
|
|
|
假设长度为n的分块表分成b块，每块中元素个数为s，又设每个元素的查找概率都相等，块间块内均采用线性查找方法，则平均查找长度为：
|
|
|
|
|
