МИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра вычислительной техники
отчет
по лабораторной работе №5
по дисциплине «Алгоритмы и структуры данных»
Тема: «Поддержка произвольной последовательности в структуре данных для множеств»
Вариант №42
|
Студенты гр. 6307 |
|
Лазарев С.О. Медведев Е.Р. |
|
Преподаватель |
|
Колинько П.Г. |
Санкт-Петербург
2018
ЦЕЛЬ 3
ЗАДАНИЕ 3
Формализация задания 4
Обоснование выбора способа дополнения базовой структуры данных 4
Временная сложность 6
ВЫВОДЫ 7
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 8
ПРИЛОЖЕНИЕ 9
ЦЕЛЬ
Получить практические навыки по работе с последовательностями в структурах данных для множеств.
ЗАДАНИЕ
Составить и отладить программу, которая будет выполнять определенные операции над последовательностями
Формализация задания
Дополнить программу, составленную по теме ДДП, операциями над последовательностями:
- EXCL – вторая последовательность исключается из первой, если она является ее частью.
- SUBST – вторая последовательность включается в первую с указанной позиции p.
- CONCAT – вторая последовательность подсоединяется к концу первой, образуя ее продолжение.
Выбрать такой способ доработки структуры данных, чтобы получились эффективные алгоритмы.
Обоснование выбора способа дополнения базовой структуры данных
Если нужно поддерживать любую последовательность, то возможны следующие подходы:
-
Присоединить к каждому ключу дополнительное поле для хранения порядкового номера.
-
С помощью дополнительных указателей для каждого ключа сформировать из них список.
-
Создать массив указателей на ключи
Мы создаем массив указателей на ключи, т.к с этим массивом нам удобнее работать.
Пример:
Рис 1. Дерево А.
Рис. 2 Дерево В.
Рис 3. Дерево A CONCAT B.
Рис 4. Дерево A EXCL B.
Рис 5. Дерево A SUBST B.
Временная сложность
Таблица 1. Временная сложность
|
Операция |
Сложность |
|
EXCL |
O(n^2) |
|
SUBST |
O(n) |
|
CONCAT |
O(n) |
ВЫВОДЫ
В этой работе мы научились дополнять классы определенным способом, получили знания о представлении этих способов, научились выбирать способ дополнения. Провели работу с последовательностями в ДДП.
Выбор оказался достаточно хорошим, реализация данных функций с учетом особенностей выбранного способа последовательностей была не очень сложной и достаточно эффективной.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
-
Алгоритмы и структуры данных. – Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию, часть 2, глава 1 «Работа с иерархией объектов: наследование и полиморфизм».
ПРИЛОЖЕНИЕ
Source.Cpp
#include<iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include "avl_tree.h"
#include <time.h>
#define pow2(n) (1 << (n))
using namespace std;
const int N = 10;
avlTree generate();
avlTree ga() {
avlTree a = avlTree();
a.root = a.insert(a.root, 5); a.root = a.insert(a.root, 3); a.root = a.insert(a.root, 2); a.root = a.insert(a.root, 4);
a.root = a.insert(a.root, 6); a.root = a.insert(a.root, 7); a.root = a.insert(a.root, 9); a.root = a.insert(a.root, 1);
a.inorder(a.root);
return a;
}
avlTree gb() {
avlTree b = avlTree();
b.root = b.insert(b.root, 6); b.root = b.insert(b.root, 7); b.root = b.insert(b.root, 9);
b.inorder(b.root);
return b;
}