Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ПОБУДОВА АБСТРАКТНОГО ТИПУ ДАНИХ. БІНАРНЕ ДЕРЕВО ПОШУКУ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Обчислювальний практикум
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Звіт
З лабораторної роботи №1.4
На тему:
«ПОБУДОВА АБСТРАКТНОГО ТИПУ ДАНИХ.
БІНАРНЕ ДЕРЕВО ПОШУКУ»
з дисципліни:
«Обчислювальний практикум»
Львів – 2013
Мета роботи:
Вивчити побудову та застосування до розв’язання прикладних задач динамічних структур даних.
Теоретична частина
Абстрактний тип даних
Абстрактний тип даних (АТД) - це тип даних, який надає для роботи з елементами цього типу певний набір функцій, а також можливість створювати елементи цього типу за допомогою спеціальних функцій. Вся внутрішня структура такого типу захована від розробника програмного забезпечення - в цьому і полягає суть абстракції. Абстрактний тип даних визначає набір функцій, незалежних від конкретної реалізації типу, для оперування його значеннями. Конкретні реалізації АТД називаються структурами даних.
В програмуванні абстрактні типи даних звичайно представляються у вигляді інтерфейсів, які приховують відповідні реалізації типів. Програмісти працюють з абстрактними типами даних виключно через їх інтерфейси, оскільки реалізація може в майбутньому змінитися. Такий підхід відповідає принципу інкапсуляції в об'єктно-орієнтованому програмуванні. Сильною стороною цієї методики є саме приховування реалізації. Раз зовні опублікований тільки інтерфейс, то поки структура даних підтримує цей інтерфейс, всі програми, що працюють із заданою структурою абстрактним типом даних, будуть продовжувати працювати. Розробники структур даних стараються, не змінюючи зовнішнього інтерфейсу і семантики функцій, поступово допрацьовувати реалізації, покращуючи алгоритми по швидкості, надійності і використовуваної пам'яті.
Різниця між абстрактними типами даних і структурами даних, які реалізують абстрактні типи, можна пояснити на наступному прикладі. Абстрактний тип даних список може бути реалізований за допомогою масиву або лінійного списку, з використанням різних методів динамічного виділення пам'яті. Однак кожна реалізація визначає один і той же набір функцій, який повинен працювати однаково (по результату, а не по швидкості) для всіх реалізацій.
Абстрактні типи даних дозволяють досягти модульності програмних продуктів і мати кілька альтернативних взаємозамінних реалізацій окремого модуля.
Дерево
Деревом називається множина взаємно-зв’язаних елементів які називаються вузлами розташованих по рівнях. Бінарне дерево- це скінченна множина вузлів кожен з яких або порожній, або складається з кореня пов’язаного з двома різними бінарними деревами які називається лівим і правим піддеревом.
Двійкове (або Бінарне) дéрево пóшуку (англ. binary search tree, BST) в інформатиці — двійкове дерево, в якому кожній вершині xспівставлене певне значення val[x]. При цьому такі значення повинні задовольняти умові впорядкованості:
нехай x — довільна вершина двійкового дерева пошуку. Якщо вершина y знаходиться в лівому піддереві вершини x, то val[y] ≤ val[x].
Якщо у знаходиться у правому піддереві x, то val[y] ≥ val[x].
Таке структурування дозволяє надрукувати усі значення у зростаючому порядку за допомогою простого алгоритму центрованого обходу дерева.
Представляється таке дерево вузлами наступного вигляду:
*Node = (element, key, left, right, parent). Доступ до дерева T здійснюється за допомогою посилання root.
Бінарні дерева пошуку набагато ефективніші в операціях пошуку, аніж лінійні структури, в яких витрати часу на пошук пропорційні O(n), де n — розмір масиву даних, тоді як в повному бінарному дереві цей час пропорційний в середньому O(log2n) або O(h), де h — висота дерева (хоча гарантувати, що h не перевищує log2n можна лише для збалансованих дерев, які є ефективнішими на пошукових алгоритмах, аніж прості бінарні дерева пошуку).
Завдання
Побудова АТД
Змоделювати абстрактний тип даних (АТД) , який використати в Завданні 4. Оформити АТД у вигляді класа. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів з АТД.
Алгоритм розв’язання задачі:
Tree.h
#pragma once
#include<iostream>
#include<fstream>
#include<clocale>
using std::cout;
using std::cin;
using std::endl;
class Node//клас, який представляє вітку
{
private:
char* Data;//дані у вітці
Node** SubNodes;//вказівники на підвітки
Node* Parent;//вказівник на вітку-батька
int SubNodesNum;//кількість підвіток у вітки
int MaxSubNodesNum;//максимальна кількість підвіток у вітки
public:
Node(Node* ParentNode, char* NodeData, int _MaxSubNodeNum)
{
MaxSubNodesNum = _MaxSubNodeNum;
Parent = ParentNode;
SubNodes = new Node*[1000];
SubNodesNum = 0;
for(int i = 0; i < MaxSubNodesNum; i++)
{
SubNodes[i] = NULL;
}
if(NodeData != NULL)
{
Data = new char[strlen(NodeData)+1];
strcpy(Data, NodeData);
}
else
{
Data = NULL;
}
}
virtual Node* AddSubNode(char* _Data)//додає підвітку до вітки
{
if(SubNodesNum < MaxSubNodesNum)
{
SubNodes[SubNodesNum] = new Node(this,_Data, MaxSubNodesNum);
return SubNodes[SubNodesNum++];
}
else
{
return NULL;
}
}
void DeleteSubNode(int index)
{
if(index > 0 && index <this->GetSubNodesNum())
{
if(index == GetSubNodesNum()+1)
{
this->SubNodes[index] = NULL;
this->SubNodesNum--;
return;
}
for(int i = index; i <this->GetSubNodesNum() - 1; i++)
{
this->SubNodes[i] = this->SubNodes[i+1];
}
this->SubNodesNum--;
}
}
char* GetData()//повертає дані у вітці
{
return Data;
}
int GetSubNodesNum()
{
return SubNodesNum;
}
Node* GetParent()
{
return Parent;
}
Node* operator[](int index)//перевантажений оператор [] поверне вказівник на підвітку залежно від індексу в квадратних дужках [index]
{
if(index >=0 && index < SubNodesNum)
{
return SubNodes[index];
}
else
{
return NULL;
}
}
};
class Tree//клас дерево
{
public:
Tree(char* RootData,int _MaxSubNode)//в конструкторі вказується скільки підвіток може мати кожна вітка дерева
{
Root = new Node(NULL,RootData, _MaxSubNode);
}
Node* GetRoot()
{
return Root;
}
private:
Node* Root;
};
class Iterator
{
public:
Iterator(Tree* _ItsTree)
{
this->ItsTree = _ItsTree;
this->TotalNode = this->ItsTree->GetRoot();
this->TotalSubNodeIndex = 0;
}
Node* CreateSubNode(char* Data)
{
return this->TotalNode->AddSubNode(Data);
}
bool DeleteSubNode(int index)
{
if((*this->TotalNode)[index] != NULL)
{
this->TotalNode->DeleteSubNode(index);
return true;
}
else
{
return false;
}
}
void ReturnToRoot()
{
this->TotalNode = this->ItsTree->GetRoot();
this->TotalSubNodeIndex = 0;
return;
}
bool ToSubNode(int index)
{
if((*this->TotalNode)[index] != NULL)
{
this->TotalNode = (*this->TotalNode)[index];
this->TotalSubNodeIndex = index;
}
else
{
return false;
}
}
bool ToNextNode()
{
if((*this->TotalNode->GetParent())[this->TotalSubNodeIndex + 1] != NULL)
{
this->TotalNode = (*this->TotalNode->GetParent())[TotalSubNodeIndex + 1];
TotalSubNodeIndex++;
return true;
}
else
{
return false;
}
}
bool ToPreviousNode()
{
if((*this->TotalNode->GetParent())[this->TotalSubNodeIndex - 1] != NULL)
{
this->TotalNode = (*this->TotalNode->GetParent())[--TotalSubNodeIndex];
return true;
}
else
{
return false;
}
}
void PrintTotalData()
{
cout <<this->TotalNode->GetData() << endl;
return;
}
private:
Tree* ItsTree;
Node* TotalNode;
int TotalSubNodeIndex;//показує якою підвіткою попорядку є дана вітка
};
Main.cpp
#include"Tree.h"
void main()
{
Tree* tree = new Tree(NULL, 1000);
Iterator* iterator = new Iterator(tree);
iterator->CreateSubNode("Node1");
iterator->CreateSubNode("Node2");
iterator->CreateSubNode("Node3");
iterator->CreateSubNode("Node4");
iterator->ToSubNode(0);
for(int i = 0; i < 4;i++)
{
iterator->PrintTotalData();
iterator->ToNextNode();
}
iterator->ReturnToRoot();
iterator->DeleteSubNode(2);
iterator->ToSubNode(2);
for(int i = 0; i < 3;i++)
{
iterator->PrintTotalData();
iterator->ToPreviousNode();
}
iterator->ReturnToRoot();
iterator->ToSubNode(2);
iterator->PrintTotalData();
}
Результат виконання програми:
/
Рис1. Ескіз вікна з результатом виконання програми
Висновок: Виконавши дану лабораторну роботу, я зрозумів що собою являє абстрактний тип даних, а також як працює і реалізовується АТД "Бінарне дерево пошуку" .
14.04.2015 19:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора