Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Динамічні структури даних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2014
Тип роботи:
Розрахунково - графічна робота
Предмет:
Обчислювальний практикум
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
Розрахунково-графічна робота
на тему: "Динамічні структури даних"
з дисципліни: "Обчислювальний практикум"
№ варіанта – 1
Зміст
1 Теоретична частина 4
1.1 Стек 4
1.2 Черга 5
1.3 Список 6
1.4 Дерево 6
2 Реалізація АТД 7
2.1 Стек 7
2.1.1 Текст програми 7
2.1.2 Результати виконання програми 8
2.2 Черга 9
2.2.1 Текст програми: 9
2.2.2 Результати виконання програми 10
2.3 Список 10
2.3.1 Текст програми: 10
2.3.2 Результати виконання програми 13
2.4 Дерево 13
2.4.1 Текст програми: 13
2.4.2 Результати виконання програми 17
3 Завдання 4. Застосування АТД 18
3.1 Застосування АТД "СТЕК" до розв’язання прикладної задачі 18
3.1.1 Опис алгоритму вирішення задачі 18
3.1.2 Аналіз алгоритму 18
3.1.3 Результат виконання програми 19
3.2 Застосування АТД " ЧЕРГА " до розв’язання прикладних задач 20
3.2.1 Опис алгоритму вирішення задачі 20
3.2.2 Аналіз алгоритму 20
3.2.3 Результат виконання програми 21
3.3 Застосування АТД " СПИСОК " до розв’язання прикладних задач 22
3.3.1 Опис алгоритму вирішення задачі 22
3.3.2 Аналіз алгоритму 22
3.3.3 Результат виконання програми 23
3.4 Застосування АТД " ДЕРЕВО " до розв’язання прикладних задач 24
3.4.1 Опис алгоритму вирішення задачі 24
3.4.2 Аналіз алгоритму 25
3.4.3 Результат виконання програми 25
4 Висновки 26
5 Список літератури 27
Додаток А 28
Додаток Б 31
Додаток В 32
Додаток Д 34
Теоретична частина
Абстрактний тип даних
Абстрактний тип даних (АТД) - це тип даних, який надає для роботи з елементами цього типу певний набір функцій, а також можливість створювати елементи цього типу за допомогою спеціальних функцій. Вся внутрішня структура такого типу захована від розробника програмного забезпечення - в цьому і полягає суть абстракції. Абстрактний тип даних визначає набір функцій, незалежних від конкретної реалізації типу, для оперування його значеннями. Конкретні реалізації АТД називаються структурами даних.
В програмуванні абстрактні типи даних звичайно представляються у вигляді інтерфейсів, які приховують відповідні реалізації типів. Програмісти працюють з абстрактними типами даних виключно через їх інтерфейси, оскільки реалізація може в майбутньому змінитися. Такий підхід відповідає принципу інкапсуляції в об'єктно-орієнтованому програмуванні. Сильною стороною цієї методики є саме приховування реалізації. Раз зовні опублікований тільки інтерфейс, то поки структура даних підтримує цей інтерфейс, всі програми, що працюють із заданою структурою абстрактним типом даних, будуть продовжувати працювати. Розробники структур даних стараються, не змінюючи зовнішнього інтерфейсу і семантики функцій, поступово допрацьовувати реалізації, покращуючи алгоритми по швидкості, надійності і використовуваної пам'яті.
Різниця між абстрактними типами даних і структурами даних, які реалізують абстрактні типи, мож
на пояснити на наступному прикладі. Абстрактний тип даних список може бути реалізований за допомогою масиву або лінійного списку, з використанням різних методів динамічного виділення пам'яті. Однак кожна реалізація визначає один і той же набір функцій, який повинен працювати однаково (по результату, а не по швидкості) для всіх реалізацій.
Абстрактні типи даних дозволяють досягти модульності програмних продуктів і мати кілька альтернативних взаємозамінних реалізацій окремого модуля.
Стек
Стек в інформатиці та програмуванні — різновид лінійного списку, структура даних, яка працює за принципом (дисципліною) «останнім прийшов — першим пішов» (LIFO, англ. last in, first out). Всі операції (наприклад, видалення елементу) в стеку можна проводити тільки з одним елементом, який знаходиться на верхівці стеку та був введений в стек останнім.
Стек можна розглядати як певну аналогію до стопки тарілок, з якої можна взяти верхню, і на яку можна покласти верхню тарілку (інша назва стеку — «магазин», за аналогією з принципом роботи магазину в автоматичній зброї)
Операції зі стеком
Виконання операції push
push ("заштовхнути елемент"): елемент додається в стек та розміщується в його верхівці. Розмір стеку збільшується на одиницю. При перевищенні розміру стека граничної величини, відбувається переповнення стека (англ. stack overflow)
pop ("виштовхнути елемент"): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні "виштовхнути" елемент з вже пустого стеку, відбувається ситуація "незаповнення" стеку (англ. stack underflow)
Кожна з цих операцій зі стеком виконується за фіксований час O(1) і не залежить від розміру стеку.
Додаткові операції (присутні не у всіх реалізаціях стеку):
isEmpty: перевірка наявності елементів в стеку; результат: істина (true), коли стек порожній.
isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе.
clear: звільнити стек (видалити усі елементи).
top: отримати верхній елемент (без виштовхування).
size: отримати розмір (кількість елементів) стека.
swap: поміняти два верхніх елементи місцями.
Організація в пам'яті комп'ютера
Стек може бути організований як масив або множина комірок в певній області комп'ютера з додатковим зберіганням ще й вказівника на верхівку стека. Заштовхування першого елемента в стек збільшує адресу вказівника, виштовхування елементу зменшує її. Таким чином, адреса вказівника завжди відповідає комірці масиву, в якій зараз знаходиться верхівка стеку.
Багато процесорів ЕОМ мають спеціалізовані регістри, які використовуються як вказівники на верхівку стеку, або використовують деякі з регістрів загального вжитку для цієї спеціальної функції в певних режимах адресації пам'яті.
Черга
Чергою FІFO (Fіrst - Іn - Fіrst- Out - "першим прийшов - першим вийшов") називається така послідовність зі змінною довжиною, у якій додавання елементів виконується тільки з однієї сторони (цю сторону часто називають кінцем або хвостом черги), а вилучення - з іншої сторони (називають початком або головою черги). Ті самі черги до прилавків і до кас, які ми так не любимо, є типовим побутовим прикладом черги FІFO.
Основні операції над чергою - ті ж, що й над стеком - додавання, вилучення, визначення розміру, читання, що не руйнує чергу.
Дек - особливий вид черги. Дек (від англ. deq - double ended queue, тобто черга із двома кінцями) - це така послідовність, у якій як додавання, так і вилучення елементів може здійснюватися з кожного із двох кінців. Окремі випадки дека - дек з обмеженим входом і дек з обмеженим виходом. Логічна й фізична структури дека аналогічні логічній і фізичній структурі кільцевої FіFO-черги. Однак, стосовно до дека доцільно говорити не про початок і кінець, а про лівий і правий кінці. Динамічна реалізація дека є об'єднанням стека і черги.
Основні операції над деком:
додавання элемента справа;
додавання элемента слева;
вилучення элемента справа;
вилучення элемента слева;
Задачі, що вимагають використання структури дека, зустрічаються в обчислювальній техніці і програмуванні набагато рідше, ніж завдання, реалізовані на структурі стека або черги. Як правило, вся організація дека виконується програмістом без яких-небудь спеціальних засобів системної підтримки.
Прикладом дека може бути, наприклад, якийсь термінал, у який вводяться команди, кожна з яких виконується якийсь час. Якщо ввести наступну команду, не дочекавшись, поки закінчиться виконання попередньої, то вона встане в чергу й почне виконуватися, як тільки звільниться термінал. Це FІFO-черга. Якщо ж додатково ввести операцію скасування останньої введеної команди, то отримаємо дек.
Список
Лінійний список – це скінчена послідовність однотипних елементів (вузлів), можливо, з повтореннями. Список розташовується в пам'яті довільним чином. Кожний вузол однонаправленого лінійного зв'язаного списку містить вказівник на наступний вузол списку, що дозволяє переміщуватись вперед по списку. Кожний вузол двонаправленого лінійного зв'язаного списку містить вказівники на попередній і наступний вузли списку, що дозволяє переміщуватись по списку вперед та назад.
Вставка і вилучення вузлів у списку реалізовані ефективно: змінюються тільки вказівники. З іншого боку, довільний доступ до вузлів списку підтримується погано: щоб прийти до певного вузла списку, треба відвідати всі попередні вузли. Крім того, на відміну від стеків або черг, додатково витрачається пам'ять під один або два вказівники на кожний елемент списку.
Список росте дуже просто: додавання кожного нового елемента приводить до того, що вказівники на попередній і наступний вузли списку, між якими вставляється новий вузол, міняють свої значення. У новому елементі таким вказівникам присвоюється значення адрес сусідніх елементів.
Список використовує тільки такий об'єм пам'яті, який потрібний для наявної кількості елементів.
Дерево
Деревом називається множина взаємно-зв’язаних елементів які називаються вузлами розташованих по рівнях. Бінарне дерево- це скінченна множина вузлів кожен з яких або порожній, або складається з кореня пов’язаного з двома різними бінарними деревами які називається лівим і правим піддеревом.
Двійкове (або Бінарне) дéрево пóшуку (англ. 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. Оформити АТД у вигляді класа. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів з АТД.
Такі структури даних як Стек і Черга я реалізував за допомогою масивів.
Натомість такі структури як Список та Дерево я реалізував за допомогою зв’язаних вузлів, які більш доцільніші в даних випадках.
Стек
Текст програми:
#include <iostream>
using namespace std;
///////////////////////////////////////////////////////////
class stack
{
private:
int top;
int s[15];
public:
stack(): top(0)
{}
int push(int var);
int pop(int var);
bool empty() const;
};
int stack::push(int var)
{
top++;
s[top] = var;
return var;
}
int stack::pop(int var)
{
//int var = s[top];
top --;
return var;
}
bool stack::empty() const
{
return top==0;
}
///////////////////////////////////////////////////////////
int main ( )
{
long arr[15];
int count=-1;
int a;
stack s1;
int i=0;
while(i!=3)
{
cout <<"For addition Data enter 1, for deleting Data enter 2, For exit enter 3"<<endl;
cin>>i;
if (i==1)
{
cout<<"Enter data -\t";
cin>>a;
s1.push(a);
count++; arr[count]=a;
}
if(i==2)
{
if
(s1.empty())
cout<<"NUll."<<endl;
else
{
s1.pop(a);
count--;
cout<<"number "<<a<<" delete from stack."<<endl;
}
}
if(i==3)
{
getchar();
cout <<"Good luck:)\n";
}
cout<<"Stack contains:\n";
for(int i=count;i>=0;i--)
cout<<arr[i]<<"\t";
cout<<endl;
}
return 0;
}
Результати виконання програми:
Рис.2.1.1. Ескіз вікна з результатом виконання програми АТД «Стек»
Черга
Текст програми:
#include <iostream>
#define maxn 1000
using namespace std;
typedef struct
{
int h,t;
int val[maxn];
} deque;
void push_front(deque *d, int x)
{
if (d->h<1) d->h +=maxn; //щоб вказівники не були відємними
d->val[(--d->h)%maxn]=x;
}
void push_back(deque *d,int x)
{
d->val[(d->t++)%maxn]=x;
}
int pop_front(deque *d)
{
return d->val[(d->h++)%maxn];
}
int pop_back(deque *d)
{
if (d->t<1) d->t +=maxn;
return d->val[(--d->t)%maxn];
}
int main()
{
deque a;
int dlen;
if (a.t>a.h) dlen=(a.t-a.h)%maxn;
else dlen=maxn-(a.h-a.t)%maxn;
a.t=0;
a.h=0;
push_back(&a,3);
push_back(&a,1);
push_back(&a,2);
push_back(&a,3);
push_back(&a,4);
push_back(&a,6);
push_back(&a,7);
while (a.h !=a.t-3)
{
std::cout<<pop_front(&a)<<endl;
}
std::cout<<"etap 2"<<endl;
if (a.h==a.t) std::cout<<"finita"<<endl;
else //перевірка роботи
{
while (a.h !=a.t)
{
std::cout<<pop_front(&a)<<std::endl;
}
}
if (a.h==a.t) std::cout<<"finita"<<endl;
return 0;
}
Результати виконання програми:
Рис.2.2.1. Ескіз вікна з результатом виконання програми АТД «Черга»
Список
Текст програми:
//List.cpp
#include <iostream>
#include "list.h"
using namespace std;
void list::push_back(int el)
{
node* p,*p1;
p = head;
while(p->next != NULL)
{p = p->next;}
p1 = new (node);
p1->data = el;
p1->next = NULL;
p1->prev = p;
p->next = p1;
}
void list::print()
{
node* p;
p = head->next;
while(p != NULL)
{
cout<<(p->data)<<" ";
p = p->next;
}
}
void list::push_front(int el)
{
node* p;
p = new (node);
p->data = el;
if(head->next == NULL)
{
p->next = head->next;
head->next = p;
p->prev = head;
}
else
{
p->next = head->next;
head->next->prev = p;
head->next = p;
p->prev = head;
}
}
void list::destroy()
{
node* p,* p1;
p = head;
p1 = p->next;
while(p1 != NULL)
{
p = p1;
p1 = p1->next;
delete p;
}
}
void list::pop_back()
{
node* p,* p1;
p = head;
p1 = p->next;
while(p1->next != NULL)
{
p = p1;
p1 = p1->next;
}
p->next = NULL;
delete p1;
}
void list::pop_front()
{
node* p;
p = head->next;
head->next = p->next;
p->next->prev = head;
delete p;
}
//list.h
#ifndef list_h
#define list_h
class list
{
public:
list(){head = new (node); head->next = NULL;}
~list(){destroy(); delete head;}
void push_back(int);
void push_front(int);
void pop_back();
void pop_front();
void print();
void destroy();
private:
struct node
{
int data;
node* next;
node* prev;
};
node* head;
};
//main.cpp
#include <iostream>
#include "list.h"
using namespace std;
int main()
{
{
list L;
for(int i=0;i<10;++i)
{cin>>i;
L.push_back(i);
}
L.print();
}
system("pause>0");
return 0;
}
Результати виконання програми:
Рис.2.3.1. Ескіз вікна з результатом виконання програми АТД «Список»
Дерево
Текст програми:
//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();
}
Результати виконання програми:
Рис.2.3.4. Ескіз вікна з результатом виконання програми АТД «Дерево»
Завдання 4. Застосування АТД
Застосування АТД "СТЕК" до розв’язання прикладної задачі
Перетворити вираз з інфіксної форми запису в префіксну.
Вказівки до розв’язання задачі: При перетворенні інфіксний рядок зчитуйте справа наліво і префіксний рядок створюйте також справа наліво. В стеку зберігати операції з однаковим пріоритетом.
Опис алгоритму вирішення задачі
Рис.3.1.1. Блок- схема алгоритму АТД «Стек»
Аналіз алгоритму
Текст програми наведений в додатку А.
В даній програмі потрібно перетворити вираз з інфіксної в префіксну форму. Спершу вводиться інфіксна форма виразу, потім відбувається зчитування інформації посимвольно з введеного виразу. Відбувається розстановка пріоритетів змінним в залежності від їхнього положення в виразі, наявності дужок, та математичних символів операцій за правилами математики. Далі відбувається створення нового блоку даних в якому зберігається кінцевий результат. Кінцевий результат виводится на екран.
Результат виконання програми
Рис.3.1.2. Ескіз вікна з результатом виконання програми АТД «Стек»
Застосування АТД " ЧЕРГА " до розв’язання прикладних задач
1. У магазині стоїть черга з m покупців. Час обслуговування покупця з черги – це випадкове ціле число в діапазоні від 1 до t1. Час додавання нового покупця до черги - це випадкове ціле число в діапазоні від 1 до t2.
Промоделювати стан черги:
а) вивести повідомлення про час виникнення подій ( обслуговування та додавання покупця ) за період часу T (T >> t1, T >> t2);
б) показати залишок черги;
в) розв’язати задачу, передбачивши, що через випадковий час від 1 до t3 до початку черги додається „пільговий” покупець, який обслуговується першим, а через випадковий час від 1 до t4 не витримує та йде з черги останній покупець.
Опис алгоритму вирішення задачі
Рис.3.2.1. Блок- схема алгоритму АТД «Черга»
Аналіз алгоритму
Текст програми наведений в додатку Б.
В завданні потрібно промоделювати стан черги в магазині яка обслуговує покупці. Спершу потрібно ввести всі дані необхідні для емуляції черги, такі як: час емуляції, середня кількість покупців за певний час, початкова кількість покупців і тд. Далі відбувається створення двовхідної черги для забезпечення емуляції віп покупців. Далі, випадково, відбувається надходження покупців, обслуження покупців, вихід покупців з черги, надходження віп покупців. Вся динаміка черги відповідно відображається на екрані, де вона виводится.
Результат виконання програми
Рис.3.2.2. Ескіз вікна з результатом виконання програми АТД «Черга»
Застосування АТД " СПИСОК " до розв’язання прикладних задач
1. Многочлен виду , де представити у вигляді зв’язаного списку в якому кожний вузол має три поля: одне – для коефіцієнта Сi , друге – для показника степеня ni , третє – для вказівника на наступний вузол списку. Для описаного представлення многочленів програмно реалізувати таку операцію:
Додавання двох многочленів.
Опис алгоритму вирішення задачі
Рис.3.3.1. Блок- схема алгоритму АТД «Список»
Аналіз алгоритму
Текст програми наведений в додатку В.
В даній програмі необхідно здійснити додавання двох многочленів. Спершу потрібно ввести в всі поля списку відповідні дані кожного многочлена який підлягає додаванню. Далі відбувається групування елементів списку (многочленів) відповідно за коефіцієнтами для подальшого додавання. Відбувається додавання згрупованих многочленів і їх подальший вивід.
Результат виконання програми
Рис.3.3.2. Ескіз вікна з результатом виконання програми АТД «Список»
Застосування АТД " ДЕРЕВО " до розв’язання прикладних задач
4.1. Операційні системи типу UNIX, PC-DOS (старші версії) підтримують деревоподібну структуру збереження даних на диску. При цьому мінімальна іменована одиниця інформації називається файлом. Файли об'єднуються в каталоги, кожний з яких теж має ім'я. Множина каталогів і окремих файлів можуть у свою чергу також утворити каталог більш високого рівня. Каталог найвищого рівня називається кореневим. Кількість рівнів вкладеності не обмежена. Розглядати тільки випадки без порожніх каталогів (тобто каталогів, що не мають файлів).
Скласти програму для виводу на екран по рівнях:
а) списку всіх елементів даних, "вкладених" у довільний каталог на всіх рівнях;
б) списку всіх каталогів, "вкладених" у довільний каталог;
в) списку всіх файлів, "вкладених" у довільний каталог;
г) списку всіх елементів даних кореневого каталогу, виведених в алфавітному порядку.
Приклад:
На заданій схемі елемент 0 є кореневим каталогом диску;
елементи 2,3,6,10 - каталогами; елементи 1,4,7,9,8,5 - файлами.
Для каталогу 2 перше завдання має виводити таку послідовність:
2
6
4
7
9
Примітка: для всіх завдань замість номерів використовувати імена (текстові значення).
Опис алгоритму вирішення задачі
Рис. 3.4.1. Блок- схема алгоритму АТД «Дерево»
Аналіз алгоритму
Текст програми наведений в додатку Д.
В даній програмі необхідно реалізувати інтерфейс який забезпечить функціонування такої структури як папка та файли/папки і ній. Відбувається створення папок, відповідна навігація по каталогам та створення в них файлів та папок для показу можливостей інтерфейсу. Відбувається виведення інформації про всі папки та їх вмістилища.
Створюю клас DosHierarchy в якому є об’єкт типу «дерево». Вітка дерева без підвіток – файл, вітка з підвітками –каталог. В класі реалізовано методи для створення та видалення каталогів
14.04.2015 19:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора