原文:经典算法题每日演练——第二十五题 块状链表
在数据结构的世界里，我们会认识各种各样的数据结构，每一种数据结构都能解决相应领域的问题，每一种数据结构都像
是降龙十八掌中的某一掌，掌掌毙命。。。 当然每个数据结构，有他的优点，必然就有它的缺点，那么如何创造一种数据结构
来将某两种数据结构进行扬长避短，那就非常完美了。这样的数据结构也有很多，比如：双端队列，还有就是今天讲的 块状链表，
我们都知道 数组 具有 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 else
14 {
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和list
64 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 else
14 {
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 else
43 {
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 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 }
View Code
时间： 2024-07-31 14:00:04