Главная страница
Навигация по странице:

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

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


    Скачать 251.36 Kb.
    НазваниеОтчет по выполнению практического задания
    АнкорПрактическая 4 Гусаров
    Дата24.11.2022
    Размер251.36 Kb.
    Формат файлаdocx
    Имя файлаПрактическая 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.


    написать администратору сайта