objetos - Estructuras de datos fundamentales en C#

estructuras en c# ejemplos

Question

Me gustaría saber cómo las personas implementan las siguientes estructuras de datos en C # sin utilizar las implementaciones de la biblioteca de la clase base:

• Lista enlazada
• Tabla de picadillo
• Árbol de búsqueda binaria
• Árbol Rojo-Negro
• B-Tree
• Montón binomial
• Montón de Fibonacci

¡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

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.

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

La clase de nodo:

 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 2

Hay una serie de artículos de MSDN 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 biblioteca 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 de Vector genérica directa y no segura para subprocesos es más lenta que la List<T> nativa List<T> . 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 3

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 aquí ).

Otro recurso útil son las Colecciones de Poder de Wintellect que se encuentran en Codeplex aquí .

¡Espero que esto ayude!

Answer 4

Consulte Rotor 2 ( http://research.microsoft.com/sscli/ ) o use reflector ( http://www.red-gate.com/products/reflector/ ) ¡también vea cómo Microsoft lo hizo!

Answer 5

NGenerics

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