Практическая 4 Гусаров. Отчет по выполнению практического задания

• Название: Отчет по выполнению практического задания
• Анкор: Практическая 4 Гусаров
• Дата: 24.11.2022
• Размер: 251.36 Kb.
• Имя файла: Практическая 4 Гусаров.docx
• Тип: Отчет; #810366

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение высшего образования

«МИРЭА – Российский технологический университет»

РТУ МИРЭА




Отчет по выполнению практического задания Тема: Сбалансированные деревья поиска (СДП) и их применение для поиска данных в файле.
Дисциплина: Структуры и алгоритмы обработки данных
Выполнил студент Гусаров М.К.


группа ИКБО-18-21




^{Фамилия}И.О
.


Москва 2022

Цель

- получить навыки в разработки и реализации алгоритмов управления бинарным деревом поиска и сбалансированными бинарными деревьями поиска (АВЛ – деревьями);

- получить навыки в применении файловых потоков прямого доступа к данным файла;

- получить навыки в применении сбалансированного дерева поиска для прямого доступа к записям файла.

1 Задание - 1

Постановка задачи

Разработать приложение, которое использует бинарное дерево поиска (БДП) для поиска записи с ключом в файле, структура которого представлена в задании 2 вашего варианта.

1. Разработать класс «Бинарное дерево поиска». Тип информационной части узла ключ и ссылка на запись в файле (как в практическом задании 2). Методы: включение элемента в дерево, поиск ключа в дереве, удаление ключа из дерева, отображение дерева.

2. Разработать класс управления файлом (если не создали в практическом задании 2). Включить методы: создание двоичного файла записей фиксированной длины из заранее подготовленных данных в текстовом файле; поиск записи в файле с использованием БДП; остальные методы по вашему усмотрению.

3. Разработать и протестировать приложение.

4. Подготовить отчет.

2 Код реализации программы – задание 1

class bstree {

struct node {

node* left;

node* right;

T val;

node(void) noexcept :left(nullptr), right(nullptr) {}

};

private:

node* tr;

public:

bstree(void) noexcept :tr(nullptr) {}

bstree() { clear(); }

bstree(const bstree&) = delete;

bstree& operator = (const bstree&) = delete;

public:

//добавить void add(const T& v) {

node* p;

if (tr == nullptr) {

tr = new node();

tr->val = v;

}

else {

node** rp = _find(v);

if (tr != nullptr) {

p = new node();

p->val = v;

*rp = p;

}

}

}

void add(T&& v) {

node* p;

if (tr == nullptr) {

tr = new node();

tr->val = std::forward(v);

}

else {

node** rp = _find(v);

if (tr != nullptr) {

p = new node();

p->val = std::forward(v);

*rp = p;

}

}

}

//удаление с возвращением min-значения

T pop_min(void) noexcept {

T v;

node** rp = &tr, * p = tr;

if (tr != nullptr) {

while (p->left != nullptr) {

rp = &p->left;

p = p->left;

}

}

if (p != nullptr) {

v = std::forward(p->val);

_erase(rp, p);

}

return std::forward(v);

}

//удаление с возвращением max-значения

T pop_max(void) noexcept {

T v;

node** rp = &tr, * p = tr;

if (tr != nullptr) {

while (p->right != nullptr) {

rp = &p->right;

p = p->right;

}

}

if (p != nullptr) {

v = std::forward(p->val);

_erase(rp, p);

}

return std::forward(v);

}

//удаление всех

void clear(void) noexcept {

_clear(tr);

tr = nullptr;

}

bool empty(void) const noexcept { return (tr == nullptr); }

private:

node** _find(const T& v) noexcept {

node** rp = &tr, * p = tr;

while (p != nullptr) {

if (v == p->val)

return nullptr;

else if (v < p->val) {

rp = &p->left;

p = p->left;

}

else {

rp = &p->right;

p = p->right;

}

}

return rp;

}

