Назад к основам – обобщенные структуры данных и алгоритмы в .NET 2.0 - Матрицы, наборы и деревья
ОГЛАВЛЕНИЕ
Матрица
public class Matrix : IVisitableCollection<double>, IMathematicalMatrix<T>
{
// методы
public Matrix Invert();
public bool IsEqual(Matrix m);
public Matrix Minus(Matrix Matrix);
public static Matrix operator +(Matrix m1, Matrix m2);
public static Matrix operator *(Matrix m1, Matrix m2);
public static Matrix operator *(Matrix m1, double number);
public static Matrix operator *(double number, Matrix m2);
public static Matrix operator -(Matrix m1, Matrix m2);
public Matrix Plus(Matrix Matrix);
public Matrix Times(Matrix Matrix);
public Matrix Times(double number);
public Matrix Transpose();
public void AddColumn();
public void AddColumn(params double[] values);
public void AddColumns(int columnCount);
public void AddRow();
public void AddRow(params double[] values);
public void AddRows(int rowCount);
public Matrix GetSubMatrix(int rowStart, int columnStart,
int rowCount, int columnCount);
public void InterchangeColumns(int firstColumn, int secondColumn);
public void InterchangeRows(int firstRow, int secondRow);
// ...
// свойства
public int Columns { get; }
public bool IsSymmetric { get; }
public double this[int i, int j] { get; set; }
public int Rows { get; }
// ...
}
Класс Matrix соответствует записи матрицы в линейной алгебре. Он реализует простые операции вроде Plus, Times, Minus и IsSymmetric.
Базовое представление класса Matrix – простой двумерный массив типа double.
[Дополнительная информация о матрицах]
Матрица объектов
public class ObjectMatrix<T> : IMatrix<T>, IVisitableCollection<T>
{
// методы
public void Accept(IVisitor<T> visitor);
public void AddColumn();
public void AddColumn(params T[] values);
public void AddColumns(int columnCount);
public void AddRow();
public void AddRow(params T[] values);
public void AddRows(int rowCount);
public T[] GetColumn(int columnIndex);
public IEnumerator<T> GetEnumerator();
public T[] GetRow(int rowIndex);
public ObjectMatrix<T> GetSubMatrix(int rowStart,
int columnStart, int rowCount, int columnCount);
public void InterchangeColumns(int firstColumn, int secondColumn);
public void InterchangeRows(int firstRow, int secondRow);
public void Resize(int newNumberOfRows, int newNumberOfColumns);
// ...
// свойства
public int Columns { get; }
public int Count { get; }
public bool IsSquare { get; }
public T this[int i, int j] { get; set; }
public int Rows { get; }
// ...
}
Класс ObjectMatrix – простое представление 2-мерного массива объектов. Он предоставляет кое-какой функционал, отличный от стандартного непрямоугольного массива, вроде изменения размеров матрицы, получения строк и столбцов по отдельности, и перестановки строк / столбцов.
Набор Паскаля
public class PascalSet : IVisitableCollection<int>, ISet
{
// методы
public PascalSet Difference(PascalSet set);
public PascalSet Intersection(PascalSet set);
public PascalSet Inverse();
public bool IsEqual(PascalSet set);
public bool IsProperSubsetOf(PascalSet set);
public bool IsProperSupersetOf(PascalSet set);
public bool IsSubsetOf(PascalSet set);
public bool IsSupersetOf(PascalSet set);
public static PascalSet operator +(PascalSet s1, PascalSet s2);
public static bool operator >(PascalSet s1, PascalSet s2);
public static bool operator >=(PascalSet s1, PascalSet s2);
public static bool operator <(PascalSet s1, PascalSet s2);
public static bool operator <=(PascalSet s1, PascalSet s2);
public static PascalSet op_LogicalNot(PascalSet set);
public static PascalSet operator *(PascalSet s1, PascalSet s2);
public static PascalSet operator -(PascalSet s1, PascalSet s2);
public PascalSet Union(PascalSet set);
// ...
// свойства
public bool this[int i] { get; }
public int LowerBound { get; }
public int UpperBound { get; }
// ...
}
Набор Паскаля (так назван, потому что реализует набор наподобие класса Set, применяемого в Pascal) соответствует математической записи набора, где элементы в некоторой конечной совокупности могут содержаться в коллекции. Класс PascalSet реализует простые операции вроде проверки поднаборов, расширенных наборов, объединений и разностей между наборами.
[Дополнительная информация о наборах]
Очередь с приоритетом
public class PriorityQueue<T> : IVisitableCollection<T>, IQueue<T>
{
// методы
public void Add(T item, int priority);
public void DecreaseItemPriority(int by);
public T Dequeue();
public void Enqueue(T item);
public void Enqueue(T item, int priority);
public T Dequeue();
public IEnumerator<Association<int, T>> GetKeyEnumerator();
public void IncreaseItemPriority(int by);
public T Peek();
// ...
}
Очередь с приоритетом является особым типом очереди, где удаленный из очереди элемент всегда является наименьшим (в неубывающей очереди с приоритетом) или наибольшим (в невозрастающей очереди с приоритетом) из элементов, содержащихся в очереди. Базовое представление реализовано с помощью неубывающей/невозрастающей кучи (в зависимости от типа очереди с приоритетом). Максимальный/минимальный элемент в куче всегда хранится в корне, а значит, впереди очереди.
Также имеются методы для увеличения приоритетов и уменьшения приоритетов на конкретные величины – это не влияет на упорядоченность элементов, так как операция воздействует на все элементы.
[Дополнительная информация об очередях с приоритетом]
Коллекция свойств только для чтения
public sealed class ReadOnlyPropertyList<T, TProperty> :
IList<TProperty>, IVisitableCollection<TProperty>
{
// методы
public ReadOnlyPropertyList(IList<T> list, PropertyDescriptor property);
public void Accept(IVisitor<TProperty> visitor);
public int CompareTo(object obj);
public bool Contains(TProperty item);
public void CopyTo(TProperty[] array, int arrayIndex);
public IEnumerator<TProperty> GetEnumerator();
public int IndexOf(TProperty item);
// ...
// свойства
public TProperty this[int index] { get; }
TProperty IList<TProperty>.this[int index] { get; set; }
}
Класс ReadOnlyPropertyCollection является простой служебной коллекцией, реализующей IList<TProperty>. Он предоставляет свойство типа в списке как другой список. Например, List<Person> может предоставляться как List<string> (список имен) посредством ReadOnlyPropertyCollection, путём использования оригинального списка, не делая копию того списка.
Красно-черное дерево
public class RedBlackTree<TKey, TValue> : IVisitableDictionary<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 bool Contains(KeyValuePair<TKey, TValue> item);
public bool ContainsKey(TKey key);
public void DepthFirstTraversal(
OrderedVisitor<KeyValuePair<TKey, TValue>> visitor);
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator();
public bool Remove(TKey key);
public bool TryGetValue(TKey key, out TValue value);
// ...
// свойства
public IComparer<TKey> Comparer { get; }
public TValue this[TKey key] { get; set; }
public ICollection<TKey> Keys { get; }
public TKey Max { get; }
public TKey Min { get; }
public ICollection<TValue> Values { get; }
// ...
}
Красно-черное дерево является самобалансирующимся двоичным деревом поиска. Это значит, что длина путей от корневого узла до дочерних узлов контролируется – нельзя получить крайне длинный путь к одному узлу и короткие пути к другим (что снижает производительность поиска).
Красно-черное дерево реализовано в NGenerics с реализацией интерфейса IDictionary<TKey, TValue>.
Алгоритмы вставки и удаления были адаптированы из алгоритмов Джульена Уолкера (вечно запутанный).