C#實現(xiàn)塊狀鏈表的項目實踐

更新時間：2023年11月27日 15:00:42 作者：神仙別鬧

這篇文章主要介紹了C#實現(xiàn)塊狀鏈表的項目實踐,通過定義塊和鏈表類,利用塊內(nèi)元素引用實現(xiàn)塊與塊之間的鏈接關(guān)系,從而實現(xiàn)對塊狀鏈表的遍歷、插入和刪除等操作,感興趣的可以了解一下

在數(shù)據(jù)結(jié)構(gòu)的世界里，我們會認(rèn)識各種各樣的數(shù)據(jù)結(jié)構(gòu)，每一種數(shù)據(jù)結(jié)構(gòu)都能解決相應(yīng)領(lǐng)域的問題，當(dāng)然每個數(shù)據(jù)結(jié)構(gòu)，有他的優(yōu)點，必然就有它的缺點，那么如何創(chuàng)造一種數(shù)據(jù)結(jié)構(gòu)來將某兩種數(shù)據(jù)結(jié)構(gòu)進(jìn)行揚長避短，那就非常完美了。這樣的數(shù)據(jù)結(jié)構(gòu)也有很多，比如：雙端隊列，還有就是今天講的塊狀鏈表。

我們都知道

數(shù)組具有 O(1)的查詢時間，O(N)的刪除，O(N)的插入。。。
鏈表具有 O(N)的查詢時間，O(1)的刪除，O(1)的插入。。。

那么現(xiàn)在我們就有想法了，何不讓“鏈表”和“數(shù)組”結(jié)合起來，來一起均攤 CURD 的時間，做法將數(shù)組進(jìn)行分塊，然后用指針相連接，比如我有 N=100 個元素，那么最理想情況下，我就可以將數(shù)組分成 x=10 段，每段 b=10 個元素（排好序），那么我可以用 √N 的時間找到段，因為段中的元素是已經(jīng)排好序的，所以可以用 lg√N 的時間找到段中的元素，那么最理想的復(fù)雜度為 √N+lg√N≈√N。。。

下面我們看看怎么具體使用：

一、結(jié)構(gòu)定義

這個比較簡單，我們在每個鏈表節(jié)點中定義一個頭指針，尾指針和一個數(shù)組節(jié)點。

 public class BlockLinkNode
 {
     /// <summary>
     /// 指向前一個節(jié)點的指針
     /// </summary>
     public BlockLinkNode prev;

     /// <summary>
     /// 指向后一個節(jié)點的指針
     /// </summary>
     public BlockLinkNode next;

     /// <summary>
     /// 鏈表中的數(shù)組
     /// </summary>
     public List<int> list;
 }

二、插入

剛才也說了，每個鏈表節(jié)點的數(shù)據(jù)是一個數(shù)組塊，那么問題來了，我們是根據(jù)什么將數(shù)組切開呢？總不能將所有的數(shù)據(jù)都放在一個鏈表的節(jié)點吧，那就退化成數(shù)組了，在理想的情況下，為了保持 √N 的數(shù)組個數(shù)，所以我們定了一個界限 2√N，當(dāng)鏈表中的節(jié)點數(shù)組的個數(shù)超過 2√N 的時候，當(dāng)下次插入數(shù)據(jù)的時候，我們有兩種做法：

在元素的數(shù)組插入處，將當(dāng)前數(shù)組切開，插入元素處之前為一個鏈表節(jié)點，插入元素后為一個鏈表節(jié)點。將元素插入數(shù)組后，將數(shù)組從中間位置切開。

 /// <summary>
 /// 添加元素只會進(jìn)行塊狀鏈表的分裂
 /// </summary>
 /// <param name="node"></param>
 /// <param name="num"></param>
 /// <returns></returns>
 private BlockLinkNode Add(BlockLinkNode node, int num)
 {
     if (node == null)
     {
         return node;
     }
     else
     {
         /*
          *  第一步：找到指定的節(jié)點
          */
         if (node.list.Count == 0)
         {
             node.list.Add(num);

             total = total + 1;

             return node;
         }

         //下一步：再比較是否應(yīng)該分裂塊
         var blockLen = (int)Math.Ceiling(Math.Sqrt(total)) * 2;

         //如果該節(jié)點的數(shù)組的最后位置值大于插入值，則此時我們找到了鏈表的插入節(jié)點，
         //或者該節(jié)點的next=null，說明是最后一個節(jié)點，此時也要判斷是否要裂開
         if (node.list[node.list.Count - 1] > num || node.next == null)
         {
             node.list.Add(num);

             //最后進(jìn)行排序下，當(dāng)然可以用插入排序解決，O(N)搞定
             node.list = node.list.OrderBy(i => i).ToList();

             //如果該數(shù)組里面的個數(shù)大于2*blockLen，說明已經(jīng)過大了，此時需要對半分裂
             if (node.list.Count > blockLen)
             {
                 //先將數(shù)據(jù)插入到數(shù)據(jù)庫
                 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));


                 //開始分裂節(jié)點，需要新開辟一個新節(jié)點
                 var nNode = new BlockLinkNode();

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

                 //改變當(dāng)前節(jié)點的next和list
                 node.list = firstList;
                 node.next = nNode;
             }

             total = total + 1;

             return node;
         }

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

