Назад к основам – обобщенные структуры данных и алгоритмы в .NET 2.0 - Использование кода и структуры данных
ОГЛАВЛЕНИЕ
Использование кода и структуры данных
Интерфейс IVisitableCollection
public interface IVisitable<T>
{
// методы
void Accept(IVisitor<T> visitor);
}
public interface IVisitableCollection<T> :
ICollection<T>, IEnumerable<T>,
IEnumerable, IComparable, IVisitable<T>
{
// свойства
bool IsEmpty { get; }
bool IsFixedSize { get; }
bool IsFull { get; }
}
Шаблон посетителя является, пожалуй, одним из наиболее используемых (и переоцененным) шаблонов в информатике. Интерфейс IVisitableCollection<T> предоставляет интерфейс для любой коллекции, чтобы принимать посетителей – тем самым изолируя действие, выполняемое над объектами, от реализации конкретной структуры данных. Дополнительную информацию о посетителях смотрите в интерфейсе IVisitor<T>.
При вызове метода Accept коллекция перечисляет все содержащиеся в ней объекты и вызывает метод Visit посетителя для каждого из них. IsEmpty и IsFull возвращают логическое значение, указывающее, пуст или полон текущий экземпляр, соответственно. Метод IsFull применяется только к коллекциям фиксированного размера и указывает, что коллекция не растет динамически по мере добавления элементов к ней.
Другой интерфейс по имени IVisitableDictionary<T> представляет коллекции на базе словарей, также реализуя интерфейс IVisitable<T>.
Ассоциация
public class Association<TKey, TValue>
{
// методы
public Association(TKey key, TValue value);
public KeyValuePair<TKey, TValue> ToKeyValuePair();
// свойства
public TKey Key { get; set; }
public TValue Value { get; set; }
}
Класс, копирующий функционал стандартного KeyValuePair<TKey, TValue>, но с добавленными устанавливающими методами для свойств Key и Value. Класс Association применяется в основном в структуре данных SortedList, где надо поддерживать отношение ключ-значение между приоритетом и значением элемента.
Мультимножество
public class Bag<T> : IVisitableCollection<T>, IBag<T>
{
// методы
public void Accept(IVisitor<KeyValuePair<T, int>> visitor);
public void Add(T item, int amount);
public Bag<T> Difference(Bag<T> bag);
public IEnumerator<KeyValuePair<T, int>> GetCountEnumerator();
public IEnumerator<T> GetEnumerator();
public Bag<T> Intersection(Bag<T> bag);
public bool IsEqual(Bag<T> bag);
public static Bag<T> operator +(Bag<T> b1, Bag<T> b2);
public static Bag<T> operator *(Bag<T> b1, Bag<T> b2);
public static Bag<T> operator -(Bag<T> b1, Bag<T> b2);
public bool Remove(T item, int max);
public Bag<T> Union(Bag<T> bag);
// ...
// свойства
public int this[T item] { get; }
// ....
}
Мультимножество является структурой данных, содержащей любое число элементов. Оно отличается от набора тем, что позволяет содержаться в коллекции множественным вхождениям элементов, следовательно, более приспособлено к подсчету элементов. Содержащаяся в этой библиотеке структура данных мультимножество реализована с помощью структуры данных Dictionary<T, int>, хранящей ссылку на число элементов, содержащееся в мультимножестве.
Класс Bag реализован с помощью объекта Dictionary<KeyType, int>, где объект хешируется с помощью счетчика, представляющего количество конкретных элементов, содержащихся в мультимножестве. Реализованы стандартные операции:
• Пересечение – возвращает мультимножество, содержащее элементы, находящиеся в обоих мультимножествах.
• Объединение - возвращает мультимножество со всеми элементами в обоих мультимножествах.
• Разность - "вычесть" одно мультимножество из другого. Эта операция вычитает количество элементов, содержащихся в другом мультимножестве, из задействованного мультимножества.
Двоичное дерево
public class BinaryTree<T> : IVisitableCollection<T>, ITree<T>
{
// методы
public void Add(BinaryTree<T> subtree);
public virtual void breadthFirstTraversal(IVisitor<T> visitor);
public virtual void
DepthFirstTraversal(OrderedVisitor<T> orderedVisitor);
public BinaryTree<T> GetChild(int index);
public bool Remove(BinaryTree<T> child);
public virtual void RemoveLeft();
public virtual void RemoveRight();
// ...
// свойства
public virtual T Data { get; set; }
public int Degree { get; }
public virtual int Height { get; }
public virtual bool IsLeafNode { get; }
public BinaryTree<T> this[int i] { get; }
public virtual BinaryTree<T> Left { get; set; }
public virtual BinaryTree<T> Right { get; set; }
// ...
}
Двоичное дерево является особым видом дерева, где каждый узел в дереве имеет максимум два дочерних узла. Класс BinaryTree<T> содержит указатели на максимум два дочерних узла. Методы BreadthFirstTraversal и DepthFirstTraversal предоставляют указанный доступ конкретным посетителям. Обход в глубину производится тремя способами: симметричный, в обратном порядке или в прямом порядке, где симметричный применим только к двоичным деревьям.
Свойство Height работает путем рекурсивного подсчета количества уровней в этом двоичном дереве и ниже. Так как каждый потомок BinaryTree сам является BinaryTree, каждый потомок имеет свою собственную высоту.
[Дополнительная информация о двоичных деревьях]
Двоичное дерево поиска
public class BinarySearchTree<TKey, TValue> :
IVisitableDictionary<TKey, TValue>,
IDictionary<TKey, TValue>,
IVisitableCollection<KeyValuePair<TKey, TValue>>
{
// методы
public void Accept(IVisitor<KeyValuePair<TKey, TValue>> visitor);
public void Add(KeyValuePair<TKey, TValue> item);
public void Add(TKey key, TValue value);
public int CompareTo(object obj);
public bool Contains(KeyValuePair<TKey, TValue> item);
public bool ContainsKey(TKey key);
public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex);
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator();
public IEnumerator<KeyValuePair<TKey, TValue>> GetSortedEnumerator();
public bool Remove(KeyValuePair<TKey, TValue> item);
public bool Remove(TKey key);
public bool TryGetValue(TKey key, out TValue value);
// ...
// свойства
public IComparer<TKey> Comparer { get; }
public int Count { get; }
public bool IsEmpty { get; }
public bool IsFixedSize { get; }
public bool IsFull { get; }
public bool IsReadOnly { get; }
public TValue this[TKey key] { get; set; }
public ICollection<TKey> Keys { get; }
public KeyValuePair<TKey, TValue> Max { get; }
public KeyValuePair<TKey, TValue> Min { get; }
public ICollection<TValue> Values { get; }
// ...
}
Двоичное дерево поиска является структурой поиска данных, имеющей форму двоичного дерева. Его внутреннее устройство простое: элементы, меньшие, чем родительский узел, помещаются в левое поддерево, а элементы, которые больше, помещаются в правое поддерево. Это обеспечивает быстрый поиск элементов путем исключения большего числа элементов на каждом уровне. Но один из его худших случаев – добавление элементов в последовательном порядке - O(n) сравнений требуется в худшем случае. Однако из-за своей простоты это подходящая структура поиска данных для рандомизированных входных данных. Если рандомизацию данных нельзя обеспечить, следует использовать сбалансированное дерево поиска (например, красно-черное дерево).
[Дополнительная информация о двоичных деревьях поиска]
Дек
public sealed class Deque<T> : IVisitableCollection<T>, IDeque<T>
{
// методы
public T DequeueHead();
public T DequeueTail();
public void EnqueueHead(T obj);
public void EnqueueTail(T obj);
// ...
// свойства
public T Head { get; }
public T Tail { get; }
// ...
}
Структура данных дек (или двусторонняя очередь) похожа на структуру данных очередь, за исключением того, что она может поставить в очередь или убрать из очереди в голове или хвосте текущей очереди. Дек реализован как связанный список, обеспечивающий легкий доступ к началу и концу списка.
[Дополнительная информация о деках]
Общее дерево
public class GeneralTree<T> : IVisitableCollection<T>, ITree<T>
{
// методы
public void Add(GeneralTree<T> child);
public void breadthFirstTraversal(Visitor<T> visitor);
public void DepthFirstTraversal(OrderedVisitor<T> orderedVisitor);
public GeneralTree<T> GetChild(int index);
public bool Remove(GeneralTree<T> child);
public void RemoveAt(int index);
public void Sort(ISorter<GeneralTree<GeneralTree<T>>> sorter);
public void Sort(ISorter<GeneralTree<GeneralTree<T>>> sorter,
IComparer<GeneralTree<T>> comparer);
public void Sort(ISorter<GeneralTree<GeneralTree<T>>> sorter,
Comparison<GeneralTree<T>> comparison);
// ...
// свойства
public T Data { get; }
public int Degree { get; }
public int Height { get; }
public virtual bool IsLeafNode { get; }
public GeneralTree<T> this[int i] { get; }
public GeneralTree<T>[] Ancestors { get; }
public GeneralTree<T> Parent { get; }
// ...
}
Общее дерево – самый обобщенный вид структуры данных дерево. Оно разрешает любое число дочерних узлов у данного узла (в том числе ноль узлов, что делает его листовым узлом). Класс GeneralTree<T>, как класс BinaryTree<T>, предусматривает обход в ширину и обход в глубину для посетителей.
GeneralTree реализовано с помощью списка для слежения за потомками (тоже типа GeneralTree). Свойство Height работает аналогично свойству Height двоичного дерева – оно рекурсивно считает число уровней вниз по дереву.