.NET 2.0 中的泛型数据结构和算法回归基础

Riaan Hanekom

4.96/5 (91投票s)

2006 年 11 月 11 日

Ms-PL

15分钟阅读

289281

2623

在 .NET 2.0 中实现泛型数据结构和算法。

引言

自 .NET 发布以来，我一直渴望编写自己的数据结构和算法集合。这是尝试为 .NET 2.0 及更高版本提供一个可重用的泛型数据结构和算法集合。本文不会提供这些集合和算法内部工作原理的所有细节和完整描述，而是提供网上资源的链接（没有必要去和维基百科较劲），并介绍此特定实现的要点。

背景

.NET 框架确实已经发展成为一个非常丰富的框架。它提供了许多经过深思熟虑的接口和类，但省略了计算机科学领域中许多重要的数据结构和算法。该库旨在提供这些缺失的功能并扩展 .NET 框架。

概述

目前已实现以下数据结构和算法

新的数据结构	扩展数据结构	排序算法	图算法
`Association<TKey, TValue>`	`VisitableHashTable<TKey, TValue>`	冒泡排序	Dijkstra 的单源最短路径算法
`Bag<T>`	`VisitableLinkedList<T>`	桶排序	Prim 的最小生成树算法
`BinaryTree<T>`	`VisitableList<T>`	鸡尾酒排序
`BinarySearchTree<TKey, TValue>`	`VisitableQueue<T>`	梳排序	数学算法
`Deque<T>`	`VisitableStack<T>`	侏儒排序	斐波那契数生成。
`GeneralTree<T>`		堆排序	欧几里得算法
`Graph<T>`		插入排序
`Heap<T>`		归并排序
`矩阵`		奇偶排序
`PascalSet`		快速排序
`PriorityQueue<T>`		选择排序
`SkipList<TKey, TValue>`		摇摆排序
`SortedList<T>`		希尔排序
`SortedList<T>`		希尔排序
`RedBlackTree<T>`
`ReadOnlyPropertyCollection <T, TProperty>`
`ObjectMatrix<T>`
`HashList<TKey, TValue>`

使用代码

提供的数据结构

IVisibleCollection 接口

public interface IVisitable<T>
{
      // Methods
      void Accept(IVisitor<T> visitor);
}

public interface IVisitableCollection<T> : 
       ICollection<T>, IEnumerable<T>, 
       IEnumerable, IComparable, IVisitable<T>
{
      // Properties
      bool IsEmpty { get; }
      bool IsFixedSize { get; }
      bool IsFull { get; }
}

访问者模式可能是计算机科学中最常用（许多人认为被高估）的模式之一。IVisibleCollection<T> 接口为任何集合提供了一个接受访问者的接口，从而将对对象执行的操作与特定数据结构的实现分开。有关访问者的更多信息，请参阅IVisitor<T> 接口。

当调用 Accept 方法时，集合必须遍历其中包含的所有对象，并在每个对象上调用访问者的 Visit 方法。IsEmpty 和 IsFull 返回一个布尔值，分别指示当前实例是否为空或已满（不出所料）。IsFull 方法仅适用于固定大小的集合，并指示集合在添加项目时不会动态增长。

另一个名为 IVisibleDictionary<T> 的接口用于表示基于字典的集合，也实现了 IVisible<T> 接口。

关联

public class Association<TKey, TValue>
{
      // Methods
      public Association(TKey key, TValue value);
      public KeyValuePair<TKey, TValue> ToKeyValuePair();

      // Properties
      public TKey Key { get; set; }
      public TValue Value { get; set; }
}

一个类，复制了标准 KeyValuePair<TKey, TValue> 的功能，但增加了 Key 和 Value 属性的 setter。Association 类主要用于 SortedList 数据结构，在该结构中，需要保持优先级与项目值之间的键值关系。

Bag

public class Bag<T> : IVisitableCollection<T>, IBag<T>
{
      // Methods      
      public void Accept(IVisitor<KeyValuePair<T, int>> visitor);      
      public void Add(T item, int amount);      
      public Bag<T> Difference(Bag<T> bag);
      public IEnumerator<KeyValuePair<T, int>> GetCountEnumerator();
      public IEnumerator<T> GetEnumerator();
      public Bag<T> Intersection(Bag<T> bag);
      public bool IsEqual(Bag<T> bag);
      public static Bag<T> operator +(Bag<T> b1, Bag<T> b2);
      public static Bag<T> operator *(Bag<T> b1, Bag<T> b2);
      public static Bag<T> operator -(Bag<T> b1, Bag<T> b2);      
      public bool Remove(T item, int max);            
      public Bag<T> Union(Bag<T> bag);
      // ...


      // Properties      
      public int this[T item] { get; }
      // ....     
}

Bag 是一种包含任意数量元素的数据结构。它与集合不同，因为它允许集合中包含多个相同的项，因此更适合“计数”项。此库中包含的 Bag 数据结构是通过使用 Dictionary<T, int> 数据结构实现的，它保留了对 Bag 中包含的项数量的引用。

Bag 类使用 Dictionary<KeyType, int> 对象实现，其中对象根据 Bag 中包含的特定项的数量进行哈希处理。标准操作已实现。

交集 - 返回一个包含两个 Bag 中都存在的项的 Bag。
并集 - 返回一个包含两个 Bag 中所有项的 Bag。
差集 - “减去”一个 Bag。此操作会从应用 Bag 中减去另一个 Bag 中包含的项数。

BinaryTree

public class BinaryTree<T> : IVisitableCollection<T>, ITree<T>
{
      // Methods
      public void Add(BinaryTree<T> subtree);
      public virtual void breadthFirstTraversal(IVisitor<T> visitor);
      public virtual void 
             DepthFirstTraversal(OrderedVisitor<T> orderedVisitor);
      public BinaryTree<T> GetChild(int index);
      public bool Remove(BinaryTree<T> child);
      public virtual void RemoveLeft();
      public virtual void RemoveRight();

      // ...

      // Properties
      public virtual T Data { get; set; }
      public int Degree { get; }
      public virtual int Height { get; }
      public virtual bool IsLeafNode { get; }
      public BinaryTree<T> this[int i] { get; }
      public virtual BinaryTree<T> Left { get; set; }
      public virtual BinaryTree<T> Right { get; set; }
      
      // ...
}

二叉树是一种特殊的树，其中每个节点最多有两个子节点。BinaryTree<T> 类最多包含指向两个子节点的指针。BreadthFirstTraversal 和 DepthFirstTraversal 方法为指定的访问者提供访问。深度优先遍历可以以三种方式进行：中序、后序或前序，其中中序仅适用于二叉树。

Height 属性通过递归计算此二叉树及其下方的层数来工作。由于 BinaryTree 的每个子节点本身都是一个 BinaryTree，因此每个子节点都有自己的高度。

[关于二叉树的更多信息]

二叉搜索树

public class BinarySearchTree<TKey, TValue> : 
       IVisitableDictionary<TKey, TValue>, 
       IDictionary<TKey, TValue>, 
       IVisitableCollection<KeyValuePair<TKey, TValue>>
{    
    // Methods
    public void Accept(IVisitor<KeyValuePair<TKey, TValue>> visitor);
    public void Add(KeyValuePair<TKey, TValue> item);
    public void Add(TKey key, TValue value);
    public int CompareTo(object obj);
    public bool Contains(KeyValuePair<TKey, TValue> item);
    public bool ContainsKey(TKey key);
    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex);
    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator();
    public IEnumerator<KeyValuePair<TKey, TValue>> GetSortedEnumerator();
    public bool Remove(KeyValuePair<TKey, TValue> item);
    public bool Remove(TKey key);
    public bool TryGetValue(TKey key, out TValue value);
    
    // ...

    // Properties
    public IComparer<TKey> Comparer { get; }
    public int Count { get; }
    public bool IsEmpty { get; }
    public bool IsFixedSize { get; }
    public bool IsFull { get; }
    public bool IsReadOnly { get; }
    public TValue this[TKey key] { get; set; }
    public ICollection<TKey> Keys { get; }
    public KeyValuePair<TKey, TValue> Max { get; }
    public KeyValuePair<TKey, TValue> Min { get; }
    public ICollection<TValue> Values { get; } 
    
    // ...
}

二叉搜索树是一种搜索数据结构，采用二叉树的形式。它的内部工作原理很简单：小于父节点的项放在左子树中，大于父节点的项放在右子树中。这允许通过消除每层更多的项来进行快速搜索。然而，它的最坏情况之一是按顺序添加项 - 在最坏情况下需要 O(n) 次比较。但是，由于其简单性，它是一种适用于输入将随机化的场合的搜索数据结构。在无法确保输入随机化的情况下，建议使用平衡搜索树（如红黑树）。

[关于二叉搜索树的更多信息]

Deque

public sealed class Deque<T> : IVisitableCollection<T>, IDeque<T>
{
      // Methods
      public T DequeueHead();
      public T DequeueTail();
      public void EnqueueHead(T obj);
      public void EnqueueTail(T obj);

      // ...      

      // Properties
      public T Head { get; }
      public T Tail { get; }

      // ...
}

Deque（或双端队列）数据结构类似于 Queue 数据结构，不同之处在于它可以从当前队列的头部或尾部进行入队或出队。Deque 实现为链表，可以轻松访问列表的前端和后端。

[关于 Deque 的更多信息]

GeneralTree

public class GeneralTree<T> : IVisitableCollection<T>, ITree<T>
{
      // Methods
      public void Add(GeneralTree<T> child);
      public void breadthFirstTraversal(Visitor<T> visitor);
      public void DepthFirstTraversal(OrderedVisitor<T> orderedVisitor);
      public GeneralTree<T> GetChild(int index);
      public bool Remove(GeneralTree<T> child);
      public void RemoveAt(int index);
      public void Sort(ISorter<GeneralTree<GeneralTree<T>>> sorter);
      public void Sort(ISorter<GeneralTree<GeneralTree<T>>> sorter, 
             IComparer<GeneralTree<T>> comparer);
      public void Sort(ISorter<GeneralTree<GeneralTree<T>>> sorter, 
                  Comparison<GeneralTree<T>> comparison);
      


      // ...

      // Properties
      public T Data { get; }
      public int Degree { get; }
      public int Height { get; }
      public virtual bool IsLeafNode { get; }
      public GeneralTree<T> this[int i] { get; }
      public GeneralTree<T>[] Ancestors { get; }
      public GeneralTree<T> Parent { get; }


      // ...
}

通用树是最通用的树数据结构。它允许给定节点有任意数量的子节点（包括零个节点，使其成为叶节点）。GeneralTree<T> 类，与 BinaryTree<T> 类一样，允许访问者进行广度优先遍历和深度优先遍历。

GeneralTree 使用一个列表来实现，用于跟踪子节点（也为 GeneralTree 类型）。Height 属性的工作方式类似于二叉树的 Height 属性 - 它递归地计算树下方的层数。

[关于树数据结构的更多信息]

图

图数据结构由三部分组成：

一个 Vertex<T> 类，代表图中的一个节点。
一个 Edge<T> 类，在两个顶点之间形成连接。
一个 Graph<T> 类，代表边和顶点的集合。

Vertex<T>

public class Vertex<T>
{
      // Methods
      public Edge<T> GetEmanatingEdgeTo(Vertex<T> toVertex);
      public Edge<T> GetIncidentEdgeWith(Vertex<T> toVertex);
      public bool HasEmanatingEdgeTo(Vertex<T> toVertex);
      public bool HasIncidentEdgeWith(Vertex<T> fromVertex);      
      // ...
    
      // Properties
      public T Data { get; set; }
      public int Degree { get; }
      public IEnumerator<Edge<T>> EmanatingEdges { get; }
      public IEnumerator<Edge<T>> IncidentEdges { get; }
      public int IncidentEdgesCount { get; }
      // ...
}

Vertex<T> 类代表图中的一个节点。它保留了一个边列表（由图添加），这些边从它发出（指向另一个顶点）以及与之相关的边。这些列表可以通过 EmanatingEdges 和 IncidentEdges 属性访问。数据项与顶点关联，以区分它与其他顶点。

Edge<T>

