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)進行揚長避短，那就非常完美了。這樣的數(shù)據(jù)結(jié)構(gòu)也有很多，比如：雙端隊列，還有就是今天講的塊狀鏈表。
我們都知道
- 數(shù)組 具有 O(1)的查詢時間，O(N)的刪除，O(N)的插入。。。
- 鏈表 具有 O(N)的查詢時間，O(1)的刪除，O(1)的插入。。。
那么現(xiàn)在我們就有想法了，何不讓“鏈表”和“數(shù)組”結(jié)合起來，來一起均攤 CURD 的時間，做法將數(shù)組進行分塊，然后用指針相連接，比如我有 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>
/// 添加元素只會進行塊狀鏈表的分裂
/// </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);
//最后進行排序下，當(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é)點進行合并。
/// <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é)點進行合并
//如果該節(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
隨機刪除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>
/// 添加元素只會進行塊狀鏈表的分裂
/// </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);
//最后進行排序下，當(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é)點進行合并
//如果該節(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)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- C#數(shù)據(jù)結(jié)構(gòu)之單鏈表(LinkList)實例詳解
- C#實現(xiàn)的簡單鏈表類實例
- C#雙向鏈表LinkedList排序?qū)崿F(xiàn)方法
- C#定義并實現(xiàn)單鏈表實例解析
- C#數(shù)據(jù)結(jié)構(gòu)之雙向鏈表(DbLinkList)實例詳解
- C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘三 鏈表
- C#數(shù)據(jù)結(jié)構(gòu)之循環(huán)鏈表的實例代碼
- C#集合之鏈表的用法
- C#通過鏈表實現(xiàn)隊列的方法
- C#集合本質(zhì)之鏈表的用法詳解
- C#模擬鏈表數(shù)據(jù)結(jié)構(gòu)的實例解析
- C#實現(xiàn)基于鏈表的內(nèi)存記事本實例
相關(guān)文章
c# StringBuilder.Replace 方法 (Char, Char, Int32, Int32)
c# StringBuilder.Replace 方法 (Char, Char, Int32, Int32)...2007-08-08
這篇文章主要介紹了c#自帶緩存使用方法,包括獲取數(shù)據(jù)緩存、設(shè)置數(shù)據(jù)緩存、移除指定數(shù)據(jù)緩存等方法，需要的朋友可以參考下2014-02-02
C#?wpf使用DockPanel實現(xiàn)制作截屏框
做桌面客戶端的時候有時需要實現(xiàn)截屏功能,能夠在界面上框選截屏,本文就來為大家介紹一下wpf如何使用DockPanel制作截屏框吧,感興趣的可以了解下2023-09-09
這篇文章主要介紹了C#打開和關(guān)閉可執(zhí)行文件，以QQ應(yīng)用程序為例，需要的朋友可以參考下2015-12-12
進程通信一般情況下比較少用,但是也有一些使用場景,有些做視頻傳輸?shù)乃坪鯐枚噙M程來實現(xiàn),還有在子進程中調(diào)用特定的庫來避免內(nèi)存泄漏,筆者最近也遇到了需要使用多進程的場景,本文介紹了C#基于共享內(nèi)存實現(xiàn)跨進程隊列,需要的朋友可以參考下2024-07-07
C#中日期和時間操作主要通過System.DateTime類實現(xiàn),提供了創(chuàng)建、格式化、比較和計算等功能,下面就來具體介紹一下,感興趣的可以了解一下2025-03-03
c# richtextbox更新大量數(shù)據(jù)不卡死的實現(xiàn)方式
這篇文章主要介紹了c# richtextbox更新大量數(shù)據(jù)不卡死的實現(xiàn)方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-04-04
在本篇文章里小編給大家整理的是關(guān)于C#鎖住文件的操作步驟以及相關(guān)知識點，需要的朋友們參考下。2019-08-08
C# wpf使用ffmpeg命令行實現(xiàn)錄屏的示例代碼
本文主要介紹了C# wpf使用ffmpeg命令行實現(xiàn)錄屏的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08
這篇文章介紹了C#文件非占用讀取與幫助類FileHelper，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-04-04