Я хотел бы знать, как люди реализуют следующие структуры данных в С# без использования реализаций библиотеки базового класса: -
и любые другие фундаментальные структуры данных, о которых люди могут подумать!
Мне любопытно, что я хочу улучшить свое понимание этих структур данных, и было бы неплохо увидеть версии С#, а не типичные примеры C в Интернете!
В этой статье приведен ряд статей MSDN. Тем не менее, я действительно не читал текст сам. Я считаю, что структура коллекций .NET имеет сломанный интерфейс и не может быть расширена очень хорошо.
Там также C5, libray, который я изучаю прямо сейчас.
По причине, упомянутой выше, у меня был проект по реализации моей собственной библиотеки коллекций для .NET, но я остановил этот проект после того, как первый тест показал, что даже простой, не потокобезопасный общий Vector реализация медленнее, чем нативный List<T>. Поскольку я позаботился о том, чтобы не создавать какой-либо неэффективный IL-код, это означает, что .NET просто не подходит (пока) для записи на-парных замен для встроенных структур данных и что платформа .NET должна использовать некоторые из -scenes для оптимизации встроенных классов коллекции.
Вот общее двоичное дерево поиска. Единственное, чего я не делал, это реализовать IEnumerable <T> поэтому вы можете пересечь дерево с помощью счетчика. Однако это должно быть достаточно прямым.
Особая благодарность Скотту Митчел за его статью BSTTree, я использовал ее как ссылку на метод удаления.
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; }
}
}
И фактический класс Tree:
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--;
}
}
}
Я бы рекомендовал два ресурса для структур данных, которые вы упомянули: Во-первых, есть исходный код .NET Framework (информацию можно найти в блоге ScottGu здесь).
Другим полезным ресурсом являются коллекции Wintellect Power Collections, найденные в Codeplex здесь.
Надеюсь, это поможет!
"Библиотека классов, предоставляющая общие структуры данных и алгоритмы, не реализованные в стандартной платформе .NET.
Проверьте Rotor 2 (http://research.microsoft.com/sscli/) или используйте отражатель (http://www.red-gate.com/products/reflector/), также посмотрите, как это сделала Microsoft!