Collections

Материалы

• Хеширование. RSDN
• Коллекции в .NET Framework Class Library
• Двоичные деревья поиска
• Бинарные деревья
• Под капотом у Dictionary и ConcurrentDictionary
• The .NET Dictionary
• Обход бинарного дерева с помощью итератора. Под вопросом

Задачи

1. Реализовать простейший метод-калькулятор, описывающий выполнение основных арифметических операций на основе вычислительного стека. В качестве входных данных для вычислений использовать последовательность лексем арифметического выражения, записанных в постфиксной форме.
2. Разработать обобщенный класс-коллекцию "Очередь" (Queue), предоставляющий основные операции для работы с очередью в виде методов Enqueue(), Dequeue(), Peek(), а также возможность итерирования по коллекции (итератор реализовать «вручную»). Работу методов класса потестировать, используя в качестве аргумента типа следующие типы: int, string, пользовательский тип.
3. Разработать обобщенный класс-коллекцию "Стек" (Stack), предоставляющий основные операции для работы со стеком в виде методов Push(), Pop(), Peek(), а также предоставляющий возможность итерирования по коллекции, реализовав итератор «вручную». Работу методов класса потестировать, используя в качестве аргумента типа следующие типы: int, string, пользовательский тип.
4. Разработать обобщенный класс-коллекцию "Бинарное дерево поиска" (BinarySearchTree), предоставляющий основные операции для работы с бинарным деревом поиска. Предусмотреть возможность моделирования для элементов коллекции отношения порядка как на основе сравнения по умолчанию, так и с использованием подключаемого компаратора. Реализовать три способа обхода дерева: прямой (Preorder), поперечный (Inorder), обратный (Postorder) - для реализации использовать блок-итератор (yield). Работу методов класса потестировать, используя в качестве аргумента типа следующие типы:
   • int (использовать сравнение по умолчанию и подключаемый компаратор)
   • string (использовать сравнение по умолчанию и подключаемый компаратор)
   • пользовательский класc, реализующий интерфейс IComparable (использовать сравнение по умолчанию и подключаемый компаратор)
   • пользовательскую структуру, не реализующую интерфейс IComparable. Для тестирования разработанного типа использовать консольное приложение с интерфейсом командной строки или unit-тесты.
5. Создать обобщенные классы для представления квадратной, симметрической и диагональной матриц (симметрическая матрица – это квадратная матрица, которая совпадает с транспонированной к ней; диагональная матрица – это квадратная матрица, у которой элементы вне главной диагонали заведомо имеют значения равные значению по умолчанию параметра типа). Описать в созданных классах событие, которое происходит при изменении элемента матрицы с индексами (i, j). В классе-клиенте (консольное приложение) продемонстрировать работу события. Расширить функциональные возможности иерархии классов, реализовав метод сложения двух матриц. Создать unit-тесты для тестирования разработанных типов.