Фундаментальные структуры данных в C#
Исключение нулевого указателя генерируется, когда приложение пытается использовать null в случае, когда требуется объект. К ним относятся:
- Вызов метода экземпляра объекта
null. - Доступ или изменение поля объекта
null. - Принимая длину
null, как если бы это был массив. - Доступ или изменение слотов
null, как если бы это был массив. - Бросок
nullкак будто это было значение Throwable.
Приложения должны бросать экземпляры этого класса, чтобы указать на другие незаконные использования объекта null.
Ссылка: http://docs.oracle.com/javase/8/docs/api/java/lang/NullPointerException.html
5 ответов
Существует ряд статей MSDN об этом предмете. Однако я действительно не прочитал текст сам. Я полагаю, что платформа наборов.NET имеет поврежденный интерфейс и не может быть расширена очень хорошо.
Существует также C5, библиотека, которую я исследую прямо сейчас.
По упомянутой выше причине у меня был проект реализовать мою собственную библиотеку наборов для.NET, но я остановил этот проект после того, как первый сравнительный тест показал что даже простой, неориентированный на многопотоковое исполнение дженерик Vector реализация медленнее, чем собственный компонент List<T>. Так как я заботился для не создания любого неэффективного кода IL, это означает, что.NET (еще) просто не удовлетворяют для записи наравне замен для внутренних структур данных, и что платформа.NET должна использовать некоторое закулисное знание для оптимизации встроенных классов набора.
Я рекомендовал бы два ресурса для структур данных, которые Вы упоминаете: Во-первых, существует Исходный код Платформы.NET (информация может быть найдена на блоге ScottGu здесь).
Другой полезный ресурс является Наборами Питания Wintellect, найденными на Codeplex здесь.
Надеюсь, это поможет!
Вот универсальное Дерево двоичного поиска. Единственная вещь, которую я не сделал, была реализовать 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--;
}
}
}
"Библиотека классов, обеспечивающая универсальные структуры данных и алгоритмы, не реализованные в стандартной платформе.NET".
Ротор выезда 2 (http://research.microsoft.com/sscli/) или отражатель использования (http://www.red-gate.com/products/reflector/) также видит, как Microsoft сделала это!!!