【数据结构】静态查找之分块查找
发布时间：2020-12-15 06:00:05 所属栏目：安全 来源：网络整理
导读：【分块查找】 分块查找，也称索引顺序查找，是一种折半查找和顺序查找的改进方法。 【思想】 ① 把线性表分成若干块，每块包含若干个元素 ②块内无序，块间有序。 ③ 建立一个索引表，把每块中的最大关键字值和每块的第一个元素在表中的位置和最后一个元素在
|
【分块查找】
分块查找，也称索引顺序查找，是一种折半查找和顺序查找的改进方法。
【思想】
①
把线性表分成若干块，每块包含若干个元素
②块内无序，块间有序。
③
建立一个索引表，把每块中的最大关键字值和每块的第一个元素在表中的位置和最后一个元素在表中的位置存放在索引项中。
④
先确定待查数据元素所在的块，然后再块内顺序查找
如图：
【ASL】
ASLbs=(n/s+s)/2 +1,（其中s是每块的元素个数，n为表长）
【时间复杂度】
时间复杂度为O(n
)~O(log
2
n)
【优缺点】
（1）优点：适用范围大，顺序存储和连式存储都适用；查找效率高
（2）缺点：需要将待查表分块排序，并且要增加一个存储空间用来存储索引表
三大静态查找：
静态查找之顺序查找
静态查找之二分查找
【小结】
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |