分块查找法
标签: 数据结构
学习人数: 3155


全屏播放
赞赏支持

算法定义

分块查找,也叫索引顺序查找,算法实现除了需要查找表本身之外,还需要根据查找表建立一个索引表。

建立的索引表要求按照关键字进行升序排序,查找表要么整体有序,要么分块有序。

分块有序:指的是第二个子表中所有关键字都要大于第一个子表中的最大关键字,第三个子表的所有关键字都要大于第二个子表中的最大关键字,依次类推。

块(子表)中各关键字的具体顺序,根据各自可能会被查找到的概率而定。如果各关键字被查找到的概率是相等的,那么可以随机存放;否则可按照被查找概率进行降序排序,以提高算法运行效率。

 

算法原理

所有前期准备工作完成后,开始在此基础上进行分块查找。分块查找的过程分为两步进行:

1、确定要查找的关键字可能存在的具体块(子表);
2、在具体的块中进行顺序查找。

方法描述

将n个数据元素”按块有序”划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须”按块有序”;即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;...

登录查看完整内容


课后作业

掌握本节内容


登录后发布评论

暂无评论,来抢沙发