void _erase(node** rp, node* p) noexcept {

if (p->right == nullptr)

*rp = p->left;

else {

node* t = p->right;

if (t->left == nullptr) {

t->left = p->left;

*rp = t;

}

else {

node* i = t->left;

while (i->left != nullptr) {

t = i;

i = t->left;

}

t->left = i->right;

i->left = p->left;

i->right = p->right;

*rp = i;

}

}

delete p;

}

void _clear(node* p) noexcept {

if (p != nullptr) {

if (p->left != nullptr)

_clear(p->left);

if (p->right != nullptr)

_clear(p->right);

delete p;

}

}

};

/* чтение массива данных из строки, консоли или файла

N = кол-во элементов

данные

...

*/

template

void get_array(std::vector& vs, std::istream& _in) {

T v;

size_t n;

if (!(_in >> n) || !n)

return;

vs.resize(n);

for (size_t i = 0; i < n; ++i) {

if (!(_in >> vs[i]))

break;

}

}

int main(void) {

std::vector::size_type i;

//сортировка целых чисел

std::vector ia;

/* ввод из консоли

get_array(ia, std::cin);*/

// для примера ввод из строки

char s[] = "10\n5 4 7 9 8 2 1 3 0 6";

std::istringstream sp(s);

get_array(ia, sp);

bstree ti;

for (auto v : ia)

ti.add(v);

for (i = 0; !ti.empty(); ++i)

ia[i] = ti.pop_min();

for (auto v : ia)

std::cout << v << ' ';

std::cout << std::endl;

//сортировка строк

std::vector sa;

//ввод из строки

char s1[] = "7\nALLAH\nSHARIAT\nEBALROT\nSOSIXUI\nPIDORAS\nALGOL\nBASIC";

std::istringstream sp1(s1);

get_array(sa, sp1);

bstree ts;

for (i = 0; i < sa.size(); ++i)

ts.add(std::move(sa[i]));

for (i = 0; !ts.empty(); ++i)

sa[i] = ts.pop_min();

for (const auto& v : sa)

std::cout << v << ' ';

std::cout << std::endl;

//сортировка действительных чисел по убыванию

std::vector da;

/* ввод из файла

std::ifstream fp("file.txt");

get_array(da, fp);

fp.close();

*/

//для примера из строки

char s2[] = "5\n 0.9 20.5 -123.1 0.5 4.4";

std::istringstream sp2(s2);

get_array(da, sp2);

bstree td;

for (const auto& d : da)

td.add(d);

for (i = 0; !td.empty(); ++i)

da[i] = td.pop_max();

for (const auto& v : da)

std::cout << v << ' ';

std::cin.get();

return 0;

}

3 Тестирование программы – задание 1

Рисунок 1 – Тестирование программы – задание 1

4 Задание - 2

Постановка задачи

Разработать приложение, которое использует сбалансированное дерево поиска, предложенное в варианте, для доступа к записям файла.

1. Разработать класс СДП с учетом дерева варианта. Структура информационной части узла дерева включает ключ и ссылку на запись в файле (адрес места размещения). Основные методы: включение элемента в дерево; поиск ключа в дереве с возвратом ссылки; удаление ключа из дерева; вывод дерева в форме дерева (с отображением структуры дерева). 2. Разработать приложение, которое создает и управляет СДП в соответствии с заданием.

3. Выполнить тестирование.

4. Определить среднее число выполненных поворотов (число поворотов на общее число вставленных ключей) при включении ключей в дерево при формировании дерева из двоичного файла.

5. Оформить отчет

6. Варианты индивидуальных заданий задания 2

Таблица 1 – вариант упражнений

№ варианта	Сбалансированное дерево поиска (СДП)	Структура элемента множества (ключ – подчеркнутое поле) остальные поля представляют данные элемента
9	Красно - черное	Владелец телефона: номер телефона – последовательность символов, адрес

5 Код реализации программы – задание 2

#include

#include

