МИНОБРНАУКИ РОССИИСАНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)Кафедра Вычислительной техникиОТЧЕТпо лабораторной работе № 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 дерева с автобалансировкой. Так же были получены новые знания в сфере возможностей языка С++ и о его библиотеках..

---

Смотрите также файлы

• ценности воспитания детей в условиях глобальных вызовов xxi века.doc

• Доклад Типичные недостатки семейного воспитания и пути их преодоления. Формы работы классного руководителя с детьми группы риска.docx

• Логопедия как наука основные категории по учебной дисциплине Логопедия.docx

• Лабораторная работа 2 Модульное программирование. Интерфейсы. По дисциплине Объектноориентированное программирование.docx

• Бж таырыбы ант диабеті 1 тип абылдаан Мехмет Зия Генчер Орындаан Пернебаева сел Тобы жм807.pptx