public class Edge<T>
{
      // Methods
      public Vertex<T> GetPartnerVertex(Vertex<T> vertex);
      // ...

      // Properties
      public Vertex<T> FromVertex { get; }
      public bool IsDirected { get; }
      public Vertex<T> ToVertex { get; }
      public double Weight { get; }
      // ...
}

Edge<T> 类表示图中的两个顶点之间的边，该边可以是定向的或无向的，具体取决于图的类型。边可以加权，即可以为边分配一个值来表示其负载或两个顶点之间的距离。GetPartnerVertex 方法（给定边中的一个顶点）返回关系中的另一个顶点。

Graph<T>

public class Graph<T> : IVisitableCollection<T>
{
      // Methods
      public void AddEdge(Edge<T> edge);
      public Edge<T> AddEdge(Vertex<T> from, Vertex<T> to);
      public Edge<T> AddEdge(Vertex<T> from, Vertex<T> to, double weight);
      public void AddVertex(Vertex<T> vertex);
      public Vertex<T> AddVertex(T item);
      public void BreadthFirstTraversal(IVisitor<Vertex<T>> visitor, 
                                        Vertex<T> startVertex);
      public bool ContainsEdge(Edge<T> edge);
      public bool ContainsEdge(Vertex<T> from, Vertex<T> to);
      public bool ContainsEdge(T fromValue, T toValue);
      public bool ContainsVertex(Vertex<T> vertex);
      public bool ContainsVertex(T item);
      public void DepthFirstTraversal(OrderedVisitor<Vertex<T>> visitor, 
                                      Vertex<T> startVertex);
      public Edge<T> GetEdge(Vertex<T> from, Vertex<T> to);
      public bool RemoveEdge(Edge<T> edge);
      public bool RemoveEdge(Vertex<T> from, Vertex<T> to);
      public bool RemoveVertex(Vertex<T> vertex);
      public bool RemoveVertex(T item);
      // ...

      // Properties
      public int EdgeCount { get; }
      public IEnumerator<Edge<T>> Edges { get; }
      public bool IsDirected { get; }
      public bool IsStronglyConnected { get; }
      public bool IsWeaklyConnected { get; }
      public int VertexCount { get; }
      public IEnumerator<Vertex<T>> Vertices { get; }
      // ...
}

Graph<T> 类是顶点和边的容器。所有添加和删除操作都由图执行。标准添加、删除和获取操作已实现。还实现了类似于树数据结构的 DepthFirstTraversal 和 BreadthFirstTraversal，只是它们需要一个起始顶点，因为图没有根。

IsStronglyConnected 和 IsWeaklyConnected 测试图中连接性。弱连接确保图中的每个顶点之间都存在无向边。换句话说，所有顶点都可以从每个其他顶点到达。请注意，对于有向图，该算法将有向边表示为无向边。测试图是否强连通需要确保每个顶点都可以从每个其他顶点到达，并且仅在有向图上可用。

[关于图的更多信息]

HashList

public sealed class HashList<TKey, TValue> : 
              VisitableHashtable<TKey, IList<TValue>>
{
    // Methods    
    public void Add(TKey key, ICollection<TValue> values);
    public void Add(TKey key, TValue value);
    public IEnumerator<TValue> GetValueEnumerator();
    public bool Remove(TValue item);
    public bool Remove(TKey key, TValue item);
    public void RemoveAll(TValue item);

    // Properties
    public int KeyCount { get; }
    public int ValueCount { get; }    
}

HashList（或多字典）是一个 HashTable，可以为特定键存储多个值。它基于标准的 Dictionary 类构建，并执行与 Dictionary<TKey, IList<TValue>> 类相同的功能，但语法更简洁。

[关于 Hash List 的更多信息]

Heap

public class Heap<T> : IVisitableCollection<T>, IHeap<T>
{
      // Methods
      public override void Add(T item);
      public T RemoveSmallestItem();

      // ...

      // Properties}
      public T SmallestItem { get; }

      // ...
}

Heap 数据结构是一种树结构，具有一个特殊属性：树的根节点包含最小项（最小堆）或最大项（最大堆）。此库中实现的 Heap 可以是最小堆或最大堆，在构造函数中设置。对于最大堆，使用的 IComparer<T> 实例包装在 ReverseComparer<IComparer<T>> 实例中，从而反转比较决策并以相反的顺序排序。

[关于堆的更多信息]

矩阵

public class Matrix : IVisitableCollection<double>, IMathematicalMatrix<T>
{
      // Methods
      public Matrix Invert();
      public bool IsEqual(Matrix m);
      public Matrix Minus(Matrix Matrix);
      public static Matrix operator +(Matrix m1, Matrix m2);
      public static Matrix operator *(Matrix m1, Matrix m2);
      public static Matrix operator *(Matrix m1, double number);
      public static Matrix operator *(double number, Matrix m2);
      public static Matrix operator -(Matrix m1, Matrix m2);
      public Matrix Plus(Matrix Matrix);
      public Matrix Times(Matrix Matrix);
      public Matrix Times(double number);
      public Matrix Transpose();
      
      public void AddColumn();
      public void AddColumn(params double[] values);
      public void AddColumns(int columnCount);
      public void AddRow();
      public void AddRow(params double[] values);
      public void AddRows(int rowCount);
      
      public Matrix GetSubMatrix(int rowStart, int columnStart, 
                                 int rowCount, int columnCount);
      public void InterchangeColumns(int firstColumn, int secondColumn);
      public void InterchangeRows(int firstRow, int secondRow);

      // ...

      // Properties
      public int Columns { get; }
      public bool IsSymmetric { get; }
      public double this[int i, int j] { get; set; }
      public int Rows { get; }

      // ...
}

Matrix 类对应于线性代数中的矩阵表示。它实现了简单的操作，如 Plus、Times、Minus 和 IsSymmetric。

Matrix 类的底层表示是一个简单的二维数组，类型为 double。

[关于矩阵的更多信息]

ObjectMatrix

public class ObjectMatrix<T> : IMatrix<T>, IVisitableCollection<T>
{    
    // Methods   
    public void Accept(IVisitor<T> visitor);
    public void AddColumn();
    public void AddColumn(params T[] values);
    public void AddColumns(int columnCount);
    public void AddRow();
    public void AddRow(params T[] values);
    public void AddRows(int rowCount);           
    public T[] GetColumn(int columnIndex);
    public IEnumerator<T> GetEnumerator();
    public T[] GetRow(int rowIndex);
    public ObjectMatrix<T> GetSubMatrix(int rowStart, 
           int columnStart, int rowCount, int columnCount);
    public void InterchangeColumns(int firstColumn, int secondColumn);
    public void InterchangeRows(int firstRow, int secondRow);
    public void Resize(int newNumberOfRows, int newNumberOfColumns);

    // ...

    // Properties
    public int Columns { get; }
    public int Count { get; }
    public bool IsSquare { get; }
    public T this[int i, int j] { get; set; }
    public int Rows { get; }
    
    // ...    
}

ObjectMatrix 类是对象二维数组的简单表示。它提供了比标准交错数组更多的功能，例如调整矩阵大小、单独获取行和列以及交换行/列。

PascalSet

public class PascalSet : IVisitableCollection<int>, ISet
{
      // Methods
      public PascalSet Difference(PascalSet set);
      public PascalSet Intersection(PascalSet set);
      public PascalSet Inverse();
      public bool IsEqual(PascalSet set);
      public bool IsProperSubsetOf(PascalSet set);
      public bool IsProperSupersetOf(PascalSet set);
      public bool IsSubsetOf(PascalSet set);
      public bool IsSupersetOf(PascalSet set);
      public static PascalSet operator +(PascalSet s1, PascalSet s2);
      public static bool operator >(PascalSet s1, PascalSet s2);
      public static bool operator >=(PascalSet s1, PascalSet s2);
      public static bool operator <(PascalSet s1, PascalSet s2);
      public static bool operator <=(PascalSet s1, PascalSet s2);
      public static PascalSet op_LogicalNot(PascalSet set);
      public static PascalSet operator *(PascalSet s1, PascalSet s2);
      public static PascalSet operator -(PascalSet s1, PascalSet s2);
      public PascalSet Union(PascalSet set);

      // ...

