23 lines
4.2 KiB
Markdown
23 lines
4.2 KiB
Markdown
# AiSD
|
||
## Тема: Комбинированные структуры данных и стандартная библиотека шаблонов
|
||
##### Вариант 35
|
||
|
||
|
||
### Цель работы
|
||
Получение практических знаний по созданию собственного контейнера для работы с множествами и последовательностями
|
||
### Задание
|
||
Реализовать индивидуальное задание темы «Множества + последовательности» в виде программы, используя свой контейнер для дерева двоичного поиска с хранением высоты дерева в каждом узле и доработать его для поддержки операций с последовательностями.
|
||
#### 1. Описание созданного контейнера
|
||
Для реализации поставленной задачи было решено использовать контейнер Container, на который ссылаются итераторы разного типа: он используется для хранения элементов множества. В основе реализации этого контейнера лежит дерево двоичного поиска, что обеспечивает оптимальное время выполнения операций: поиск, вставка, удаление за O(log n), где n – мощность множества
|
||
Но при всех плюсах есть существенный недостаток – при работе с элементами множества теряется информация о порядке добавления элемента и возможных повторах элементов
|
||
Для генерации множества используется генератор псевдослучайных чисел, из-за чего элементы множества могут повторяться. Также для генерации дерева была использована автобалансировка, поэтому элементы располагаются в том порядке, в котором они были разложены при автобалансировке, поэтому порядок элементов отличается от теоретического
|
||
Использованы две функции вывода дерева: та, которая выводит их в том порядке, в каком они были заложены в контейнер, и та, которая выводит значения узлов дерева, переходя от родителей к сыновьям
|
||
|
||
#### 2. Реализованные функции для операций над последовательностями
|
||
Т.к. в библиотеки algorithm отсутствуют операции CHANGE и SUBST, они были реализованы самостоятельно
|
||
Функция subst вставляет последовательность B в последовательность А в заданное место. Сложность реализованной функции O(n log n)
|
||
Функция change заменяет последовательность элементами второй последовательности, начиная с позиции p. Сложность реализованной функции O(n)
|
||
|
||
### Вывод
|
||
Стандартные контейнеры подходят для работы с множествами, однако для работы с последовательностями, где важен порядок добавления элементов в множество, стандартные контейнеры нужно дорабатывать.
|
||
В результате выполнения лабораторной работы был создан пользовательский контейнер на основе деревьев двоичного поиска |