|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
对查找表经常要进行两种操作：查询某个特定的数据元素是否在查找表中；检索某个特定的数据元素的各种属性。通常只进行这两种操作的查找表称为静态查找表。静态查找表主要有顺序查找、折半查找和分块查找。
|
|
|
|
|
|
顺序查找，又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。
|
|
|
|
|
|
|
|
|
|
折半查找是一种采用顺序存储结构的线性表进行查找的方法，也称二分查找。在进行折半查找之前，线性表中的数据元素必须按照关键字的值升序或降序排列。
|
|
|
|
折半查找的过程是先将给定值与有序线性表中间位置上的元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。平均查找长度为：
|
|
|
|
|
|
|
|
分块查找又称索引顺序查找，是顺序查找的一种改进方法。在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块，然后在块中顺序查找。
|
|
|
|
假设长度为n的分块表分成b块，每块中元素个数为s，又设每个元素的查找概率都相等，块间块内均采用线性查找方法，则平均查找长度为：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
顺序查找又称线性查找，顺序查找的过程是从线性表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；若表中所有元素的关键字与给定值比较都不成功，则查找失败。
|
|
|
|
|
|
折半查找的过程是先将给定值与有序线性表中间位置上元素的关键字进行比较，若两者相等，则查找成功；若给定值小于该元素的关键字，那么选取中间位置元素关键字值小的那部分元素作为新的查找范围，然后继续进行折半查找；如果给定值大于该元素的关键字，那么选取比中间位置元素关键字值大的那部分元素作为新的查找范围，然后继续进行折半查找，直到找到关键字与给定值相等的元素或查找范围中的元素数量为零时结束。
|
|
|
|
|
|
在分块查找过程中，首先将表分成若干块，每一块中关键字不一定有序，但块之间是有序的。此外，还建立了一个索引表，索引表按关键字有序。分块查找过程需分两步进行：先确定待查记录所在的块；然后在块中顺序查找。
|
|
|
|
|
|
根据设定的哈希函数H（key）和处理冲突的方法，将一组关键字映射到一个有限的连续地址集上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，也称散列表。这一过程所得到的存储位置称为散列地址，由此形成的查找方法称为散列查找。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
从表中的一端开始，逐个进行记录的关键字和给定值的比较，若找到一个记录的关键字与给定值相等，则查找成功；若整个表中的记录均比较过，仍未找到关键字等于给定值的记录，则查找失败。
|
|
|
|
顺序查找的方法对于顺序存储和链式存储方式的查找表都适用。
|
|
|
|
从顺序查找的过程可见，Ci取决于所查记录在表中的位置。若需查找的记录正好是表中的第一个记录时，仅需比较一次；若查找成功时找到的是表中的最后一个记录，则需比较n次。一般情况下，Ci=n-i+1，因此在等概率情况下，顺序查找成功的平均查找长度为：
|
|
|
|
|
|
也就是说，成功查找的平均比较次数约为表长的一半。若所查记录不在表中，则至少进行n次比较才能确定失败。
|
|
|
|
与其他查找方法相比，顺序查找方法在n值较大时，其平均查找长度较大，查找效率较低。但这种方法也有优点，那就是算法简单且适应面广，对查找表的结构没有要求，无论记录是否按关键字有序排列均可应用。
|
|
|
|
|
|
|
|
|
|
|
|
|
