天天看点

经典算法题每日演练——第二十五题 块状链表

  在数据结构的世界里,我们会认识各种各样的数据结构,每一种数据结构都能解决相应领域的问题,每一种数据结构都像

是降龙十八掌中的某一掌,掌掌毙命。。。 当然每个数据结构,有他的优点,必然就有它的缺点,那么如何创造一种数据结构

来将某两种数据结构进行扬长避短,那就非常完美了。这样的数据结构也有很多,比如:双端队列,还有就是今天讲的 块状链表,

   我们都知道 数组 具有 o(1)的查询时间,o(n)的删除,o(n)的插入。。。

                   链表 具有 o(n)的查询时间,o(1)的删除,o(1)的插入。。。 

   那么现在我们就有想法了,何不让“链表”和“数组”结合起来,来一起均摊curd的时间,做法将数组进行分块,然后用指针相连接,

比如我有n=100个元素,那么最理想情况下,我就可以将数组分成x=10段,每段b=10个元素(排好序),那么我可以用√n的时

间找到段,因为段中的元素是已经排好序的,所以可以用lg√n的时间找到段中的元素,那么最理想的复杂度为√n+lg√n≈√n。。。

   下面我们看看怎么具体使用:

一:结构定义

    这个比较简单,我们在每个链表节点中定义一个 头指针,尾指针 和 一个数组节点。

二: 插入

  刚才也说了,每个链表节点的数据是一个数组块,那么问题来了,我们是根据什么将数组切开呢?总不能将所有的数据都放在一个

链表的节点吧,那就退化成数组了,在理想的情况下,为了保持√n的数组个数,所以我们定了一个界限2√n,当链表中的节点数组

的个数超过2√n的时候,当下次插入数据的时候,我们有两种做法:

① 在元素的数组插入处,将当前数组切开,插入元素处之前为一个链表节点,插入元素后为一个链表节点。

② 将元素插入数组后,将数组从中间位置切开。

经典算法题每日演练——第二十五题 块状链表

二:删除

   跟插入道理一样,既然有裂开,就有合并,同样也定义了一个界限值√n /2  ,当链表数组节点的数组个数小于这个界限值

的时候,需要将此节点和后面的链表节点进行合并。

经典算法题每日演练——第二十五题 块状链表

四: 查询

    在理想的情况下,我们都控制在√n,然后就可以用√n的时间找到区块,lg√n的时间找到区块中的指定值,当然也有人在查询

的时候做 链表的合并和分裂,这个就有点像伸展树一样,在查询的时候动态调整,拼的是均摊情况下的复杂度。这里顺便提醒你一

下,其实你也可以这么做。。。

好了,curd都分析好了,到这里大家应该对 块状链表 有个大概的认识了吧,这个代码是我下午抽闲写的,没有仔细测试,

最后是总的代码: