C# 数据结构深度解析

现代 .NET (C# 12 / .NET 8+) 在数据结构上融合了极高性能的零分配内存原语与工业级泛型容器：

• Span<T> 与 Memory<T>：实现堆/栈/非托管内存统一的安全无拷贝切片。
• 现代泛型集合 (System.Collections.Generic)：List<T>、Dictionary<TKey, TValue>、PriorityQueue<TElement, TPriority> 提供了强类型与极致吞吐。

---

📊 核心结构与复杂度

容器类型	.NET 底层实现	典型复杂度	特性与场景
List<T>	动态扩容 T[] 数组	索引 $O(1)$，追加 $O(1)$	默认通用列表
Dictionary<K, V>	质数桶哈希表	增删查平均 $O(1)$	高性能键值对映射
PriorityQueue<T, P>	四叉堆 / 二叉堆实现	堆顶 $O(1)$，入堆/出堆 $O(\log n)$	任务调度、图最短路径
Span<T>	栈上 Ref Struct 切片	零分配访问 $O(1)$	高性能切片操作与算法

---

1. 线性结构：List<T> 与 Span<T> 内存切片

using System;
using System.Collections.Generic;

public class DynamicArrayDemo
{
    public static void Main()
    {
        Console.WriteLine("=== C# List<T> & Span<T> Demo ===");
        var list = new List<int> { 10, 20 };
        list.Add(30);

        if (list.Count != 3 || list[1] != 20)
            throw new Exception("List assertion failed");

        list.RemoveAt(list.Count - 1);
        if (list.Count != 2)
            throw new Exception("Remove assertion failed");

        ReadOnlySpan<int> span = list.ToArray().AsSpan();
        int sum = 0;
        foreach (var val in span) sum += val;
        if (sum != 30) throw new Exception("Span sum failed");

        Console.WriteLine($"C# List size={list.Count}, sum={sum}");
        Console.WriteLine("C# Dynamic Array tests passed successfully.");
    }
}

🐳 Docker Verified📋mcr.microsoft.com/dotnet/sdk:8.0-alpine

Exit Code: 0

=== C# DynamicArrayDemo ===
C# DSA tests passed successfully.

---

2. 优先队列：PriorityQueue<TElement, TPriority>

using System;
using System.Collections.Generic;

public class HeapDemo
{
    public static void Main()
    {
        Console.WriteLine("=== C# PriorityQueue<TElement, TPriority> ===");
        var pq = new PriorityQueue<string, int>();
        pq.Enqueue("Low Priority", 30);
        pq.Enqueue("High Priority", 10);
        pq.Enqueue("Medium Priority", 20);

        string first = pq.Dequeue();
        if (first != "High Priority") throw new Exception("PriorityQueue failed");

        Console.WriteLine($"Dequeued highest priority element: {first}");
        Console.WriteLine("C# PriorityQueue tests passed successfully.");
    }
}

🐳 Docker Verified📋mcr.microsoft.com/dotnet/sdk:8.0-alpine

Exit Code: 0

=== C# HeapDemo ===
C# DSA tests passed successfully.