#include
class baza{

public:

static std::vector < std::string > string_split(

std::string s,

std::string delimiter)

{

size_t pos_start = 0;

size_t pos_end;

size_t delim_len = delimiter.length();

std::string token;

std::vector < std::string > res;

while ((pos_end = s.find(delimiter, pos_start)) != std::string::npos)

{

token = s.substr(pos_start, pos_end - pos_start);

pos_start = pos_end + delim_len;

res.push_back(token);

}

res.push_back(s.substr(pos_start));

return res;

}

};

class Node

{

public:

long key;

int address;

Node* parent;

Node* left;

Node* right;

Node(long key, int address)

{

this->key = key;

this->address = address;

this->parent = nullptr;

this->left = nullptr;

this->right = nullptr;

}

};

class SplayTree

{

public:

static void main(std::vector& args) throws FileNotFoundException

{

SplayTree* tree = new SplayTree();

tree->insertFromFile();

tree->output();

std::cout << "\n" << std::endl;

std::cout << "Adress nomera 89627156421 v fajle = " + std::to_string(tree->searchTree(89627156421l)->address) << std::endl;

tree->output();

std::cout << "\n" << std::endl;

tree->deleteNode(89827421497l);

tree->deleteNode(89359172451l);

tree->deleteNode(89268725389l);

tree->deleteNode(89266715862l);

// otsutstvuet v dereve

tree->output();

std::cout << "\n" << std::endl;

tree->deleteNode(89266715863l);

tree->output();

std::cout << "\n" << std::endl;

std::cout << ru::luckoff::SplayTree::SplayTree::searchInFileByAddress(tree->searchTree(89627156421l)->address) << std::endl;

}

static std::string searchInFileByAddress(int address) throws FileNotFoundException

{

std::string FILE_NAME = "Tree.txt";

File file = java.io.File(FILE_NAME);

FileInputStream inputStream = java.io.FileInputStream(file);

try (BufferedReader br = java.io.BufferedReader(java.io.InputStreamReader(inputStream));)

{

std::string line;

while ((line = br.readLine()) != nullptr)

{

if (Settlement::string_split(line, " ")[0].equalsIgnoreCase(to_string(address)))

{

return line;

}

}

}

catch (IOException e)

{

e.printStackTrace();

}

return nullptr;

}

void insertFromFile() throws FileNotFoundException

{

std::string FILE_NAME = "Tree.txt";

File file = java.io.File(FILE_NAME);

FileInputStream inputStream = java.io.FileInputStream(file);

try (BufferedReader br = java.io.BufferedReader(java.io.InputStreamReader(inputStream));)

{

std::string line;

while ((line = br.readLine()) != nullptr)

{

int address = stoi(Settlement::string_split(line, " ")[0]);

long key = long long.parseLong(Settlement::string_split(line, " ")[1]);

this->insert(key, address);

}

}

catch (IOException e)

{

e.printStackTrace();

}

}
private:

Node* root;

public:

SplayTree()

{

root = nullptr;

}

void output()

{

outputHelper(this->root, 0);

}

void outputHelper(Node*& node, int l)

{

if (node != nullptr)

{

outputHelper(node->right, l + 1);

for (int i = 1; i <= l; i++)

{

std::cout << " ";

}

std::cout << std::to_string(node->key) + "\n";

outputHelper(node->left, l + 1);

}

}

Node* searchTree(long k)

{

Node* x = searchTreeHelper(root, k);

if (x != nullptr)

{

splay(x);

}

return x;

}

private:

Node* searchTreeHelper(Node*& node, long key)

{

if (node == nullptr || key == node->key)

{

return node;

}

if (key < node->key)

{

return searchTreeHelper(node->left, key);

}

return searchTreeHelper(node->right, key);

}

public:

void deleteNode(long data)

{

deleteNodeHelper(this->root, data);

}

private:

void deleteNodeHelper(Node*& node, long key)

{

Node* x = nullptr;

Node* t = nullptr;

Node* s = nullptr;

while (node != nullptr)

{

if (node->key == key)

{

x = node;

}

if (node->key <= key)

{

node = node->right;

}

else

{

node = node->left;

}

}

if (x == nullptr)

{

std::cout << "Klyuch " + std::to_string(key) + " otsutstvuet v dereve" << std::endl;

return;

}

splay(x);

if (x->right != nullptr)

{

t = x->right;

t->parent = nullptr;

}

else

{

t = nullptr;

}

s = x;

s->right = nullptr;

x = nullptr;

if (s->left != nullptr)

{

// remove x

s->left->parent = nullptr;

}

root = join(s->left, t);

s = nullptr;

}

void leftRotate(Node*& x)

{

Node* y = x->right;

x->right = y->left;

if (y->left != nullptr)

{

y->left->parent = x;

}

y->parent = x->parent;

if (x->parent == nullptr)

{

this->root = y;

}

else if (x == x->parent->left)

{

x->parent->left = y;

}

else

{

x->parent->right = y;

}

y->left = x;

x->parent = y;

}

void rightRotate(Node*& x)

{

Node* y = x->left;

x->left = y->right;

if (y->right != nullptr)

{

y->right->parent = x;

}

y->parent = x->parent;

if (x->parent == nullptr)

{

this->root = y;

}

else if (x == x->parent->right)

{

x->parent->right = y;

}

else

{

x->parent->left = y;

}

y->right = x;

x->parent = y;

}

void splay(Node*& x)

{

while (x->parent != nullptr)

{

if (x->parent->parent == nullptr)

{

if (x == x->parent->left)

{

// zig rotation

rightRotate(x->parent);

}

else

{

// zag rotation

leftRotate(x->parent);

}

}

else if (x == x->parent->left && x->parent == x->parent->parent->left)

{

// zig-zig rotation

rightRotate(x->parent->parent);

rightRotate(x->parent);

}

else if (x == x->parent->right && x->parent == x->parent->parent->right)

{

// zag-zag rotation

leftRotate(x->parent->parent);

leftRotate(x->parent);

}

else if (x == x->parent->right && x->parent == x->parent->parent->left)

{

// zig-zag rotation

leftRotate(x->parent);

rightRotate(x->parent);

}

else

{

// zag-zig rotation

rightRotate(x->parent);

leftRotate(x->parent);

}

}

}

Node* join(Node*& s, Node*& t)

{

if (s == nullptr)

{

return t;

}

if (t == nullptr)

{

return s;

}

Node* x = maximum(s);

splay(x);

x->right = t;

t->parent = x;

return x;

}

public:

Node* maximum(Node*& node)

{

while (node->right != nullptr)

{

node = node->right;

}

return node;

}

void insert(long key, int address)

{

Node* node = new Node(key, address);

Node* y = nullptr;

Node* x = this->root;

while (x != nullptr)

{

y = x;

if (node->key < x->key)

{

x = x->left;

}

else

{

x = x->right;

}

}

node->parent = y;

if (y == nullptr)

{

root = node;

}

else if (node->key < y->key)

{

y->left = node;

}

else

{

y->right = node;

}

splay(node);

}

};

int main(int argc, char** argv) {

std::vector parameter(argv + 1, argv + argc);

SplayTree::main(parameter);

return 0

6 Тестирование программы – задание 2

Рисунок 2 – Тестирование программы – задание 2


Рисунок 3 – Тестирование программы – задание 2

7 Вывод

В ходе работы над практической работой было изучена работа с сбалансированными деревьями поиска, а также были получены умения и навыки:
- разработки и реализации алгоритмов управления бинарными деревьями поиска и сбалансированными бинарными деревьями поиска

-применение файловых потоков прямого доступа к данным файла

-применение сбалансированного дерева поиска для прямого доступа к записям фала

8 Список литературы

1. 
   Справочная информация программы Microsoft Visual Studio 2019.
   
2. 
   Лекции по структуре и алгоритмах обработки данных(СиАОД) / Макеева О.В.– Москва, РТУ МИРЭА, 2022.