第二十五题 块状链表

在数据结构的世界里，我们会认识各种各样的数据结构，每一种数据结构都能解决相应领域的问题，每一种数据结构都像 是降龙十八掌中的某一掌，掌掌毙命。。。 当然每个数据结构，有他的优点，必然就有它的缺点，那么如何创造一种数据结构

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

  1. 我们都知道 数组 具有 O(1)的查询时间，O(N)的删除，O(N)的插入。。。 
  3.                 链表 具有 O(N)的查询时间，O(1)的删除，O(1)的插入。。。  
  5. 那么现在我们就有想法了，何不让“链表”和“数组”结合起来，来一起均摊CURD的时间，做法将数组进行分块，然后用指针相连接，

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

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

  1. 下面我们看看怎么具体使用： 
  3.  这个比较简单，我们在每个链表节点中定义一个 头指针，尾指针 和 一个数组节点。

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

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

  1. 跟插入道理一样，既然有裂开，就有合并，同样也定义了一个界限值√N /2  ，当链表数组节点的数组个数小于这个界限值 
  3.  在理想的情况下，我们都控制在√N，然后就可以用√N的时间找到区块，lg√N的时间找到区块中的指定值，当然也有人在查询

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

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

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

最后是总的代码： 

  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5.  
  6. namespace ConsoleApplication3
  7. {
  8.     class Program
  9.     {
  10.         static void Main(string[] args)
  11.         {
  12.             List<int> list = new List<int>() { 8959, 30290, 18854, 7418, 28749, 17313, 5877, 27208, 15771, 4335 };
  13.  
  14.             //list.Clear();
  15.  
  16.             //List<int> list = new List<int>();
  17.  
  18.             //for (int i = 0; i < 100; i++)
  19.             //{
  20.             //    var num = new Random((int)DateTime.Now.Ticks).Next(0, short.MaxValue);
  21.  
  22.             //    System.Threading.Thread.Sleep(1);
  23.  
  24.             //    list.Add(num);
  25.             //}
  26.  
  27.  
  28.             BlockLinkList blockList = new BlockLinkList();
  29.  
  30.             foreach (var item in list)
  31.             {
  32.                 blockList.Add(item);
  33.             }
  34.  
  35.             //var b = blockList.IsExist(333);
  36.             //blockList.GetCount();
  37.  
  38.             Console.WriteLine(blockList.Get(27208));
  39.  
  40.  
  41.             #region MyRegion
  42.             ////随机删除150个元素
  43.             //for (int i = 0; i < 5000; i++)
  44.             //{
  45.             //    var rand = new Random((int)DateTime.Now.Ticks).Next(0, list.Count);
  46.  
  47.             //    System.Threading.Thread.Sleep(2);
  48.  
  49.             //    Console.WriteLine("\n**************************************\n当前要删除元素：{0}", list[rand]);
  50.  
  51.             //    blockList.Remove(list[rand]);
  52.  
  53.             //    Console.WriteLine("\n\n");
  54.  
  55.             //    if (blockList.GetCount() == 0)
  56.             //    {
  57.             //        Console.Read();
  58.             //        return;
  59.             //    }
  60.             //} 
  61.             #endregion
  62.  
  63.             Console.Read();
  64.         }
  65.     }
  66.  
  67.     public class BlockLinkList
  68.     {
  69.         BlockLinkNode blockLinkNode = null;
  70.  
  71.         public BlockLinkList()
  72.         {
  73.             //初始化节点
  74.             blockLinkNode = new BlockLinkNode()
  75.             {
  76.                 list = new List<int>(),
  77.                 next = null,
  78.                 prev = null
  79.             };
  80.         }
  81.  
  82.         /// <summary>
  83.         /// 定义块状链表的总长度
  84.         /// </summary>
  85.         private int total;
  86.  
  87.         public class BlockLinkNode
  88.         {
  89.             /// <summary>
  90.             /// 指向前一个节点的指针
  91.             /// </summary>
  92.             public BlockLinkNode prev;
  93.  
  94.             /// <summary>
  95.             /// 指向后一个节点的指针
  96.             /// </summary>
  97.             public BlockLinkNode next;
  98.  
  99.             /// <summary>
  100.             /// 链表中的数组
  101.             /// </summary>
  102.             public List<int> list;
  103.         }
  104.  
  105.         /// <summary>
  106.         /// 判断指定元素是否存在
  107.         /// </summary>
  108.         /// <param name="num"></param>
  109.         /// <returns></returns>
  110.         public bool IsExist(int num)
  111.         {
  112.             var isExist = false;
  113.  
  114.             var temp = blockLinkNode;
  115.  
  116.             while (temp != null)
  117.             {
  118.                 //判断是否在该区间内
  119.                 if (temp.list.Count > 0 && num >= temp.list[0] && num <= temp.list[temp.list.Count - 1])
  120.                 {
  121.                     isExist = temp.list.IndexOf(num) > 0 ? true : false;
  122.  
  123.                     return isExist;
  124.                 }
  125.  
  126.                 temp = temp.next;
  127.             }
  128.  
  129.             return isExist;
  130.         }
  131.  
  132.         public string Get(int num)
  133.         {
  134.             var blockIndex = 0;
  135.             var arrIndex = 0;
  136.  
  137.             var temp = blockLinkNode;
  138.  
  139.             while (temp != null)
  140.             {
  141.                 //判断是否在该区间内
  142.                 if (temp.list.Count > 0 && num >= temp.list[0] && num <= temp.list[temp.list.Count - 1])
  143.                 {
  144.                     arrIndex = temp.list.IndexOf(num);
  145.  
  146.                     return string.Format("当前数据在第{0}块中的{1}个位置", blockIndex, arrIndex);
  147.                 }
  148.  
  149.                 blockIndex = blockIndex + 1;
  150.                 temp = temp.next;
  151.             }
  152.  
  153.             return string.Empty;
  154.         }
  155.  
  156.         /// <summary>
  157.         /// 将元素加入到块状链表中
  158.         /// </summary>
  159.         /// <param name="num"></param>
  160.         public BlockLinkNode Add(int num)
  161.         {
  162.             return Add(blockLinkNode, num);
  163.         }
  164.  
  165.         /// <summary>
  166.         /// 添加元素只会进行块状链表的分裂
  167.         /// </summary>
  168.         /// <param name="node"></param>
  169.         /// <param name="num"></param>
  170.         /// <returns></returns>
  171.         private BlockLinkNode Add(BlockLinkNode node, int num)
  172.         {
  173.             if (node == null)
  174.             {
  175.                 return node;
  176.             }
  177.             else
  178.             {
  179.                 /*
  180.                  *  第一步：找到指定的节点
  181.                  */
  182.                 if (node.list.Count == 0)
  183.                 {
  184.                     node.list.Add(num);
  185.  
  186.                     total = total + 1;
  187.  
  188.                     return node;
  189.                 }
  190.  
  191.                 //下一步：再比较是否应该分裂块
  192.                 var blockLen = (int)Math.Ceiling(Math.Sqrt(total)) * 2;
  193.  
  194.                 //如果该节点的数组的最后位置值大于插入值，则此时我们找到了链表的插入节点，
  195.                 //或者该节点的next=null，说明是最后一个节点，此时也要判断是否要裂开
  196.                 if (node.list[node.list.Count - 1] > num || node.next == null)
  197.                 {
  198.                     node.list.Add(num);
  199.  
  200.                     //最后进行排序下，当然可以用插入排序解决，O(N)搞定
  201.                     node.list = node.list.OrderBy(i => i).ToList();
  202.  
  203.                     //如果该数组里面的个数大于2*blockLen，说明已经过大了，此时需要对半分裂
  204.                     if (node.list.Count > blockLen)
  205.                     {
  206.                         //先将数据插入到数据库
  207.                         var mid = node.list.Count / 2;
  208.  
  209.                         //分裂处的前段部分
  210.                         var firstList = new List<int>();
  211.  
  212.                         //分裂后的后段部分
  213.                         var lastList = new List<int>();
  214.  
  215.                         //可以在插入点处分裂，也可以对半分裂(这里对半分裂)
  216.                         firstList.AddRange(node.list.Take(mid));
  217.                         lastList.AddRange(node.list.Skip(mid).Take(node.list.Count - mid));
  218.  
  219.  
  220.                         //开始分裂节点，需要新开辟一个新节点
  221.                         var nNode = new BlockLinkNode();
  222.  
  223.                         nNode.list = lastList;
  224.                         nNode.next = node.next;
  225.                         nNode.prev = node;
  226.  
  227.                         //改变当前节点的next和list
  228.                         node.list = firstList;
  229.                         node.next = nNode;
  230.                     }
  231.  
  232.                     total = total + 1;
  233.  
  234.                     return node;
  235.                 }
  236.  
  237.                 return Add(node.next, num);
  238.             }
  239.         }
  240.  
  241.         /// <summary>
  242.         /// 从块状链表中移除元素
  243.         /// </summary>
  244.         /// <param name="num"></param>
  245.         /// <returns></returns>
  246.         public BlockLinkNode Remove(int num)
  247.         {
  248.             return Remove(blockLinkNode, num);
  249.         }
  250.  
  251.         /// <summary>
  252.         /// 从块状链表中移除元素,涉及到合并
  253.         /// </summary>
  254.         /// <param name="node"></param>
  255.         /// <param name="num"></param>
  256.         /// <returns></returns>
  257.         private BlockLinkNode Remove(BlockLinkNode node, int num)
  258.         {
  259.             if (node == null)
  260.             {
  261.                 return node;
  262.             }
  263.             else
  264.             {
  265.                 //第一步： 判断删除元素是否在该节点内
  266.                 if (node.list.Count > 0 && num >= node.list[0] && num <= node.list[node.list.Count - 1])
  267.                 {
  268.                     //定义改节点的目的在于防止remove方法假删除的情况发生
  269.                     var prevcount = node.list.Count;
  270.  
  271.                     node.list.Remove(num);
  272.  
  273.                     total = total - (prevcount - node.list.Count);
  274.  
  275.                     //下一步： 判断是否需要合并节点
  276.                     var blockLen = (int)Math.Ceiling(Math.Sqrt(total) / 2);
  277.  
  278.                     //如果当前节点的数组个数小于 blocklen的话，那么此时改节点需要和后一个节点进行合并
  279.                     //如果该节点时尾节点，则放弃合并
  280.                     if (node.list.Count < blockLen)
  281.                     {
  282.                         if (node.next != null)
  283.                         {
  284.                             node.list.AddRange(node.next.list);
  285.  
  286.                             //如果下一个节点的下一个节点不为null，则将下下个节点的prev赋值
  287.                             if (node.next.next != null)
  288.                                 node.next.next.prev = node;
  289.  
  290.                             node.next = node.next.next;
  291.                         }
  292.                         else
  293.                         {
  294.                             //最后一个节点不需要合并，如果list=0，则直接剔除该节点
  295.                             if (node.list.Count == 0)
  296.                             {
  297.                                 if (node.prev != null)
  298.                                     node.prev.next = null;
  299.  
  300.                                 node = null;
  301.                             }
  302.                         }
  303.                     }
  304.  
  305.                     return node;
  306.                 }
  307.  
  308.                 return Remove(node.next, num);
  309.             }
  310.         }
  311.  
  312.         /// <summary>
  313.         /// 获取块状链表中的所有个数
  314.         /// </summary>
  315.         /// <returns></returns>
  316.         public int GetCount()
  317.         {
  318.             int count = 0;
  319.  
  320.             var temp = blockLinkNode;
  321.  
  322.             Console.Write("各节点数据个数为：");
  323.  
  324.             while (temp != null)
  325.             {
  326.                 count += temp.list.Count;
  327.  
  328.                 Console.Write(temp.list.Count + ",");
  329.  
  330.                 temp = temp.next;
  331.             }
  332.  
  333.             Console.WriteLine("总共有:{0} 个元素", count);
  334.  
  335.             return count;
  336.         }
  337.     }
  338. }