Файл: Комбинированные структуры данных и стандартная библиотека шаблонов.docx
Добавлен: 10.11.2023
Просмотров: 73
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
МИНОБРНАУКИ РОССИИ
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ
ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)
Кафедра Вычислительной техники
ОТЧЕТ
по лабораторной работе № 3
по дисциплине «Алгоритмы и структуры данных»
Тема: комбинированные структуры данных и стандартная библиотека шаблонов
| Студент гр. 0305 | | Солодков Н.С. |
| Студент гр. 0305 | | Боев И. C. |
| Преподаватель | | Колинько П. Г. |
Санкт-Петербург
2022
Цель работы.
Изучить различные структуры данных для хранения множеств и последовательностей, в том числе с использованием стандартных библиотек и шаблонов языка С++, научиться работать с такими структурами.
Задание (вариант 11)
Реализовать индивидуальное задание темы «Множества + последовательности» в виде программы, используя свой контейнер для заданной структуры данных (хеш-таблицы или одного из вариантов ДДП), и доработать его для поддержки операций с последовательностями. Для операций с контейнером рекомендуется использовать возможности библиотеки алгоритмов. Программа должна реализовывать цепочку операций над множествами. Результат каждого шага цепочки операций выводится на экран.
-
Базовая СД: 1-2-дерево -
Дополнительные операции: CONCAT, SUBST, CHANGE -
Цепочка операций: A | B ^ C – D – E -
Мощность каждого множества: 16
Контейнер Tree
Основной контейнер представлен классом Tree.
Для реализации операций над множествами были объявлены свои поддерживаемые итераторы, и использованы стандартные функции библиотеки STL: set_union, set_intersection, set_difference и set_symmetric_difference.
Поддержка последовательностей реализована хранением в каждом узле вектора порядковых номеров, что позволяет не дублировать сами ключи в дереве. Такая форма организации позволяет восстанавливать последовательность за O(n), хотя возможно и является достаточно ёмкой с точки зрения памяти.
Предполагаемая сложность выполнения операций над множествами O(log n). Сложность операций над последовательностями в общем случае представляет из себя O(n), так как была выбрана стратегия манипуляции с восстановленными векторами последовательностей и обратным преобразованием их в дерево. Таким образом в общем случае: Восстановление последовательностей: O(n) => Операции над векторами в общем случае O(n) => Обратное преобразование в 1-2 дерево O(n). Ни одна операция не превышает линейную границу.
Пример работы программы на случайных данных
Рис. 1. Деревья A, B, C, D, E.
Рис. 2. Деревья F, G, H, I.
Рис. 3. Цепочка операций A | B ^ C – D – E.
Рис. 4. Дополнительные операции CONCAT, SUBST, CHANGE
.
Вывод.
При выполнении работы, были получены новые знания в области структур данных и их реализации. Была спроектирована своя структура данных и отработаны методы написания операций с множествами и последовательностями. В течении работы применялись разные подходы и в итоге были найдены возможности реализации с учётом всех нюансов 1-2 дерева с автобалансировкой. Так же были получены новые знания в сфере возможностей языка С++ и о его библиотеках.
.