Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Динамічні структури даних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Курсова робота
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
Національний університет “Львівська політехніка”
Кафедра ЕОМ
Курсова робота ( частина 2 )
На тему:
“ Динамічні структури даних ”
з дисципліни:
" Програмування"
Вибір варіантів індивідуального завдання:
Вибір АТД: № Варіанту = (2 + 1994 + 111) % 4 + 1 = 4.
Примітка: 1 – стек, 2 – черга, 3- список, 4 – дерево.
Вибір номера завдання: № Варіанту = 2
Зміст
2. Завдання 2: Динамічні структури даних 3
2.1. Теоретична частина 3
2.2. Частина 1. Побудова АТД 4
2.2.1. Постановка задачі 4
2.2.2. Динаміка вмісту 4
2.2.3. Результати виконання програми 5
2.3. Частина 2. Застосування АТД 6
2.3.1. Постановка задачі 6
2.3.2. Алгоритм розв’язання задачі 6
2.3.3. Результати виконання програми 7
Висновки 8
Список літератури 9
Додатки 10
2. Завдання 2: Динамічні структури даних
2.1 Теоретична частина
Переваги динамічних структур даних
Динамічні структури даних щодо визначення характеризуються відсутністю фізичної суміжності елементів структури пам'яті непостійністю і непередбачуваністю розміру (числа елементов4) структури в процесі її обробки. У цьому розділі розглянуто особливості динамічних структур, що визначаються їх першим характерним властивістю.
Оскільки елементи динамічної структури розташовуються по непередбачуваним адресами пам'яті, адреса елемента такої структури не може бути обчислений з адреси початкового або попереднього елемента. Для встановлення зв'язку між елементами динамічної структури використовуються покажчики, через які встановлюються явні зв'язки між елементами. Таке подання даних у пам'яті називається зв'язковим.
Елемент динамічної структури складається з двох полів:
інформаційного поля або поля даних, в якому містяться ті дані, заради яких і створюється структура; в загальному випадку інформаційне поле саме є інтегрованою структурою-вектором, масивом, записом і т.п.;
полі зв'язок, в якому містяться один або кілька покажчиків, що зв'язує цей елемент з іншими елементами структури.
Коли зв'язне подання даних використовується для розв'язання прикладної задачі, для кінцевого користувача дивись робиться тільки вміст інформаційного поля, а поле зв'язок використовується тільки програмістом-розробником.
Переваги зв'язкового представлення даних:
у можливості забезпечення значної мінливості структур;
розмір структури обмежується тільки розміром пам'яті машини;
при зміні логічної послідовності елементів структури потрібно не переміщення даних в пам'яті, а тільки корекція покажчиків.
Однак існують і недоліки:
робота з покажчиками вимагає, як правило, більш високої кваліфікації від програміста;
на поля зв'язок витрачається додаткова пам'ять;
доступ до елементів зв'язного структури може бути менш ефективним за часом.
Застосування динамічних структур
Останній недолік є найбільш серйозним і саме їм обмежується застосовність зв'язкового представлення даних. Якщо в суміжному поданні даних для обчислення адреси будь-якого елемента нам у всіх випадках достатньо було номера елемента або інформації, що міститься в дескрипторі структури, то для зв'язкового подання адресу елемента не може бути обчислений з вихідних даних.
Дескриптор зв'язного структури містить один або кілька покажчиків, що дозволяють увійти в структуру, далі пошук і необхідного елемента виконується проходженням по ланцюжку покажчиків від елемента до елементу. Тому зв'язне уявлення практично ніколи не застосовується в задачах, де логічна структура даних має вигляд вектора або масиву - з доступом за номером елемента, але часто застосовується в задачах, де логічна структура вимагає іншої вихідної інформації доступу (таблиці, стеки, списки, дерева і т . д.).
Дерево - в інформатиці та програмуванні одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з одного або більше вузлів (nodes), яка задовольняє наступним вимогам:
існує один відокремлений вузол - корень (root) дерева
інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T1, ..., Tm і кожна з цих множин в свою чергу є деревом. Дерева T1, ..., Tm мають назву піддерев (subtrees) даного кореня.
З цього визначення випливає, що кожний вузлів є в свою чергу коренем деякого піддерева. Кількість піддерев вузла має назву степеня (degree) цього вузла. Вузол степеню нуль називається кінцевим (terminal) або листком (leaf). Не корінь і некінцевий вузол також має назву вершини розгалуження (branch node). Нехай x - довільний вузол дерева з коренем r. Тоді існує єдиний шлях з r до x. Усі вузли на цьому шляху називаються предками (ancestors) x; якщо деякий вузол y є предком x, то x називається нащадком (descendant) y.
2.2. Частина 1. Побудова АТД
2.2.1. Постановка задачі
Змоделювати дерево, яке використати в другій частині цього завдання. Переписати основні операції роботи з деревом і продемонструвати їх застосування при додаванні вузлів в дерево та вилученні вузлів з дерева.
Динаміка вмісту дерева
CreateSubNode(“Node1”);
/
CreateSubNode(“Node2”);
/
CreateSubNode(“Node3”);
/
CreateSubNode(“Node4”);
/
DeleteSubNode(2);
/
2.2.3. Результати виконання програми
/
2.3.1. Постановка задачі
4.1. Операційні системи типу UNIX, PC-DOS (старші версії) підтримують деревоподібну структуру збереження даних на диску. При цьому мінімальна іменована одиниця інформації називається файлом. Файли об'єднуються в каталоги, кожний з яких теж має ім'я. Множина каталогів і окремих файлів можуть у свою чергу також утворити каталог більш високого рівня. Каталог найвищого рівня називається кореневим. Кількість рівнів вкладеності не обмежена. Розглядати тільки випадки без порожніх каталогів (тобто каталогів, що не мають файлів).
Скласти програму для виводу на екран по рівнях:
а) списку всіх елементів даних, "вкладених" у довільний каталог на всіх рівнях;
б) списку всіх каталогів, "вкладених" у довільний каталог;
в) списку всіх файлів, "вкладених" у довільний каталог;
г) списку всіх елементів даних кореневого каталогу, виведених в алфавітному порядку.
2.3.2. Алгоритм розв’язання задачі
Створюю клас DosHierarchy в якому є об’єкт типу «дерево». Вітка дерева без підвіток – файл, вітка з підвітками –каталог. В класі реалізовано методи для створення та видалення каталогів та файлів. А також методи, які виводять інформацію згідно з завданням.
2.3.3. Результати виконання програми
/
Висновки
Створено програму, яка моделює ієрархію збереження даних у операційних системах типу DOS за допомгою АТД «Дерево». Реалізовано всі необхідні методи та методи, які задані завданням.
Список літератури
Грегори К. Использование Visual С++. Специальное издание. - М.: «Диалектика», 1999.
Мешков А.В., Тихомиров Ю.В. Visual С++ и MFC. Пер. с англ. – 2-е изд. перераб. и доп. – СПб.: БХВ - Петербург, 2002. – 1040 с.
Страуструп Б. Язык программирования С++. Третье издание. - М.: «Издательство Бином», 1999.
Трамбле Ж., Соренсон П. Введение в структуры данных. – М.:Машиностроение, 1982
Уильям Топп, Уильям Форд. Структуры данных в С++. – М.:Бином, 2000 - 700 с
Додатки
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();
}
Tree.h(Курсова, частина 2)
#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(Курсова, частина 2)
#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(Курсова, частина 2)
#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();//повертаюся в корневий каталог та створюю каталог study додаючи в неї декілька файлів
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();//виводжу всі файли з каталогу "study"
DH->ReturnToRootFolder();
DH->EnterFolder("Study");
DH->PrintAllFolderElementsInfo();//виводжу всі "вкладені" каталоги та файли в каталозі "music"
DH->ReturnToRootFolder();
DH->PrintSortedFolderInfo();//виводжу всі каталоги з корневого каталогу у порядку сортування
}
25.01.2013 15:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора