Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Структура даних БІНАРНЕ ДЕРЕВО ПОШУКУ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування Частина III Структури даних та алгоритми
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи № 6
на тему:
"Структура даних БІНАРНЕ ДЕРЕВО ПОШУКУ"
з дисципліни:
" Програмування. Частина III. Структури даних та алгоритми "
Львів – 2013
Мета роботи:
Вивчення абстрактної структури даних "Бінарне дерево пошуку". Набуття практичних навичок побудови дерева та використання його для розв'язання прикладних задач.
Постановка задачі:
І. Завдання 1: Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати:
послідовність вершин дерева при проходженні його у прямому порядку;
послідовність листків дерева при проходженні його у зворотньому порядку;
послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку.
Виконати індивідуальне завдання згідно з варіантом.
Знайти середнє арифметичне значення всіх листків дерева.
ІІ. Завдання 2: Використовуючи побудоване в Завданні 1 бінарне дерево пошуку, розв'язати задачу згідно з варіантом.
Варіанти завдань:
1. Операційні системи типу UNIX, PC-DOS (старші версії) підтримують деревоподібну структуру збереження даних на диску. При цьому мінімальна іменована одиниця інформації називається файлом. Файли об'єднуються в каталоги, кожний з яких теж має ім'я. Множина каталогів і окремих файлів можуть у свою чергу також утворити каталог більш високого рівня. Каталог найвищого рівня називається кореневим. Кількість рівнів вкладеності не обмежена. Розглядати тільки випадки без порожніх каталогів (тобто каталогів, що не мають файлів).
Скласти програму для виводу на екран по рівнях:
а) списку всіх елементів даних, "вкладених" у довільний каталог на всіх рівнях;
б) списку всіх каталогів, "вкладених" у довільний каталог;
в) списку всіх файлів, "вкладених" у довільний каталог;
г) списку всіх елементів даних кореневого каталогу, виведених в алфавітному порядку.
Приклад:
На заданій схемі елемент 0 є кореневим каталогом диску;
елементи 2,3,6,10 - каталогами; елементи 1,4,7,9,8,5 - файлами.
Для каталогу 2 перше завдання має виводити таку
послідовність:
2
6
4
7
9
Алгоритм розв’язання:
Код програми:
І. Завдання 1
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct node
{
int data;
struct node *leftson, *rightson;
}
*binary_tree;
void Init(binary_tree *root_ptr);
int Empty(binary_tree root);
binary_tree WhoRight(binary_tree tree_node);
void PutLeftLeft(binary_tree tree_node);
binary_tree Who(binary_tree root, int new_data);
void PutRight(binary_tree root, int new_data);
binary_tree Find(binary_tree root, int search_data);
int GoStraight(binary_tree root,int k,int z);
void GoSymmetric(binary_tree root);
void GoReverse(binary_tree root);
int Compare(binary_tree root1,binary_tree root2);
binary_tree WhoFather(binary_tree root, binary_tree knot);
binary_tree WhoBrother(binary_tree root, binary_tree knot);
void AddSearchTree(binary_tree *root_ptr, int new_data);
void DeleteSearchTree(binary_tree *root_ptr, int del_data);
void PrintLevel(binary_tree root, int k, int i);
void PrintTurningTree(binary_tree root, int h);
int kil=0;
int mas1[100],i=0;
void main()
{
int z,k=0;
double ser=0;
binary_tree t1,p ;
int x;
unsigned i,n;
Init(&t1);
printf("Enter the number of knots of binary tree 1: ");
scanf("%d",&n);
for (i=1;i<=n;i++)
{
scanf("%d",&x);
AddSearchTree(&t1, x);
};
printf("\n");
kil=0;
k=GoStraight(t1,k,0); //kilkist vyzliv pru priamomy prohodgenni
printf("\nkilkist vyzliv=%d",kil);
printf("\n");
kil=0;
GoSymmetric(t1); //kilkist vyzliv z 1 nashcadkom pru symetru4nomy
z=kil;
printf("\nkilkist vyzliv z 1 nashcadkom=%d",z);
printf("\n");
kil=0; i=0;
GoReverse(t1); //kilkist lustkiv pru zvorotniomy
z=kil;
printf("\nkilkist lustkiv=%d",z);
printf("\n");
for(k=0;k<z;k++)
ser+=mas1[k];
ser/=z;
printf("seredne znachenna lustkiv = %.2lf\n",ser);
PrintLevel(t1,20,1);
printf("\n");
getch();
return;
}
void Init(binary_tree *root_ptr)
{
*root_ptr = NULL;
}
int Empty(binary_tree root)
{
return root == NULL;
}binary_tree WhoLeft(binary_tree tree_node)
{
if (tree_node)
return tree_node->leftson;
else
return tree_node;
}
binary_tree WhoRight(binary_tree tree_node)
{
if (tree_node)
return tree_node->rightson;
else
return tree_node;
}
binary_tree MakeNode(int new_data)
{
binary_tree new_node;
new_node =(struct node*) malloc(sizeof(struct node));
new_node->data = new_data;
new_node->leftson = new_node->rightson = NULL;
return new_node;
}
void PutLeft(binary_tree tree_node, int new_data)
{
binary_tree new_node;
new_node = MakeNode(new_data);
tree_node->leftson = new_node;
}
void PutRight(binary_tree tree_node, int new_data)
{
binary_tree new_node;
new_node = MakeNode(new_data);
tree_node->rightson = new_node;
}
void F(binary_tree root, int search_data, binary_tree *search_node_ptr)
{
if (root && !*search_node_ptr)
if (root->data == search_data)
*search_node_ptr = root;
else
{
F(WhoLeft(root), search_data, search_node_ptr);
F(WhoRight(root), search_data, search_node_ptr);
};
}
binary_tree Find(binary_tree root, int search_data)
{
binary_tree search_node = NULL;
F(root, search_data, &search_node);
return search_node;
}
int GoStraight(binary_tree root,int k,int z)
{
if (root)
{
k++;
printf(" %d", root->data);
kil++;
z=2;
k=GoStraight(WhoLeft(root),k,z);
z=1;
k=GoStraight(WhoRight(root),k,z);
k++;
}
else {
k=k-z;
}
return k;
}
void GoSymmetric(binary_tree root)
{
if (root)
{
GoSymmetric(WhoLeft(root));
printf(" %d", root->data);
if(root->leftson !=NULL && root->rightson == NULL || root->leftson ==NULL && root->rightson != NULL)
kil++;
GoSymmetric(WhoRight(root));
};
}
void GoReverse(binary_tree root)
{
if (root)
{
GoReverse(WhoLeft(root));
GoReverse(WhoRight(root));
printf(" %d", root->data);
if(root->leftson ==NULL && root->rightson == NULL){
kil++;
mas1[i]=root->data;
i++;
}
};
}
void WhoF(binary_tree root, binary_tree tree_node, binary_tree *father)
{
if (root && !*father)
{
if (WhoLeft(root) == tree_node || WhoRight(root) == tree_node)
*father = root;
else
{
WhoF(WhoLeft(root), tree_node, father);
WhoF(WhoRight(root), tree_node, father);
};
};
}
binary_tree WhoFather(binary_tree root, binary_tree tree_node)
{
binary_tree father = NULL;
if (root != father)
WhoF(root, tree_node, &father);
return father;
}
binary_tree WhoBrother(binary_tree root, binary_tree tree_node)
{
if (WhoLeft(WhoFather(root, tree_node)) == tree_node)
return WhoRight(WhoFather(root, tree_node));
else
return WhoLeft(WhoFather(root, tree_node));
}
void AddSearchTree(binary_tree *root_ptr, int new_data)
{
if (!*root_ptr)
*root_ptr = MakeNode(new_data);
else
if (new_data < (*root_ptr)->data)
AddSearchTree(&((*root_ptr)->leftson), new_data);
else
AddSearchTree(&((*root_ptr)->rightson), new_data);
}
void Del(binary_tree *root_ptr, binary_tree *del_node_ptr)
{
if (WhoLeft(*root_ptr))
Del(&((*root_ptr)->leftson), del_node_ptr);
else
{
(*del_node_ptr)->data = (*root_ptr)->data;
*del_node_ptr = *root_ptr;
*root_ptr = WhoRight(*root_ptr);
};
}
void DeleteSearchTree(binary_tree *root_ptr, int del_data)
{
binary_tree del_node;
if (*root_ptr)
if (del_data < (*root_ptr)->data)
DeleteSearchTree(&((*root_ptr)->leftson), del_data);
else
if (del_data > (*root_ptr)->data)
DeleteSearchTree(&((*root_ptr)->rightson), del_data);
else
{
del_node = *root_ptr;
if (!del_node->rightson)
*root_ptr = WhoLeft(del_node);
else
if (!WhoLeft(del_node))
*root_ptr = WhoRight(del_node);
else Del(&del_node->rightson, &del_node);
free(del_node);
};
}
void PrintLevel(binary_tree root, int k, int i)
{
char c;
if (root)
{
printf("\n");
for(c=1;c<=40+i;c++) printf(" ");
printf(" %d",root->data);
PrintLevel(WhoLeft(root),k/2,i-k);
PrintLevel(WhoRight(root),k/2,i+k);
};
return;
}
void PrintTurningTree(binary_tree root, int h)
{
int i;
if (root)
{
PrintTurningTree(WhoRight(root),h+1);
for (i=1;i<=h;i++) printf(" ");
printf(" %d\n",root->data);
PrintTurningTree(WhoLeft(root),h+1);
};
}
ІІ. Завдання 2
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;//показує якою підвіткою попорядку є дана вітка
};
DosHierarchy.h
#include"Tree.h"
//enum UnitType{FILE = 0, FOLDER};
//class DosUnit : public Node
//{
// DosUnit(
//}
class DosHierarchy// клас, який моделює ієрархію представлення даних в ОС типу DOS за допомогою АТД "Дерево"
{
public:
DosHierarchy(int MaxFoldersNum)
{
if(MaxFoldersNum > 0)
this->DosTree = new Tree("Root Folder", MaxFoldersNum);
else
this->DosTree = new Tree("Root Folder",10000);
this->TotalFolder = DosTree->GetRoot();
}
void ReturnToRootFolder()// робить корневий каталог поточним
{
this->TotalFolder = this->DosTree->GetRoot();
}
void ReturnToPreviousFolder()//робить каталогом, для якого даний каталог є підкаталогом, поточним
{
this->TotalFolder = this->TotalFolder->GetParent();
}
bool CreateFolder(char* FolderName)//створює каталог в поточному каталозі
{
int i = 0;
for(; i <this->TotalFolder->GetSubNodesNum(); i++)
{
if(!strcmp((*this->TotalFolder)[i]->GetData(), FolderName))
{
return false;
}
}
this->TotalFolder->AddSubNode(FolderName);
return true;
}
bool CreateFile(char* FileName)//створює файл в поточному каталозі
{
int i = 0;
for(; i <this->TotalFolder->GetSubNodesNum(); i++)
{
if(!strcmp((*this->TotalFolder)[i]->GetData(), FileName))
{
return false;
}
}
this->TotalFolder->AddSubNode(FileName);
return true;
}
bool EnterFolder(char* FolderName)//робить вибраний каталог поточним, якщо він існує, інакше повертає false
{
int i = 0;
for(; i <this->TotalFolder->GetSubNodesNum(); i++)
{
if(!strcmp((*this->TotalFolder)[i]->GetData(), FolderName))
{
break;
}
}
if(i == this->TotalFolder->GetSubNodesNum())
{
return false;
}
else
{
this->TotalFolder = (*this->TotalFolder)[i];
return true;
}
}
void PrintSortedFolderInfo()
{
int Length = this->TotalFolder->GetSubNodesNum();
char** Names = new char*[Length];
for(int i = 0; i < Length;i++)
{
Names[i] = new char[strlen((*this->TotalFolder)[i]->GetData()) + 1];
strcpy(Names[i], (*this->TotalFolder)[i]->GetData());
}
this->sort(Names, Length);
for(int i = 0; i < Length;i++)
cout << Names[i] << endl;
}
void PrintAllFolderElementsInfo()//виводить всі файли і каталоги в поточному каталозі
{
this->PrintFolderAllInfo(this->TotalFolder);
return;
}
void PrintAllSubFlodersInfo()//виводить список всіх каталогів у поточному каталозі
{
this->PrintOnlyFoldersInfo(this->TotalFolder);
return;
}
void PrintAllFilesInfo()//виводить список всіх файлів у поточному каталозі
{
this->PrintOnlyFilesInfo(this->TotalFolder);
return;
}
private:
void PrintFolderAllInfo(Node* _TotalFolder)//рекурсивна функція, яка буде входити в підкаталоги поки незустріне каталог без підкаталогів
{
for(int i = 0; i < _TotalFolder->GetSubNodesNum(); i++)
{
if((*_TotalFolder)[i]->GetSubNodesNum() > 0)
{
cout << (*_TotalFolder)[i]->GetData() <<"->"<< endl;
PrintFolderAllInfo((*_TotalFolder)[i]);
}
else
{
cout <<'\t'<<"File:"<< (*_TotalFolder)[i]->GetData() << endl;
}
}
return;
}
void PrintOnlyFoldersInfo(Node* _TotalFolder)
{
cout << _TotalFolder->GetData() << endl;
cout <<"Folders:"<< endl;
for(int i = 0; i < _TotalFolder->GetSubNodesNum(); i++)
{
if((*TotalFolder)[i]->GetSubNodesNum() > 0)
{
PrintOnlyFoldersInfo((*_TotalFolder)[i]);
}
}
return;
}
void PrintOnlyFilesInfo(Node* _TotalFolder)
{
cout <<"Files:"<< endl;
for(int i = 0; i < _TotalFolder->GetSubNodesNum(); i++)
{
if((*_TotalFolder)[i]->GetSubNodesNum() == 0)
{
(*_TotalFolder)[i]->GetData();
}
}
return;
}
void sort(char** arr, int len)
{
bool end = false;
while(!end)
{
end = true;
for(int i = 0; i < len - 1; i++)
{
if(strcmp(arr[i],arr[i+1]) > 0)
{
char* t = arr[i];
arr[i] = arr[i+1];
arr[i+1] = t;
end = false;
}
}
}
return;
}
Tree* DosTree;//дерево представлення даних
Node* TotalFolder;
};
Main.cpp
#include"Tree.h"
#include"DosHierarchy.h"
void main()
{
DosHierarchy* DH = new DosHierarchy(1000);
DH->CreateFolder("Music");// створюю папку music та наповнюю її каталогами з назвами груп, альбомів та файлами
DH->EnterFolder("Music");
DH->CreateFolder("Queen");
DH->CreateFolder("AC/DC");
DH->EnterFolder("Queen");
DH->CreateFolder("A night at the Opera album - 1975");
DH->EnterFolder("A night at the Opera album - 1975");
DH->CreateFile("Bohemian Rhapsody.mp3");
DH->CreateFile("Love of my life.mp3");
DH->ReturnToRootFolder();
DH->EnterFolder("Music");
DH->EnterFolder("AC/DC");
DH->CreateFolder("Back in black album - 1980");
DH->EnterFolder("Back in black album - 1980");
DH->CreateFile("Hells bells.mp3");
DH->CreateFile("Back in black.mp3");
DH->ReturnToRootFolder();//повертаюся в корневий каталог та створюю каталог study додаючи в неї декілька файлів
DH->CreateFolder("Study");
DH->EnterFolder("Study");
DH->CreateFolder("Programming");
DH->EnterFolder("Programming");
DH->CreateFile("Project1.exe");
DH->CreateFile("Project2.exe");
DH->ReturnToRootFolder();//повертаюся в корневий каталог та створюю каталог photo додаючивнеїдекількафайлів
DH->CreateFolder("Photo");
DH->EnterFolder("Photo");
DH->CreateFolder("AlushtaPhotos");
DH->EnterFolder("AlushtaPhotos");
DH->CreateFile("Photo1");
DH->CreateFile("Photo2");
DH->CreateFile("Photo3");
DH->CreateFile("Photo4");
DH->CreateFile("Photo5");
DH->ReturnToRootFolder();
DH->EnterFolder("Music");
DH->PrintAllFolderElementsInfo();//виводжу всі файли з каталогу "music"
DH->ReturnToRootFolder();
DH->EnterFolder("Study");
DH->PrintAllFolderElementsInfo();//виводжувсі "вкладені" каталогитафайливкаталозі "study"
DH->ReturnToRootFolder();
DH->PrintSortedFolderInfo();//виводжу всі каталоги з корневого каталогу у порядку сортування
}
Результат виконання програми:
/
Рис.1. Ескіз вікна з результатом виконання програми Завдання 1
/
Рис.2. Ескіз вікна з результатом виконання програми Завдання 2
Висновок: закріпив теоретичні знання та оволодів практичними навиками опрацювання структур даних “Бінарне дерево пошуку”. Засвоїв техніку створення та опрацювання складних типів даних.
14.04.2015 19:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора