基本數據結構

Question

我想知道人們是如何實現在C＃中的以下數據結構不使用基類庫實現： -

• 鏈表
• 哈希表
• 二叉搜索樹
• 紅 - 黑樹
• B樹
• 二項堆
• 斐波那契堆

和任何其他人們可以想到的基本數據結構！

我很好奇，因爲我想提高對這些數據結構的理解，很高興看到C＃版本，而不是在Internet上的典型C示例！

Answer 1

在這個問題上有一系列MSDN articles。但是，我自己並沒有真正閱讀過這些文字。我相信.NET的集合框架有一個破損的界面，不能很好地擴展。

還有C5，我正在調查的libray現在。

由於上述原因，我有一個項目來實現我自己的.NET集合庫，但是我在第一個基準測試中發現即使是一個簡單的，非線程安全的通用實現Vector比原生List<T>慢。由於我已經注意到不會產生任何低效的IL代碼，這意味着.NET不適合（但是）編寫內置數據結構的內置替代品，並且.NET框架必須使用一些後置代碼 - 瞭解優化內建集合類的知識。

Answer 2

我會爲您提到的數據結構推薦兩種資源： 首先，有.NET Framework源代碼（可在ScottGu的博客here上找到相關信息）。

另一個有用的資源是在Codeplex here上找到的Wintellect的Power Collections。

希望這會有所幫助！

Answer 3

這是一個通用的二叉搜索樹。我沒有做的唯一的事情是實現IEnumerable <T>所以你可以使用枚舉器遍歷樹。但是，這應該是相當直接的。

特別感謝Scott Mitchel爲他的BSTTree文章，我用它作爲刪除方法的參考。

節點類：

class BSTNode<T> where T : IComparable<T> 
    { 
     private BSTNode<T> _left = null; 
     private BSTNode<T> _right = null;   
     private T _value = default(T); 

     public T Value 
     { 
      get { return this._value; } 
      set { this._value = value; } 
     } 

     public BSTNode<T> Left 
     { 
      get { return _left; } 
      set { this._left = value; } 
     } 

     public BSTNode<T> Right 
     { 
      get { return _right; } 
      set { this._right = value; } 
     }   
    } 

和實際的樹類：

class BinarySearchTree<T> where T : IComparable<T> 
    { 
     private BSTNode<T> _root = null; 
     private int _count = 0; 

     public virtual void Clear() 
     { 
      _root = null; 
      _count = 0; 
     } 

     public virtual int Count 
     { 
      get { return _count; } 
     } 

     public virtual void Add(T value) 
     { 
      BSTNode<T> newNode = new BSTNode<T>(); 
      int compareResult = 0; 

      newNode.Value = value; 

      if (_root == null) 
      { 
       this._count++; 
       _root = newNode; 
      } 
      else 
      { 
       BSTNode<T> current = _root; 
       BSTNode<T> parent = null; 

       while (current != null) 
       { 
        compareResult = current.Value.CompareTo(newNode.Value); 

        if (compareResult > 0) 
        { 
         parent = current; 
         current = current.Left; 
        } 
        else if (compareResult < 0) 
        { 
         parent = current; 
         current = current.Right; 
        } 
        else 
        { 
         // Node already exists 
         throw new ArgumentException("Duplicate nodes are not allowed."); 
        } 
       } 

       this._count++; 

       compareResult = parent.Value.CompareTo(newNode.Value); 
       if (compareResult > 0) 
       { 
        parent.Left = newNode; 
       } 
       else 
       { 
        parent.Right = newNode; 
       } 
      } 
     } 

     public virtual BSTNode<T> FindByValue(T value) 
     { 
      BSTNode<T> current = this._root; 

      if (current == null) 
       return null; // Tree is empty. 
      else 
      { 
       while (current != null) 
       { 
        int result = current.Value.CompareTo(value); 
        if (result == 0) 
        { 
         // Found the corrent Node. 
         return current; 
        } 
        else if (result > 0) 
        { 
         current = current.Left; 
        } 
        else 
        { 
         current = current.Right; 
        } 
       } 

       return null; 
      } 
     } 

     public virtual void Delete(T value) 
     { 

      BSTNode<T> current = this._root; 
      BSTNode<T> parent = null; 

      int result = current.Value.CompareTo(value); 

      while (result != 0 && current != null) 
      { 
       if (result > 0) 
       { 
        parent = current; 
        current = current.Left; 
       } 
       else if (result < 0) 
       { 
        parent = current; 
        current = current.Right; 
       } 

       result = current.Value.CompareTo(value); 
      } 

      if (current == null) 
       throw new ArgumentException("Cannot find item to delete."); 



      if (current.Right == null) 
      { 
       if (parent == null) 
        this._root = current.Left; 
       else 
       { 
        result = parent.Value.CompareTo(current.Value); 
        if (result > 0) 
        { 
         parent.Left = current.Left; 
        } 
        else if (result < 0) 
        { 
         parent.Right = current.Left; 
        } 
       } 
      } 
      else if (current.Right.Left == null) 
      { 
       if (parent == null) 
        this._root = current.Right; 
       else 
       { 
        result = parent.Value.CompareTo(current.Value); 
        if (result > 0) 
        { 
         parent.Left = current.Right; 
        } 
        else if (result < 0) 
        { 
         parent.Right = current.Right; 
        } 
       } 
      } 
      else 
      { 

       BSTNode<T> furthestLeft = current.Right.Left; 
       BSTNode<T> furthestLeftParent = current.Right; 

       while (furthestLeft.Left != null) 
       { 
        furthestLeftParent = furthestLeft; 
        furthestLeft = furthestLeft.Left; 
       } 

       furthestLeftParent.Left = furthestLeft.Right; 

       furthestLeft.Left = current.Left; 
       furthestLeft.Right = current.Right; 

       if (parent != null) 
       { 
        result = parent.Value.CompareTo(current.Value); 
        if (result > 0) 
        { 
         parent.Left = furthestLeft; 
        } 
        else if (result < 0) 
        { 
         parent.Right = furthestLeft; 
        } 
       } 
       else 
       { 
        this._root = furthestLeft; 
       } 
      } 

      this._count--; 
     } 
    } 
} 

Answer 4

退房轉子2（http://research.microsoft.com/sscli/），或使用反射鏡（http://www.red-gate.com/products/reflector/）也希望看到微軟是如何做到的！

Answer 5

NGenerics

「A類庫提供通用數據結構，並在標準的.NET框架不實現的算法」。