      // Properties
      public bool this[int i] { get; }
      public int LowerBound { get; }
      public int UpperBound { get; }

      // ...
}

PascalSet（之所以这样命名，是因为它实现了类似于 Pascal 中的 Set 类的集合）对应于集合的数学表示，其中集合可以包含有限集合中的项。PascalSet 类实现了简单的操作，如检查子集、超集、并集和集合之间的差集。

[关于集合的更多信息]

PriorityQueue

public class PriorityQueue<T> : IVisitableCollection<T>, IQueue<T>
{
      // Methods      
      public void Add(T item, int priority);
      public void DecreaseItemPriority(int by);
      public T Dequeue();
      public void Enqueue(T item);
      public void Enqueue(T item, int priority);
      public T Dequeue();
      public IEnumerator<Association<int, T>> GetKeyEnumerator();
      public void IncreaseItemPriority(int by);
      public T Peek();

      // ...
}

优先队列是一种特殊类型的队列，从中出队的项始终是队列中最小的（最小优先队列）或最大的（最大优先队列）。底层表示使用最小/最大堆（取决于优先队列的类型）实现。堆中的最大/最小项始终保留在根部，因此在队列的前端。

还提供了通过特定量增加或减少优先级的操作 - 这不会影响项的排序，因为所有项都受到操作的影响。

[关于优先队列的更多信息]

ReadOnlyPropertyCollection

public sealed class ReadOnlyPropertyList<T, TProperty> : 
              IList<TProperty>, IVisitableCollection<TProperty>
{ 
    // Methods
    public ReadOnlyPropertyList(IList<T> list, PropertyDescriptor property);
    public void Accept(IVisitor<TProperty> visitor);
    public int CompareTo(object obj);
    public bool Contains(TProperty item);
    public void CopyTo(TProperty[] array, int arrayIndex);
    public IEnumerator<TProperty> GetEnumerator();
    public int IndexOf(TProperty item);    
    
    // ...
    
    // Properties    
    public TProperty this[int index] { get; }
    TProperty IList<TProperty>.this[int index] { get; set; }    
}

ReadOnlyPropertyCollection 类是一个简单的实用集合，实现了 IList<TProperty>。它将列表中某个类型的属性公开为另一个列表。例如，通过使用原始列表而不是复制该列表，可以通过 ReadOnlyPropertyCollection 将 List<Person> 公开为 List<string>（姓名列表）。

红黑树

public class RedBlackTree<TKey, TValue> : IVisitableDictionary<TKey, TValue>
{
    // Methods    
    public void Accept(IVisitor<KeyValuePair<TKey, TValue>> visitor);
    public void Add(KeyValuePair<TKey, TValue> item);
    public void Add(TKey key, TValue value);    
    public bool Contains(KeyValuePair<TKey, TValue> item);
    public bool ContainsKey(TKey key);    
    public void DepthFirstTraversal(
           OrderedVisitor<KeyValuePair<TKey, TValue>> visitor);    
    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator();
    public bool Remove(TKey key);
    public bool TryGetValue(TKey key, out TValue value);

    // ...

    // Properties
    public IComparer<TKey> Comparer { get; }
    public TValue this[TKey key] { get; set; }
    public ICollection<TKey> Keys { get; }
    public TKey Max { get; }
    public TKey Min { get; }
    public ICollection<TValue> Values { get; }
    
    // ...
}

红黑树是一种自平衡二叉搜索树。本质上，这意味着从根节点到子节点的路径长度受到控制，因此你不会出现一条路径非常长，而其他路径很短的情况（这会降低搜索性能）。

NGenerics 中实现的红黑树实现了 IDictionary<TKey, TValue> 接口。

插入和删除算法改编自 Julienne Walker（Eternally confuzzled）的算法 - 如果你想了解红黑树，请先查看此处。

[关于红黑树的更多信息]

SortedList

public class SortedList<T> : IVisitableCollection<T>, IList<T>
{
      // Methods
      public override void Accept(IVisitor<T> visitor);
      public override void Add(T item);
      public override void Clear();
      public override int CompareTo(object obj);
      public override bool Contains(T item);
      public override void CopyTo(T[] array, int arrayIndex);
      public override IEnumerator<T> GetEnumerator();
      public override bool Remove(T item);
      public void RemoveAt(int index);

