加载中...

第二十五题 块状链表


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

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

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

   我们都知道 数组 具有 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的时候,当下次插入数据的时候,我们有两种做法:

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

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

/// <summary>
        /// 添加元素只会进行块状链表的分裂
        /// </summary>
        /// <param name="node"></param>
        /// <param name="num"></param>
        /// <returns></returns>
        private BlockLinkNode Add(BlockLinkNode node, int num)
        {
            if (node == null)
            {
                return node;
            }
            else
            {
                /*
                 *  第一步:找到指定的节点
                 */
                if (node.list.Count == 0)
                {
                    node.list.Add(num);

                    total = total + 1;

                    return node;
                }

                //下一步:再比较是否应该分裂块
                var blockLen = (int)Math.Ceiling(Math.Sqrt(total)) * 2;

                //如果该节点的数组的最后位置值大于插入值,则此时我们找到了链表的插入节点,
                //或者该节点的next=null,说明是最后一个节点,此时也要判断是否要裂开
                if (node.list[node.list.Count - 1] > num || node.next == null)
                {
                    node.list.Add(num);

                    //最后进行排序下,当然可以用插入排序解决,O(N)搞定
                    node.list = node.list.OrderBy(i => i).ToList();

                    //如果该数组里面的个数大于2*blockLen,说明已经过大了,此时需要对半分裂
                    if (node.list.Count > blockLen)
                    {
                        //先将数据插入到数据库
                        var mid = node.list.Count / 2;

                        //分裂处的前段部分
                        var firstList = new List<int>();

                        //分裂后的后段部分
                        var lastList = new List<int>();

                        //可以在插入点处分裂,也可以对半分裂(这里对半分裂)
                        firstList.AddRange(node.list.Take(mid));
                        lastList.AddRange(node.list.Skip(mid).Take(node.list.Count - mid));


                        //开始分裂节点,需要新开辟一个新节点
                        var nNode = new BlockLinkNode();

                        nNode.list = lastList;
                        nNode.next = node.next;
                        nNode.prev = node;

                        //改变当前节点的next和list
                        node.list = firstList;
                        node.next = nNode;
                    }

                    total = total + 1;

                    return node;
                }

                return Add(node.next, num);
            }
        }

二:删除

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

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

四: 查询

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

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

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

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

