Назад к основам – обобщенные структуры данных и алгоритмы в .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 двоичного дерева – оно рекурсивно считает число уровней вниз по дереву.

[Дополнительная информация о деревьях]