fondamentales Structures de données en C#

Question

Je voudrais savoir comment les gens mettent en œuvre les structures de données suivantes en C# sans utiliser les implémentations de la bibliothèque de classes de base: -

• Liste liés
• Hash Table
• binaire Recherche Arbre
• Arbre Rouge-Noir
• B-Tree
• binomial Heap
• Fibonacci Heap

et toutes les autres structures de données fondamentales auxquelles les gens peuvent penser! Je suis curieux car je veux améliorer ma compréhension de ces structures de données et ce serait bien de voir les versions C# plutôt que les exemples C typiques sur Internet!

Answer 1

Il existe une série de MSDN articles sur ce sujet. Cependant, je n'ai pas vraiment lu le texte moi-même. Je crois que le cadre de collections par .NET a une interface cassée et ne peut pas être étendu très bien.

Il y a aussi C5, une librairie que j'étudie actuellement.

Pour la raison mentionnée ci-dessus, j'ai eu le projet d'implémenter ma propre bibliothèque de collections pour .NET mais j'ai arrêté ce projet après que le premier benchmark a révélé que même une implémentation Vector générique simple et non thread-safe est plus lent que le natif List<T>. Comme j'ai pris soin de ne pas produire de code IL inefficace, cela signifie que .NET n'est tout simplement pas (encore) adapté pour écrire des remplacements à la parité pour les structures de données intrinsèques, et que le framework .NET doit en utiliser un derrière le -signifie les connaissances pour optimiser les classes de collection intégrées.

Answer 2

Je recommanderais deux ressources pour les structures de données que vous mentionnez: Tout d'abord, il existe le code source .NET Framework (vous trouverez des informations sur le blog here de ScottGu).

Une autre ressource utile est les collections de puissance de Wintellect trouvées sur le codeplex here.

Espérons que cela aide!

Answer 3

Voici un arbre de recherche binaire générique. La seule chose que je n'ai pas faite était implémenter IEnumerable <T> ainsi vous pourriez traverser l'arbre en utilisant un énumérateur. Cependant, cela devrait être assez simple.

Un merci spécial à Scott Mitchel pour son article BSTTree, je l'ai utilisé comme référence sur la méthode delete.

Le Noeud Classe:

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

Et la classe réelle des arbres:

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

Check out rotor 2 (http://research.microsoft.com/sscli/) ou utiliser le réflecteur (http://www.red-gate.com/products/reflector/) aussi voir comment Microsoft a fait !!!

Answer 5

NGenerics

« Une bibliothèque de classes fournissant des structures de données génériques et des algorithmes non mis en œuvre dans le cadre .NET standard. »