estructuras de datos fundamentales en C#

Question

Me gustaría saber cómo la gente poner en práctica las siguientes estructuras de datos en C# sin necesidad de utilizar las implementaciones de biblioteca de clases base de: -

• lista enlazada
• tabla hash
• búsqueda binaria Árbol
• rojo-Negro Árbol
• árbol B
• binomial Montón
• Fibonacci Heap

y cualquier otra estructura de datos fundamental en la que la gente pueda pensar!

Tengo curiosidad porque quiero mejorar mi comprensión de estas estructuras de datos y sería agradable ver las versiones de C# en lugar de los típicos ejemplos de C en Internet.

Answer 1

Hay una serie de MSDN articles sobre este tema. Sin embargo, realmente no he leído el texto yo mismo. Creo que el framework de colecciones de .NET tiene una interfaz rota y no se puede extender muy bien.

También hay C5, una libray que estoy investigando en este momento.

Por la razón mencionada anteriormente, tuve el proyecto de implementar mi propia biblioteca de colecciones para .NET pero detuve este proyecto después de que el primer punto de referencia reveló que incluso una implementación genérica Vector directa y no segura para subprocesos es más lento que el List<T> nativo. Como he tenido cuidado de no producir ningún código IL ineficiente, esto significa que .NET simplemente no es adecuado (todavía) para escribir reemplazos par-par para estructuras de datos intrínsecas, y que el framework .NET tiene que usar algo detrás del -escenas de conocimiento para optimizar las clases de colección integradas.

Answer 2

Recomendaría dos recursos para las estructuras de datos que menciona: Primero, está el Código fuente del .NET Framework (la información se puede encontrar en el blog de ScottGu here).

Otro recurso útil es Colecciones de energía de Wintellect encontradas en Codeplex here.

Espero que esto ayude!

Answer 3

Aquí hay un árbol genérico de búsqueda binaria. Lo único que no hice fue implementar IEnumerable <T> para que pudiera recorrer el árbol usando un enumerador. Sin embargo, eso debería ser bastante directo.

Agradecimiento especial a Scott Mitchel por su artículo BSTTree, lo usé como referencia en el método de eliminación.

La clase Node:

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; } 
     }   
    } 

Y la clase de árbol real:

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

Salida del rotor 2 (http://research.microsoft.com/sscli/) o usar el reflector (http://www.red-gate.com/products/reflector/) también ver cómo Microsoft lo hizo !!!

Answer 5

NGenerics

"Una biblioteca de clases que proporciona estructuras y algoritmos no aplicadas en el marco .NET estándar de datos genéricos."