二、刪除

跟插入道理一樣，既然有裂開，就有合并，同樣也定義了一個界限值 √N /2 ，當(dāng)鏈表數(shù)組節(jié)點的數(shù)組個數(shù)小于這個界限值的時候，需要將此節(jié)點和后面的鏈表節(jié)點進(jìn)行合并。

 /// <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
     {
         //第一步： 判斷刪除元素是否在該節(jié)點內(nèi)
         if (node.list.Count > 0 && num >= node.list[0] && num <= node.list[node.list.Count - 1])
         {
             //定義改節(jié)點的目的在于防止remove方法假刪除的情況發(fā)生
             var prevcount = node.list.Count;

             node.list.Remove(num);

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

             //下一步： 判斷是否需要合并節(jié)點
             var blockLen = (int)Math.Ceiling(Math.Sqrt(total) / 2);

             //如果當(dāng)前節(jié)點的數(shù)組個數(shù)小于 blocklen的話，那么此時改節(jié)點需要和后一個節(jié)點進(jìn)行合并
             //如果該節(jié)點時尾節(jié)點，則放棄合并
             if (node.list.Count < blockLen)
             {
                 if (node.next != null)
                 {
                     node.list.AddRange(node.next.list);

                     //如果下一個節(jié)點的下一個節(jié)點不為null，則將下下個節(jié)點的prev賦值
                     if (node.next.next != null)
                         node.next.next.prev = node;

                     node.next = node.next.next;
                 }
                 else
                 {
                     //最后一個節(jié)點不需要合并，如果list=0，則直接剔除該節(jié)點
                     if (node.list.Count == 0)
                     {
                         if (node.prev != null)
                             node.prev.next = null;

                         node = null;
                     }
                 }
             }

             return node;
         }

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

三、查詢

在理想的情況下，我們都控制在 √N，然后就可以用 √N 的時間找到區(qū)塊，lg√N 的時間找到區(qū)塊中的指定值，當(dāng)然也有人在查詢的時候做鏈表的合并和分裂，這個就有點像伸展樹一樣，在查詢的時候動態(tài)調(diào)整，拼的是均攤情況下的復(fù)雜度。

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

     var temp = blockLinkNode;

     while (temp != null)
     {
         //判斷是否在該區(qū)間內(nèi)
         if (temp.list.Count > 0 && num >= temp.list[0] && num <= temp.list[temp.list.Count - 1])
         {
             arrIndex = temp.list.IndexOf(num);

             return string.Format("當(dāng)前數(shù)據(jù)在第{0}塊中的{1}個位置", blockIndex, arrIndex);
         }

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

     return string.Empty;
 }

好了，CURD 都分析好了，到這里大家應(yīng)該對塊狀鏈表有個大概的認(rèn)識了吧，這個代碼是我下午抽閑寫的，沒有仔細(xì)測試，最后是總的代碼：

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
             隨機(jī)刪除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當(dāng)前要刪除元素：{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()
         {
             //初始化節(jié)點
             blockLinkNode = new BlockLinkNode()
             {
                 list = new List<int>(),
                 next = null,
                 prev = null
             };
         }
 
         /// <summary>
         /// 定義塊狀鏈表的總長度
         /// </summary>
         private int total;
 
         public class BlockLinkNode
         {
             /// <summary>
             /// 指向前一個節(jié)點的指針
             /// </summary>
             public BlockLinkNode prev;
 
             /// <summary>
             /// 指向后一個節(jié)點的指針
             /// </summary>
             public BlockLinkNode next;
 
             /// <summary>
             /// 鏈表中的數(shù)組
             /// </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)
             {
                 //判斷是否在該區(qū)間內(nèi)
                 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)
             {
                 //判斷是否在該區(qū)間內(nèi)
                 if (temp.list.Count > 0 && num >= temp.list[0] && num <= temp.list[temp.list.Count - 1])
                 {
                     arrIndex = temp.list.IndexOf(num);
 
                     return string.Format("當(dāng)前數(shù)據(jù)在第{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>
         /// 添加元素只會進(jìn)行塊狀鏈表的分裂
         /// </summary>
         /// <param name="node"></param>
         /// <param name="num"></param>
         /// <returns></returns>
         private BlockLinkNode Add(BlockLinkNode node, int num)
         {
             if (node == null)
             {
                 return node;
             }
             else
             {
                 /*
                  *  第一步：找到指定的節(jié)點
                  */
                 if (node.list.Count == 0)
                 {
                     node.list.Add(num);
 
                     total = total + 1;
 
                     return node;
                 }
 
                 //下一步：再比較是否應(yīng)該分裂塊
                 var blockLen = (int)Math.Ceiling(Math.Sqrt(total)) * 2;
 
                 //如果該節(jié)點的數(shù)組的最后位置值大于插入值，則此時我們找到了鏈表的插入節(jié)點，
                 //或者該節(jié)點的next=null，說明是最后一個節(jié)點，此時也要判斷是否要裂開
                 if (node.list[node.list.Count - 1] > num || node.next == null)
                 {
                     node.list.Add(num);
 
                     //最后進(jìn)行排序下，當(dāng)然可以用插入排序解決，O(N)搞定
                     node.list = node.list.OrderBy(i => i).ToList();
 
                     //如果該數(shù)組里面的個數(shù)大于2*blockLen，說明已經(jīng)過大了，此時需要對半分裂
                     if (node.list.Count > blockLen)
                     {
                         //先將數(shù)據(jù)插入到數(shù)據(jù)庫
                         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));
 
 
                         //開始分裂節(jié)點，需要新開辟一個新節(jié)點
                         var nNode = new BlockLinkNode();
 
                         nNode.list = lastList;
                         nNode.next = node.next;
                         nNode.prev = node;
 
                         //改變當(dāng)前節(jié)點的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
             {
                 //第一步： 判斷刪除元素是否在該節(jié)點內(nèi)
                 if (node.list.Count > 0 && num >= node.list[0] && num <= node.list[node.list.Count - 1])
                 {
                     //定義改節(jié)點的目的在于防止remove方法假刪除的情況發(fā)生
                     var prevcount = node.list.Count;
 
                     node.list.Remove(num);
 
                     total = total - (prevcount - node.list.Count);
 
                     //下一步： 判斷是否需要合并節(jié)點
                     var blockLen = (int)Math.Ceiling(Math.Sqrt(total) / 2);
 
                     //如果當(dāng)前節(jié)點的數(shù)組個數(shù)小于 blocklen的話，那么此時改節(jié)點需要和后一個節(jié)點進(jìn)行合并
                     //如果該節(jié)點時尾節(jié)點，則放棄合并
                     if (node.list.Count < blockLen)
                     {
                         if (node.next != null)
                         {
                             node.list.AddRange(node.next.list);
 
                             //如果下一個節(jié)點的下一個節(jié)點不為null，則將下下個節(jié)點的prev賦值
                             if (node.next.next != null)
                                 node.next.next.prev = node;
 
                             node.next = node.next.next;
                         }
                         else
                         {
                             //最后一個節(jié)點不需要合并，如果list=0，則直接剔除該節(jié)點
                             if (node.list.Count == 0)
                             {
                                 if (node.prev != null)
                                     node.prev.next = null;
 
                                 node = null;
                             }
                         }
                     }
 
                     return node;
                 }

                 return Remove(node.next, num);
             }
         }
 
         /// <summary>
         /// 獲取塊狀鏈表中的所有個數(shù)
         /// </summary>
         /// <returns></returns>
         public int GetCount()
         {
             int count = 0;
 
             var temp = blockLinkNode;
 
             Console.Write("各節(jié)點數(shù)據(jù)個數(shù)為：");
 
             while (temp != null)
             {
                 count += temp.list.Count;
 
                 Console.Write(temp.list.Count + ",");
 
                 temp = temp.next;
             }
 
             Console.WriteLine("總共有:{0} 個元素", count);
 
             return count;
         }
     }
 }

到此這篇關(guān)于C#實現(xiàn)塊狀鏈表的項目實踐的文章就介紹到這了,更多相關(guān)C# 塊狀鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: