频道导航

【数据结构】静态查找之分块查找

2019-08-06 数据结构前端之家

前端之家收集整理的这篇文章主要介绍了【数据结构】静态查找之分块查找，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

【分块查找】

分块查找，也称索引顺序查找，是一种折半查找和顺序查找的改进方法。@H_301_4@

【思想】@H_301_4@

@H_301_4@ ①@H_301_4@ 把线性表分成若干块，每块包含若干个元素@H_301_4@

@H_301_4@ ②块内无序，块间有序。@H_301_4@
@H_301_4@

@H_301_4@ ③@H_301_4@ 建立一个索引表，把每块中的最大关键字值和每块的第一个元素在表中的位置和最后一个元素在表中的位置存放在索引项中。@H_301_4@

@H_301_4@ ④@H_301_4@ 先确定待查数据元素所在的块，然后再块内顺序查找@H_301_4@

如图：

【ASL】@H_301_4@

@H_301_4@ @H_301_4@ @H_301_4@ ASL_bs=(n/s+s)/2 +1,（其中s是每块的元素个数，n为表长）@H_301_4@ @H_301_4@

【时间复杂度】@H_301_4@

时间复杂度为O(n@H_301_4@ )~O(log@H_301_4@ ₂ n)@H_301_4@

【优缺点】@H_301_4@

（1）优点：适用范围大，顺序存储和连式存储都适用；查找效率高@H_301_4@
@H_301_4@

（2）缺点：需要将待查表分块排序，并且要增加一个存储空间用来存储索引表@H_301_4@

三大静态查找：静态查找之顺序查找

静态查找之二分查找

【小结】

原文链接：https://www.f2er.com/datastructure/382594.html

上一篇：【数据结构】静态查找之二分查找下一篇：【数据结构】链栈

猜你在找的数据结构相关文章

【数据结构】键树

键树的基本概念键树又称数字查找树（Digital Search Tree）。它是一棵度大于等于2的树，...

作者：前端之家时间：2021-02-09

【数据结构】绪论

[TOC] 基本概念数据：数据是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...

作者：前端之家时间：2021-02-09

【数据结构】证明法

[TOC] 反证法基本概念：一般地，假设原命题不成立（即在原命题的条件下，结论不成立），...

作者：前端之家时间：2021-02-09

数据结构与算法系列之目录

最近抽空整理了"数据结构和算法"的相关文章。在整理过程中，对于每种数...

作者：前端之家时间：2021-02-09

【数据结构】数组

[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...

作者：前端之家时间：2021-02-09

[操作系统]操作系统中断机制

1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...

作者：前端之家时间：2021-02-06

[日常] 浏览器前进后退与数据结构的思想

一张图保存一下红点是当前地址白色箭头是新打开页面黑色箭头是后退页面栈的思想 , 后退...

作者：前端之家时间：2021-02-06

[算法] 开放寻址法解决哈希冲突方式

开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...

作者：前端之家时间：2021-02-06

二叉树的基本概念介绍与代码实现（多图+代码）

@ 树的基本概念图1 树的结点结点：使用树结构存储的每一个数据元素都被称为“结点”。例...

作者：前端之家时间：2021-01-30

史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)

1.准备工作首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...

作者：前端之家时间：2021-01-30

编程分类

Linux Windows CentOS Ubuntu Nginx WebService Scala Memcache Apache Redis Docker Bash Azure Tomcat LNMP Shell 数据结构服务器运维网络安全

最新文章