      // ...

      // Properties
      public IComparer<T> Comparer { get; }
      public T this[int i] { get; }

      // ...
}

SortedList<T> 类执行与 .NET 框架中的默认 SortedList<TKey, TValue> 类相同的功能，但它消除了我在使用该类时发现的两个细微差别：

此 SortedList 中可以包含重复项（标准版本不允许）。
项本身进行排序，不需要键（标准 SortedList 需要键值对）。

SkipList

public class SkipList<TKey, TValue> : IVisitableDictionary<TKey, TValue>
{
      // Methods
      public void Accept(IVisitor<KeyValuePair<TKey, TValue>> visitor);
      public void Add(KeyValuePair<TKey, TValue> item);
      public void Add(TKey key, TValue value);
      public bool ContainsKey(TKey key);
      public void CopyTo(KeyValuePair<TKey, 
                         TValue>[] array, int arrayIndex);
      public IEnumerator<KeyValuePair<TKey, 
                         TValue>> GetEnumerator();
      public bool Remove(TKey key);
      public bool TryGetValue(TKey key, out TValue value);
      // ...
      
      // Properties
      public IComparer<TKey> Comparer { get; }
      public int CurrentListLevel { get; }
      public TValue this[TKey key] { get; set; }
      public ICollection<TKey> Keys { get; }
      public int MaxListLevel { get; }
      public double Probability { get; }
      public ICollection<TValue> Values { get; }
      // ...
}

SkipList 是一种巧妙的数据结构，由 William Pugh 于 1990 年首次提出。你可以在此处找到他的原始论文。SkipList 的关键在于项在不同级别的链表中重复，级别（几乎）是随机选择的。与需要顺序比较的普通链表相比，它允许通过“跳过”多个列表项来快速搜索项。

Skip lists 通常有两种实现方式：使用多个链表，或使用矩阵结构（如二维链表）。此处实现的 SkipList 使用矩阵风格实现，并基于 Leslie Stanford 和 ger 的优秀工作。它实现了 IDictionary<TKey, TValue> 接口，因此可以像框架中的标准 Dictionary<TKey, TValue> 类一样使用。

请注意，虽然性能非常出色，但项的重复可能会导致内存迅速耗尽，特别是当最大级别数很高时。

[关于 Skip List 的更多信息]

默认数据结构扩展

该库包含一些默认的 .NET 泛型数据结构的实现，它们扩展以实现 IVisibleCollection<T> 接口。它们是：

VisitableHashtable<Tkey, TValue>
VisitableLinkedList<T>
VisitableList<T>
VisitableQueue<T>
VisitableStack<T>

实现的模式

单例

public sealed class Singleton<T> where T: new()
{
      // Methods
      private Singleton();

      // Properties
      public static T Instance { get; }

      // Fields
      private static T instance;
}

单例是一种用于最小化类实例数量到只有一个的模式。随着 C# 2.0 中泛型的出现，实现泛型单例非常简洁。可以在本文中找到另一种（或多或少相同的）单例模式实现，但我更喜欢静态初始化。

访问者模式

public interface IVisitor<T>
{
      // Methods
      void Visit(T obj);

      // Properties
      bool HasCompleted { get; }
}

所有继承自 IVisibleCollection<T> 接口的集合都实现了访问者模式。继承自 IVisitor<T> 的访问者可以用于访问各种集合，而不管正在访问的数据结构的内部结构如何。它提供了两个方法：

Visit 对对象执行某些操作。例如，可以想象一个计数访问者应用于整数数据结构，并在 Visit 方法中执行 += 操作。
HasCompleted 属性指示访问者是否希望继续访问集合中剩余的对象。这对于搜索访问者很有用，例如，当找到所需对象时，它可以停止访问。

[关于访问者模式的更多信息]

排序器

ISorter 接口

public interface ISorter<T>
{
      // Methods
      void Sort(IList<T> list);
      void Sort(IList<T> list, SortOrder order);
      void Sort(IList<T> list, IComparer<T> comparer);
      void Sort(IList<T> list, Comparison<T> comparison);
}

