首页 > 代码库 > 经典算法题每日演练——第二十五题 块状链表
经典算法题每日演练——第二十五题 块状链表
原文:经典算法题每日演练——第二十五题 块状链表
View Code
在数据结构的世界里，我们会认识各种各样的数据结构，每一种数据结构都能解决相应领域的问题，每一种数据结构都像
是降龙十八掌中的某一掌，掌掌毙命。。。 当然每个数据结构，有他的优点，必然就有它的缺点，那么如何创造一种数据结构
来将某两种数据结构进行扬长避短，那就非常完美了。这样的数据结构也有很多，比如：双端队列，还有就是今天讲的 块状链表，
我们都知道 数组 具有 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。。。
下面我们看看怎么具体使用：
一：结构定义
这个比较简单，我们在每个链表节点中定义一个 头指针，尾指针 和 一个数组节点。
1 public class BlockLinkNode 2 { 3 /// <summary> 4 /// 指向前一个节点的指针 5 /// </summary> 6 public BlockLinkNode prev; 7 8 /// <summary> 9 /// 指向后一个节点的指针10 /// </summary>11 public BlockLinkNode next;12 13 /// <summary>14 /// 链表中的数组15 /// </summary>16 public List<int> list;17 }
二： 插入
刚才也说了，每个链表节点的数据是一个数组块，那么问题来了，我们是根据什么将数组切开呢？总不能将所有的数据都放在一个
链表的节点吧，那就退化成数组了，在理想的情况下，为了保持√N的数组个数，所以我们定了一个界限2√N，当链表中的节点数组
的个数超过2√N的时候，当下次插入数据的时候，我们有两种做法：
① 在元素的数组插入处，将当前数组切开，插入元素处之前为一个链表节点，插入元素后为一个链表节点。
② 将元素插入数组后，将数组从中间位置切开。
1 /// <summary> 2 /// 添加元素只会进行块状链表的分裂 3 /// </summary> 4 /// <param name="node"></param> 5 /// <param name="num"></param> 6 /// <returns></returns> 7 private BlockLinkNode Add(BlockLinkNode node, int num) 8 { 9 if (node == null)10 {11 return node;12 }13 else14 {15 /*16 * 第一步：找到指定的节点17 */18 if (node.list.Count == 0)19 {20 node.list.Add(num);21 22 total = total + 1;23 24 return node;25 }26 27 //下一步：再比较是否应该分裂块28 var blockLen = (int)Math.Ceiling(Math.Sqrt(total)) * 2;29 30 //如果该节点的数组的最后位置值大于插入值，则此时我们找到了链表的插入节点，31 //或者该节点的next=null，说明是最后一个节点，此时也要判断是否要裂开32 if (node.list[node.list.Count - 1] > num || node.next == null)33 {34 node.list.Add(num);35 36 //最后进行排序下，当然可以用插入排序解决，O(N)搞定37 node.list = node.list.OrderBy(i => i).ToList();38 39 //如果该数组里面的个数大于2*blockLen，说明已经过大了，此时需要对半分裂40 if (node.list.Count > blockLen)41 {42 //先将数据插入到数据库43 var mid = node.list.Count / 2;44 45 //分裂处的前段部分46 var firstList = new List<int>();47 48 //分裂后的后段部分49 var lastList = new List<int>();50 51 //可以在插入点处分裂，也可以对半分裂(这里对半分裂)52 firstList.AddRange(node.list.Take(mid));53 lastList.AddRange(node.list.Skip(mid).Take(node.list.Count - mid));54 55 56 //开始分裂节点，需要新开辟一个新节点57 var nNode = new BlockLinkNode();58 59 nNode.list = lastList;60 nNode.next = node.next;61 nNode.prev = node;62 63 //改变当前节点的next和list64 node.list = firstList;65 node.next = nNode;66 }67 68 total = total + 1;69 70 return node;71 }72 73 return Add(node.next, num);74 }75 }
二：删除
跟插入道理一样，既然有裂开，就有合并，同样也定义了一个界限值√N /2 ，当链表数组节点的数组个数小于这个界限值
的时候，需要将此节点和后面的链表节点进行合并。
1 /// <summary> 2 /// 从块状链表中移除元素,涉及到合并 3 /// </summary> 4 /// <param name="node"></param> 5 /// <param name="num"></param> 6 /// <returns></returns> 7 private BlockLinkNode Remove(BlockLinkNode node, int num) 8 { 9 if (node == null)10 {11 return node;12 }13 else14 {15 //第一步： 判断删除元素是否在该节点内16 if (node.list.Count > 0 && num >= node.list[0] && num <= node.list[node.list.Count - 1])17 {18 //定义改节点的目的在于防止remove方法假删除的情况发生19 var prevcount = node.list.Count;20 21 node.list.Remove(num);22 23 total = total - (prevcount - node.list.Count);24 25 //下一步： 判断是否需要合并节点26 var blockLen = (int)Math.Ceiling(Math.Sqrt(total) / 2);27 28 //如果当前节点的数组个数小于 blocklen的话，那么此时改节点需要和后一个节点进行合并29 //如果该节点时尾节点，则放弃合并30 if (node.list.Count < blockLen)31 {32 if (node.next != null)33 {34 node.list.AddRange(node.next.list);35 36 //如果下一个节点的下一个节点不为null，则将下下个节点的prev赋值37 if (node.next.next != null)38 node.next.next.prev = node;39 40 node.next = node.next.next;41 }42 else43 {44 //最后一个节点不需要合并，如果list=0，则直接剔除该节点45 if (node.list.Count == 0)46 {47 if (node.prev != null)48 node.prev.next = null;49 50 node = null;51 }52 }53 }54 55 return node;56 }57 58 return Remove(node.next, num);59 }60 }
四： 查询
在理想的情况下，我们都控制在√N，然后就可以用√N的时间找到区块，lg√N的时间找到区块中的指定值，当然也有人在查询
的时候做 链表的合并和分裂，这个就有点像伸展树一样，在查询的时候动态调整，拼的是均摊情况下的复杂度。这里顺便提醒你一
下，其实你也可以这么做。。。
1 public string Get(int num) 2 { 3 var blockIndex = 0; 4 var arrIndex = 0; 5 6 var temp = blockLinkNode; 7 8 while (temp != null) 9 {10 //判断是否在该区间内11 if (temp.list.Count > 0 && num >= temp.list[0] && num <= temp.list[temp.list.Count - 1])12 {13 arrIndex = temp.list.IndexOf(num);14 15 return string.Format("当前数据在第{0}块中的{1}个位置", blockIndex, arrIndex);16 }17 18 blockIndex = blockIndex + 1;19 temp = temp.next;20 }21 22 return string.Empty;23 }
好了，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 else178 {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和list228 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 else264 {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 else293 {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 }
经典算法题每日演练——第二十五题 块状链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。