例如要找关键字为k的元素,则先用折半查找法由索引表查出k所在的块,再 用顺序查找法在对应的块中找出k。在图8-2中若要找关键字值为41的元 素,则先由索引表查出41在第二块中(29<41<64),再在第二块中找到 由此我们可以总结:分块查找分两步进行,第一步确定要查找结点在表中的 哪一块,第二步在确定的块中找到该结点 分块查找的平均查找长度为: ASL=ASLb+ASLe 其中ASLb是折半查找的平均查找长度,ASLe是用顺序查找法查块内元素的 平均查找长度。设每块中有s个元素,可以近似的得到: 可以看出分块查找的平均查找长度位于顺序查找和折半查找之间 下面我们简单的对以上几种查找方法做出比较: (1)平均查找长度:折半查找最小,分块查找次之,顺序查找最大 (2)表的结构:顺序查找对有序表、无序表均适用;折半查找仅适用于有 序表;分块查找要求表中元素是逐段有序的,就是块与块之间的记录按 关键字有序; (3)存储结构:顺序查找和分块查找对向量和线性链表结构均适用;折半 查找只适用于向量存储结构的表,因而要求表中元素基本不变,而在需 要插入或删除运算时,要移动元素,才能保持表的有序性,所以影响了 查找效率例如要找关键字为k的元素，则先用折半查找法由索引表查出k所在的块，再 用顺序查找法在对应的块中找出k。在图8-2中若要找关键字值为41的元 素，则先由索引表查出41在第二块中（29<41<64），再在第二块中找到 41。 由此我们可以总结：分块查找分两步进行，第一步确定要查找结点在表中的 哪一块，第二步在确定的块中找到该结点。 分块查找的平均查找长度为： ASL=ASLb+ASLe 其中ASLb是折半查找的平均查找长度，ASLe是用顺序查找法查块内元素的 平均查找长度。设每块中有s个元素，可以近似的得到： 可以看出分块查找的平均查找长度位于顺序查找和折半查找之间。 下面我们简单的对以上几种查找方法做出比较： （1）平均查找长度：折半查找最小，分块查找次之，顺序查找最大； （2）表的结构：顺序查找对有序表、无序表均适用；折半查找仅适用于有 序表；分块查找要求表中元素是逐段有序的，就是块与块之间的记录按 关键字有序； （3）存储结构：顺序查找和分块查找对向量和线性链表结构均适用；折半 查找只适用于向量存储结构的表，因而要求表中元素基本不变，而在需 要插入或删除运算时，要移动元素，才能保持表的有序性，所以影响了 查找效率