АИСД (2 семестр) на С# / Лабоаторная3

_{МИНОБРНАУКИ РОССИИ}

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

отчет

по лабораторной работе №3

по дисциплине «Алгоритмы и структуры данных»

Тема: Комбинирование структуры данных

Студенты гр.
Преподаватель

Санкт-Петербург

2023

Цель работы – изучить комбинирование структуры данных.

Задание (Вариант 2):

Мощность множества: 26

Операции над множествами: (A \ B \ C) ⊕ D U E

Базовая СД: АВЛд — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

Реализуемые операции над последовательностями:

CONCAT— Вторая последовательность подсоединяется к концу первой, образуя её продолжение.

EXCL — Вторая последовательность исключается из первой, если она является ее частью.

MUL— Последовательность сцепляется сама с собой заданное количество раз

Описание работы программы

В связи с тем, что в c# нет стандартной библиотеки шаблонов STL, AVL дерево было реализовано в виде класса AVL. Элементы множества хранятся в узлах дерева. Для того чтобы получить множество используется прямой обход всех вершин дерева. Чтобы применять операции к AVL деревьям для работы c множествами в классе AVL была выполнена перегрузка операторов + (пересечение), & (объединение), / (вычитание).

Чтобы применять операции к AVL деревьям для работы с последовательностями в классе Node (узел дерева) были созданы переменные duplicates (количество повторяющихся элементов последовательности) и список numbers, в котором хранятся номера элементов в последовательности.

Так, например, если последовательность 3 5 6 5 7 8 5. То для узла содержащего значение 5: duplicates=3; List<int> numbers=new List<int>() {2, 4, 7};

В классе TreeOperations расположены методы, которые позволяют применять операции к AVL деревьям для работы с последовательностями, CONCAT(), EXCEL(), MUL(). В отличие от работы с множествами при работе с последовательностями учитываются порядковые номера элементов.

Оценка временной сложности алгоритма.

+ (пересечение)	& (объединение)	/ (вычитание)	CONCAT	MUL	EXCEL
O(n*(log(N)))	O(n*(log(N)))	O(n*(log(N)))	O(n*(log(N)))	O(n*(log(N)))	O(n*(log(N)))

Пример работы программы

Вывод: В ходе работы множества были представлены в виде АВЛ-деревьев. Реализованы операции для работы с множествами. АВЛ-дерево было доработано для хранения произвольной последовательности. Реализованы операции для работы с последовательностями.

Список использованных источников

Колинько, П. Г. Пользовательские структуры данных: Методические указания по дисциплине “Алгоритмы и структуры данных, часть 1”.– СПБ.: СПБГЭТУ “ЛЭТИ”, 2022. – 64 с.

Код программы:

AVL.cs

Container.cs

Program1.cs

TreeOperations.cs