最后是总的代码:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication3
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> list = new List<int>() { 8959, 30290, 18854, 7418, 28749, 17313, 5877, 27208, 15771, 4335 };

            //list.Clear();

            //List<int> list = new List<int>();

            //for (int i = 0; i < 100; i++)
            //{
            //    var num = new Random((int)DateTime.Now.Ticks).Next(0, short.MaxValue);

            //    System.Threading.Thread.Sleep(1);

            //    list.Add(num);
            //}


            BlockLinkList blockList = new BlockLinkList();

            foreach (var item in list)
            {
                blockList.Add(item);
            }

            //var b = blockList.IsExist(333);
            //blockList.GetCount();

            Console.WriteLine(blockList.Get(27208));


            #region MyRegion
            ////随机删除150个元素
            //for (int i = 0; i < 5000; i++)
            //{
            //    var rand = new Random((int)DateTime.Now.Ticks).Next(0, list.Count);

            //    System.Threading.Thread.Sleep(2);

            //    Console.WriteLine("\n**************************************\n当前要删除元素:{0}", list[rand]);

            //    blockList.Remove(list[rand]);

            //    Console.WriteLine("\n\n");

            //    if (blockList.GetCount() == 0)
            //    {
            //        Console.Read();
            //        return;
            //    }
            //} 
            #endregion

            Console.Read();
        }
    }

    public class BlockLinkList
    {
        BlockLinkNode blockLinkNode = null;

        public BlockLinkList()
        {
            //初始化节点
            blockLinkNode = new BlockLinkNode()
            {
                list = new List<int>(),
                next = null,
                prev = null
            };
        }

        /// <summary>
        /// 定义块状链表的总长度
        /// </summary>
        private int total;

        public class BlockLinkNode
        {
            /// <summary>
            /// 指向前一个节点的指针
            /// </summary>
            public BlockLinkNode prev;

            /// <summary>
            /// 指向后一个节点的指针
            /// </summary>
            public BlockLinkNode next;

            /// <summary>
            /// 链表中的数组
            /// </summary>
            public List<int> list;
        }

        /// <summary>
        /// 判断指定元素是否存在
        /// </summary>
        /// <param name="num"></param>
        /// <returns></returns>
        public bool IsExist(int num)
        {
            var isExist = false;

            var temp = blockLinkNode;

            while (temp != null)
            {
                //判断是否在该区间内
                if (temp.list.Count > 0 && num >= temp.list[0] && num <= temp.list[temp.list.Count - 1])
                {
                    isExist = temp.list.IndexOf(num) > 0 ? true : false;

                    return isExist;
                }

                temp = temp.next;
            }

            return isExist;
        }

        public string Get(int num)
        {
            var blockIndex = 0;
            var arrIndex = 0;

            var temp = blockLinkNode;

            while (temp != null)
            {
                //判断是否在该区间内
                if (temp.list.Count > 0 && num >= temp.list[0] && num <= temp.list[temp.list.Count - 1])
                {
                    arrIndex = temp.list.IndexOf(num);

                    return string.Format("当前数据在第{0}块中的{1}个位置", blockIndex, arrIndex);
                }

                blockIndex = blockIndex + 1;
                temp = temp.next;
            }

            return string.Empty;
        }

        /// <summary>
        /// 将元素加入到块状链表中
        /// </summary>
        /// <param name="num"></param>
        public BlockLinkNode Add(int num)
        {
            return Add(blockLinkNode, num);
        }

        /// <summary>
        /// 添加元素只会进行块状链表的分裂
        /// </summary>
        /// <param name="node"></param>
        /// <param name="num"></param>
        /// <returns></returns>
        private BlockLinkNode Add(BlockLinkNode node, int num)
        {
            if (node == null)
            {
                return node;
            }
            else
            {
                /*
                 *  第一步:找到指定的节点
                 */
                if (node.list.Count == 0)
                {
                    node.list.Add(num);

                    total = total + 1;

                    return node;
                }

                //下一步:再比较是否应该分裂块
                var blockLen = (int)Math.Ceiling(Math.Sqrt(total)) * 2;

                //如果该节点的数组的最后位置值大于插入值,则此时我们找到了链表的插入节点,
                //或者该节点的next=null,说明是最后一个节点,此时也要判断是否要裂开
                if (node.list[node.list.Count - 1] > num || node.next == null)
                {
                    node.list.Add(num);

                    //最后进行排序下,当然可以用插入排序解决,O(N)搞定
                    node.list = node.list.OrderBy(i => i).ToList();

                    //如果该数组里面的个数大于2*blockLen,说明已经过大了,此时需要对半分裂
                    if (node.list.Count > blockLen)
                    {
                        //先将数据插入到数据库
                        var mid = node.list.Count / 2;

                        //分裂处的前段部分
                        var firstList = new List<int>();

                        //分裂后的后段部分
                        var lastList = new List<int>();

                        //可以在插入点处分裂,也可以对半分裂(这里对半分裂)
                        firstList.AddRange(node.list.Take(mid));
                        lastList.AddRange(node.list.Skip(mid).Take(node.list.Count - mid));


                        //开始分裂节点,需要新开辟一个新节点
                        var nNode = new BlockLinkNode();

                        nNode.list = lastList;
                        nNode.next = node.next;
                        nNode.prev = node;

                        //改变当前节点的next和list
                        node.list = firstList;
                        node.next = nNode;
                    }

                    total = total + 1;

                    return node;
                }

                return Add(node.next, num);
            }
        }

        /// <summary>
        /// 从块状链表中移除元素
        /// </summary>
        /// <param name="num"></param>
        /// <returns></returns>
        public BlockLinkNode Remove(int num)
        {
            return Remove(blockLinkNode, num);
        }

        /// <summary>
        /// 从块状链表中移除元素,涉及到合并
        /// </summary>
        /// <param name="node"></param>
        /// <param name="num"></param>
        /// <returns></returns>
        private BlockLinkNode Remove(BlockLinkNode node, int num)
        {
            if (node == null)
            {
                return node;
            }
            else
            {
                //第一步: 判断删除元素是否在该节点内
                if (node.list.Count > 0 && num >= node.list[0] && num <= node.list[node.list.Count - 1])
                {
                    //定义改节点的目的在于防止remove方法假删除的情况发生
                    var prevcount = node.list.Count;

                    node.list.Remove(num);

                    total = total - (prevcount - node.list.Count);

                    //下一步: 判断是否需要合并节点
                    var blockLen = (int)Math.Ceiling(Math.Sqrt(total) / 2);

                    //如果当前节点的数组个数小于 blocklen的话,那么此时改节点需要和后一个节点进行合并
                    //如果该节点时尾节点,则放弃合并
                    if (node.list.Count < blockLen)
                    {
                        if (node.next != null)
                        {
                            node.list.AddRange(node.next.list);

                            //如果下一个节点的下一个节点不为null,则将下下个节点的prev赋值
                            if (node.next.next != null)
                                node.next.next.prev = node;

                            node.next = node.next.next;
                        }
                        else
                        {
                            //最后一个节点不需要合并,如果list=0,则直接剔除该节点
                            if (node.list.Count == 0)
                            {
                                if (node.prev != null)
                                    node.prev.next = null;

                                node = null;
                            }
                        }
                    }

                    return node;
                }

                return Remove(node.next, num);
            }
        }

        /// <summary>
        /// 获取块状链表中的所有个数
        /// </summary>
        /// <returns></returns>
        public int GetCount()
        {
            int count = 0;

            var temp = blockLinkNode;

            Console.Write("各节点数据个数为:");

            while (temp != null)
            {
                count += temp.list.Count;

                Console.Write(temp.list.Count + ",");

                temp = temp.next;
            }

            Console.WriteLine("总共有:{0} 个元素", count);

            return count;
        }
    }
}


还没有评论.