本库实现了多种排序器。默认的 .NET 框架库在排序方面选择不多，因此这些排序器应运而生。它具有泛型性，这意味着任何实现 IList<T> 的类都可以被排序，只要包含的项实现了 IComparable<T> 接口，或者提供了 IComparer<T> 实例。

提供的排序器如下：

算法

Dijkstra 算法

Dijkstra 算法为图中的单源最短路径问题提供了解决方案。换句话说，给定一个有向或无向 Graph<T> 作为输入，输出是一个表示从源顶点到图中每个其他顶点最短路径的图（如果顶点可从源顶点到达）。例如，请参见下方以 G 为源顶点的输入和输出图。


输入图		输出图 - 最短路径

[关于 Dijkstra 算法的更多信息]

关注点

C# 中对协方差的支持缺乏使得人们倾向于避免在此类工作中过度使用接口，仅仅是因为使用它们会迫使程序员进行比需要更多的强制类型转换（或者该库的开发者进行大量的隐式实现）。

此外，来自 C++ 背景的我，对多重继承和私有/保护继承的支持将极大地改变这种设计。希望有一天我们能在语言规范的某个遥远版本中看到对此的支持。

那么，接下来是什么？

还有一些排序器即将推出（基数排序、库排序、平滑排序、内省排序、耐心排序等）。
图算法（生成树、关键路径分析等）。
红黑树的实现。
斐波那契树。
还有许多其他不在我的简短列表中的。这可能是一个永无止境的项目，但我将努力只添加有用的东西。

参考文献

C# 排序器 [链接]
Bruno R. Preis - 使用面向对象设计模式的 C# 数据结构和算法 [链接]。
本文中包含的所有其他链接（维基百科等）。

历史

2007 年 3 月 5 日：1.2

新增内容

ObjectMatrix
HashList
RedBlackTree
ReadOnlyPropertyCollection

更改内容

Graph 的 AddVertex(T item) 和 AddEdge(Vertex<T> v1, Vertex<T> v2) 现在分别返回新创建的顶点和边。
为 Matrix 类型结构提取了接口 IMathematicalMatrix 和 IMatrix。
在 Association 类上添加了 ToKeyValuePair() 方法。
将 BinarySearchTree<T> 转换为 BinarySearchTree<TKey, TValue>：现在它实现了 IVisibleDictionary<TKey, TValue> 接口。
VisitableList<T> 和 GeneralTree<T> 现在分别实现了 ISortable<T> 和 ISortable<GeneralTree<T>>。
向 ISorter<T> 和 ISortable<T> 接口添加了方法，允许使用 Comparison<T> 委托进行排序。
在 IMAtrix、Matrix 和 ObjectMatrix 上添加了 InterchangeRows、InterchangeColumns、GetRow、GetColumn、AddColumn、AddRow。
向 GeneralTree<T> 添加了 Parent 属性，以便可以找到自底向上的路径。
向 GeneralTree<T> 添加了 Ancestors 属性，以查找树中当前节点的任何祖先。

2006 年 12 月 28 日：1.1 (NGenerics)

为了将此项目推向更高层次，DataStructures.NET 得到了一些改进，并被命名为 NGenerics。项目页面可以在此处找到。最新源代码可以在项目页面找到，但会定期在 CodeProject 上更新。

因此，进行了重大更改：

默认命名空间已更改为 NGenerics。
用于签名程序集的强名称密钥已更改，并且不再与库一起分发。这意味着如果你想从源代码编译 NGenerics，你需要提供自己的密钥（或关闭程序集的签名）。
希望这将是最后一次重大更改 - 现在情况应该会稳定下来……

新增内容

BinarySearchTree
欧几里得算法

更改内容

向 BinaryTree、GeneralTree 和 ITree 添加了 FindNode 方法。接口。
更改了 Matrix 的 IsSymmetric 方法，使其不进行当前矩阵的转置。
为 Matrix 提取了接口：IMatrix。
向 Matrix 添加了方法/属性：IsSquare、GetSubMatrix 和 Clone（Matrix 现在实现了 IClonable）。

详细的历史记录可以在源代码中找到。