Міністерство освіти і науки, молоді та спорту України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи №5
з дисципліни: “Обчислювальний практикум”
1 Теоретична частина
Переваги динамічних структур даних
Динамічні структури даних щодо визначення характеризуються відсутністю фізичної суміжності елементів структури пам'яті непостійністю і непередбачуваністю розміру (числа елементов4) структури в процесі її обробки. У цьому розділі розглянуто особливості динамічних структур, що визначаються їх першим характерним властивістю.
Оскільки елементи динамічної структури розташовуються по непередбачуваним адресами пам'яті, адреса елемента такої структури не може бути обчислений з адреси початкового або попереднього елемента. Для встановлення зв'язку між елементами динамічної структури використовуються покажчики, через які встановлюються явні зв'язки між елементами. Таке подання даних у пам'яті називається зв'язковим.
Елемент динамічної структури складається з двох полів:
інформаційного поля або поля даних, в якому містяться ті дані, заради яких і створюється структура; в загальному випадку інформаційне поле саме є інтегрованою структурою-вектором, масивом, записом і т.п.;
полі зв'язок, в якому містяться один або кілька покажчиків, що зв'язує цей елемент з іншими елементами структури.
Коли зв'язне подання даних використовується для розв'язання прикладної задачі, для кінцевого користувача дивись робиться тільки вміст інформаційного поля, а поле зв'язок використовується тільки програмістом-розробником.
Переваги зв'язкового представлення даних:
у можливості забезпечення значної мінливості структур;
розмір структури обмежується тільки розміром пам'яті машини;
при зміні логічної послідовності елементів структури потрібно не переміщення даних в пам'яті, а тільки корекція покажчиків.
Однак існують і недоліки:
робота з покажчиками вимагає, як правило, більш високої кваліфікації від програміста;
на поля зв'язок витрачається додаткова пам'ять;
доступ до елементів зв'язного структури може бути менш ефективним за часом.
Застосування динамічних структур
Останній недолік є найбільш серйозним і саме їм обмежується застосовність зв'язкового представлення даних. Якщо в суміжному поданні даних для обчислення адреси будь-якого елемента нам у всіх випадках достатньо було номера елемента або інформації, що міститься в дескрипторі структури, то для зв'язкового подання адресу елемента не може бути обчислений з вихідних даних.
Дескриптор зв'язного структури містить один або кілька покажчиків, що дозволяють увійти в структуру, далі пошук і необхідного елемента виконується проходженням по ланцюжку покажчиків від елемента до елементу. Тому зв'язне уявлення практично ніколи не застосовується в задачах, де логічна структура даних має вигляд вектора або масиву - з доступом за номером елемента, але часто застосовується в задачах, де логічна структура вимагає іншої вихідної інформації доступу (таблиці, стеки, списки, дерева і т . д.).
Дерево - в інформатиці та програмуванні одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з одного або більше вузлів (nodes), яка задовольняє наступним вимогам:
існує один відокремлений вузол - корень (root) дерева
інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T1, ..., Tm і кожна з цих множин в свою чергу є деревом. Дерева T1, ..., Tm мають назву піддерев (subtrees) даного кореня.
З цього визначення випливає, що кожний вузлів є в свою чергу коренем деякого піддерева. Кількість піддерев вузла має назву степеня (degree) цього вузла. Вузол степеню нуль називається кінцевим (terminal) або листком (leaf). Не корінь і некінцевий вузол також має назву вершини розгалуження (branchnode). Нехай x - довільний вузол дерева з коренем r. Тоді існує єдиний шлях з r до x. Усі вузли на цьому шляху називаються предками (ancestors) x; якщо деякий вузол y є предком x, то x називається нащадком (descendant) y.
3.3. Результати виконання програми
/
4.1 Постановка задачі
Глосарій або предметний покажчик підручника складається з впорядкованих по алфавіту основних термінів, кожен з яких супроводжується впорядкованою за зростанням послідовністю номерів сторінок, де він зустрічається, і множиною підтермінів. Підтерміни виводяться на наступних за основним терміном рядках, вони дещо зсунуті вправо відносно основного терміна і впорядковані по алфавіту всередині основного терміна. Кожен підтермін супроводжується впорядкованою за зростанням послідовністю номерів сторінок, де він зустрічається.
Розробити структуру даних для представлення такого предметного покажчика і написати програму для зображення предметного покажчика по вхідних даних, що зберігаються у текстовому файлі.
Кожний вхідний рядок починається або з символу М (основний термін), або з символу S (підтермін). Рядок з символом М містить основний термін, за котрим слідують номери сторінок, на котрих зустрічається основний термін. Рядок з символом S будується аналогічно, за винятком того, що він містить не основний термін, а підтермін. Вхідні рядки з’являються у будь-якому порядку. Єдина умова: кожен підтермін вважається підтерміном найближчого попереднього основного терміна. Для одного основного терміна або підтерміна може бути декілька вхідних рядків (всі номери сторінок, що з’являються для конкретного терміна у будь-якому рядку, повинні бути надруковані разом з цим терміном).
4.2.1. Алгоритм розв’язання задачі
Створюю клас Glossary, оснвою якогоє об’єкт класу Tree. Рівень 1, тобто підвітки кореня дерева, це терміни, рівень 2 це підтерміни або сторінки де зустрічаються терміни, рівень 3 це сторінки на яких зустрічаються підтерміни. В класі реалізовано методи для пошуку в глосарії за терміном, а також за терміном і підтерміном.
Основні методи класу Glossary:
voidAdd(char* Term, int* Pages, intPagesNum) - додаєінформацію в глосарій у виглядітермін ->йогосторінки
voidAdd(char* Term, char* SubTerm, int* Pages, intPagesNum)- додаєінформацію в глосарій у виглядітермін ->йогопідтерміни ->йогосторінки
boolDeleteTerm(char* Term) - видаляєтермін, якщовінприсутнійвглосарії
boolFindByTerm(char* Term)- шукаєтермінвглосаріїі виводить інформацію про нього
boolFindByTerm(char* Term, char* SubTerm) - шукає термін в глосарії за терміном та підетрміном і виводить інформацію про нього
4.2.2. Граф-Схема алгоритму роботи програми
/
Граф-Схемаалгоритму методуAdd(char* Term, int* Pages, intPagesNum)/
Граф-СхемаалгоритмуметодуAdd(char* Term, char* SubTerm, int* Pages, intPagesNum)/
Граф-СхемаалгоритмуметодуDeleteTerm(char* Term)
/
Граф-Схема алгоритму методу FindByTerm(char* Term)/
Граф-Схема алгоритму методуFindByTerm(char* Term, char* SubTerm)
/
4.2.3. Результати виконання програми
/
Висновки
Створено програму, яка моделює глосарій книги за допомгою АТД «Дерево». Реалізовано всі необхідні методи та методи, які задані завданням.
Додаток А
Tree.h (Динаміка дерева)
#pragmaonce
#include<iostream>
#include<fstream>
#include<clocale>
usingnamespacestd;
class Node//класвітка
{
public:
Node(Node* _Parent, char* _Data, int _MaxSubNode)
{
this->MaxSubNode = _MaxSubNode;
this->Parent = _Parent;
this->Sons = new Node*[1000];
this->SonsNum = 0;
for(inti = 0; i<this->MaxSubNode; i++)
{
this->Sons[i] = NULL;
}
if(_Data != NULL)
{
this->Data = newchar[strlen(_Data)+1];
strcpy(this->Data, _Data);
}
else
{
this->Data = NULL;
}
}
Node* AddSon(char* _Data)//додаєпідвіткудовітки
{
if(this->SonsNum<this->MaxSubNode)
{
this->Sons[SonsNum] = new Node(this,_Data, this->MaxSubNode);
returnthis->Sons[SonsNum++];
}
else
{
return NULL;
}
}
voidDeleteSon(int index)
{
if(index > 0 && index <GetSonsNum())
{
if(index == GetSonsNum()+1)
{
this->Sons[index] = NULL;
this->SonsNum--;
return;
}
for(inti = index; i<GetSonsNum() - 1; i++)
{
this->Sons[i] = this->Sons[i+1];
}
this->SonsNum--;
}
}
char* GetData()//повертаєданіувітці
{
returnthis->Data;
}
intGetSonsNum()
{
returnthis->SonsNum;
}
Node* GetParent()
{
returnthis->Parent;
}
Node* operator[](int index)//перевантаженийоператор [] поврневказівникнапідвіткузалежновідіндексувквадратнихдужках [index]
{
if(index >=0 && index <SonsNum)
{
returnthis->Sons[index];
}
else
{
return NULL;
}
}
private:
char* Data;//даніувітці
Node** Sons;//вказівникинапідвитки
Node* Parent;//вказівникнавітку-батька
intSonsNum;//кількістьпідвітокувітки
intMaxSubNode;//максимальнакількістьпідвітокувітки
};
class Tree//класдерево
{
public:
Tree(int _MaxSubNode)//вконструкторівказуєтьсяскількипідвітокможематикожнавіткадерева
{
this->Root = new Node(NULL,NULL, _MaxSubNode);
}
Node* GetRoot()
{
returnthis->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)
{
returnthis->TotalNode->AddSon(Data);
}
boolDeleteSubNode(int index)
{
if((*this->TotalNode)[index] != NULL)
{
this->TotalNode->DeleteSon(index);
returntrue;
}
else
{
returnfalse;
}
}
voidReturnToRoot()
{
this->TotalNode = this->ItsTree->GetRoot();
this->TotalSubNodeIndex = 0;
return;
}
boolToSubNode(int index)
{
if((*this->TotalNode)[index] != NULL)
{
this->TotalNode = (*this->TotalNode)[index];
this->TotalSubNodeIndex = index;
returntrue;
}
else
{
returnfalse;
}
}
boolToNextNode()
{
if((*this->TotalNode->GetParent())[this->TotalSubNodeIndex + 1] != NULL)
{
this->TotalNode = (*this->TotalNode->GetParent())[TotalSubNodeIndex + 1];
TotalSubNodeIndex++;
returntrue;
}
else
{
returnfalse;
}
}
boolToPreviousNode()
{
if((*this->TotalNode->GetParent())[this->TotalSubNodeIndex - 1] != NULL)
{
this->TotalNode = (*this->TotalNode->GetParent())[--TotalSubNodeIndex];
returntrue;
}
else
{
returnfalse;
}
}
voidPrintTotalData()
{
cout<<this->TotalNode->GetData() <<endl;
return;
}
private:
Tree* ItsTree;
Node* TotalNode;
intTotalSubNodeIndex;//показуєякоюпідвіткоюпопорядкуєданавітка
};
Main.cpp(Динаміка дерева)
#include"Tree.h"
void main()
{
Tree* tree = newTree(1000);
Iterator* iterator = newIterator(tree);
iterator->CreateSubNode("Node0");
iterator->CreateSubNode("Node1");
iterator->CreateSubNode("Node2");
iterator->CreateSubNode("Node3");
iterator->ToSubNode(0);
for(inti = 0; i < 4;i++)
{
iterator->PrintTotalData();
iterator->ToNextNode();
}
iterator->ReturnToRoot();
iterator->DeleteSubNode(2);
iterator->ToSubNode(2);
for(inti = 0; i < 3;i++)
{
iterator->PrintTotalData();
iterator->ToPreviousNode();
}
iterator->ReturnToRoot();
iterator->ToSubNode(2);
iterator->PrintTotalData();
}
ДодатокB
Tree.h
#pragmaonce
#include<iostream>
#include<fstream>
#include<clocale>
usingnamespacestd;
#pragmaonce
#include<iostream>
#include<fstream>
#include<clocale>
usingnamespacestd;
class Node//класвітка
{
public:
Node(Node* _Parent, char* _Data, int _MaxSubNode)
{
this->MaxSubNode = _MaxSubNode;
this->Parent = _Parent;
this->Sons = new Node*[1000];
this->SonsNum = 0;
for(inti = 0; i<this->MaxSubNode; i++)
{
this->Sons[i] = NULL;
}
if(_Data != NULL)
{
this->Data = newchar[strlen(_Data)+1];
strcpy(this->Data, _Data);
}
else
{
this->Data = NULL;
}
}
Node* AddSon(char* _Data)//додаєпідвіткудовітки
{
if(this->SonsNum<this->MaxSubNode)
{
this->Sons[SonsNum] = new Node(this,_Data, this->MaxSubNode);
returnthis->Sons[SonsNum++];
}
else
{
return NULL;
}
}
voidDeleteSon(int index)
{
if(index > 0 && index <GetSonsNum())
{
if(index == GetSonsNum()+1)
{
this->Sons[index] = NULL;
this->SonsNum--;
return;
}
for(inti = index; i<GetSonsNum() - 1; i++)
{
this->Sons[i] = this->Sons[i+1];
}
this->SonsNum--;
}
}
char* GetData()//повертаєданіувітці
{
returnthis->Data;
}
intGetSonsNum()
{
returnthis->SonsNum;
}
Node* GetParent()
{
returnthis->Parent;
}
Node* operator[](int index)//перевантаженийоператор [] поврневказівникнапідвіткузалежновідіндексувквадратнихдужках [index]
{
if(index >=0 && index <SonsNum)
{
returnthis->Sons[index];
}
else
{
return NULL;
}
}
private:
char* Data;//даніувітці
Node** Sons;//вказівникинапідвитки
Node* Parent;//вказівникнавітку-батька
intSonsNum;//кількістьпідвітокувітки
intMaxSubNode;//максимальнакількістьпідвітокувітки
};
class Tree//класдерево
{
public:
Tree(int _MaxSubNode)//вконструкторівказуєтьсяскількипідвітокможематикожнавіткадерева
{
this->Root = new Node(NULL,NULL, _MaxSubNode);
}
Node* GetRoot()
{
returnthis->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)
{
returnthis->TotalNode->AddSon(Data);
}
boolDeleteSubNode(int index)
{
if((*this->TotalNode)[index] != NULL)
{
this->TotalNode->DeleteSon(index);
returntrue;
}
else
{
returnfalse;
}
}
voidReturnToRoot()
{
this->TotalNode = this->ItsTree->GetRoot();
this->TotalSubNodeIndex = 0;
return;
}
boolToSubNode(int index)
{
if((*this->TotalNode)[index] != NULL)
{
this->TotalNode = (*this->TotalNode)[index];
this->TotalSubNodeIndex = index;
returntrue;
}
else
{
returnfalse;
}
}
boolToNextNode()
{
if((*this->TotalNode->GetParent())[this->TotalSubNodeIndex + 1] != NULL)
{
this->TotalNode = (*this->TotalNode->GetParent())[TotalSubNodeIndex + 1];
TotalSubNodeIndex++;
returntrue;
}
else
{
returnfalse;
}
}
boolToPreviousNode()
{
if((*this->TotalNode->GetParent())[this->TotalSubNodeIndex - 1] != NULL)
{
this->TotalNode = (*this->TotalNode->GetParent())[--TotalSubNodeIndex];
returntrue;
}
else
{
returnfalse;
}
}
voidPrintTotalData()
{
cout<<this->TotalNode->GetData() <<endl;
return;
}
private:
Tree* ItsTree;
Node* TotalNode;
intTotalSubNodeIndex;//показуєякоюпідвіткоюпопорядкуєданавітка
};
Glossary.h(Курсова, частина 2)
#include"Tree.h"
class Glossary//класглосарій, вякомуобявленіметодидлядодаваннятермінів, підтермінівтасторінок.. ДанівкласіпобудованінаосновіСТД "Дерево"
{
public:
Glossary(intMaxGlossaries)
{
this->GlossaryTree = new Tree(MaxGlossaries);
}
boolLoadFromFile(char* path)//заповнюєглосарійзфайла.. по заданому шляху до коректнозаповненого файла
{
char** Lines = newchar*[1000];
for(inti = 0; i < 1000;i++)
{
Lines[i] = NULL;
}
ifstreamifile(path);
if (!ifile.good())
returnfalse;
inti =0;
while (!ifile.eof())
{
charbuf[512];
Lines[i] = newchar[512];
ifile.getline(buf, sizeof(buf)-1);
buf[512-1] = '\0';
strcpy(Lines[i++], buf);
}
int* Pages = newint[i-2];
for(int j =2, k = 0; j <i;j++, k++)
{
Pages[k] = atoi(Lines[j]);
}
this->Add(Lines[0],Lines[1], Pages, i-2);
returntrue;
}
void Add(char* Term, int* Pages, intPagesNum)//додаєінформаціювглосарійувиглядітермін ->йогосторінки
{
Node* PresentTerm = NULL;
char* Buf= newchar[256];
for(inti = 0; i<this->GlossaryTree->GetRoot()->GetSonsNum(); i++)//якщотермінвжеєвдеревітовононебудестворюватиновийаоновитьужеіснуючий
{
if(!strcmp((*this->GlossaryTree->GetRoot())[i]->GetData(), Term))
{
PresentTerm = (*this->GlossaryTree->GetRoot())[i];
break;
}
}
if(PresentTerm != NULL)
{
for(inti = 0; i<PagesNum;i++)
{
itoa(Pages[i], Buf, 10);
PresentTerm->AddSon(Buf);
}
}
else
{
PresentTerm = this->GlossaryTree->GetRoot()->AddSon(Term);
for(inti = 0; i<PagesNum;i++)
{
itoa(Pages[i], Buf, 10);
PresentTerm->AddSon(Buf);
}
}
return;
}
void Add(char* Term, char* SubTerm, int* Pages, intPagesNum)//додаєінформаціювглосарійувиглядітермін ->йогопідтерміни ->йогосторінки
{
Node* PresentTerm = NULL;
Node* PresentSubTerm = NULL;
char* Buf = newchar[256];//буфер у 256 байт для тимчасовогозбереженняпереведень числа int в строку (даны у віткахтыльки строки)
for(int i = 0; i <this->GlossaryTree->GetRoot()->GetSonsNum(); i++)//якщотермінвже є в дереві то воно не буде створюватиновий а оновить уже існуючий
{
if(!strcmp((*this->GlossaryTree->GetRoot())[i]->GetData(), Term))
{
PresentTerm = (*this->GlossaryTree->GetRoot())[i];
break;
}
}
if(PresentTerm != NULL)
{
for(inti = 0; i<PresentTerm->GetSonsNum(); i++)
{
if(!strcmp((*PresentTerm)[i]->GetData(), SubTerm))
{
PresentSubTerm = (*PresentTerm)[i];
break;
}
}
if(PresentSubTerm != NULL)
{
for(inti = 0; i<PagesNum;i++)
{
itoa(Pages[i], Buf, 10);
PresentSubTerm->AddSon(Buf);
}
}
else
{
PresentSubTerm = PresentTerm->AddSon(SubTerm);
for(inti = 0; i<PagesNum;i++)
{
itoa(Pages[i], Buf, 10);
PresentSubTerm->AddSon(Buf);
}
}
}
else
{
PresentTerm = this->GlossaryTree->GetRoot()->AddSon(Term);
PresentSubTerm = PresentTerm->AddSon(SubTerm);
for(inti = 0; i<PagesNum;i++)
{
itoa(Pages[i], Buf, 10);
PresentSubTerm->AddSon(Buf);
}
}
return;
}
voidPrintWholeGlossary()//виводитьвсюінформаціювглосаріївфайл
{
Node Root = *this->GlossaryTree->GetRoot();
for(inti = 0; i<this->GlossaryTree->GetRoot()->GetSonsNum(); i++)
{
cout<< Root[i]->GetData() <<endl;
for(int j = 0; j < Root[i]->GetSonsNum(); j++)
{
cout<<" - "<< (*Root[i])[j]->GetData();
for(int k = 0; k < (*Root[i])[j]->GetSonsNum(); k++)
{
cout<<" стр."<< (*(*Root[i])[j])[k]->GetData();
if(k +1 < (*Root[i])[j]->GetSonsNum())
{
cout<<',';
}
else
{
cout<<endl;
}
}
}
}
}
boolFindByTerm(char* Term)//шукаєтермінвглосарії
{
Node* Result = NULL;
for(inti = 0; i<this->GlossaryTree->GetRoot()->GetSonsNum(); i++)//якщотермінвжеєвдеревітовононебудестворюватиновийаоновитьужеіснуючий
{
if(!strcmp((*this->GlossaryTree->GetRoot())[i]->GetData(), Term))
{
Result = (*this->GlossaryTree->GetRoot())[i];
break;
}
}
if(Result != NULL)
{
cout<< Result->GetData() <<endl;
for(int j = 0; j < Result->GetSonsNum(); j++)
{
cout<<" - "<< (*Result)[j]->GetData();
for(int k = 0; k < (*Result)[j]->GetSonsNum(); k++)
{
cout<<" стр."<< (*(*Result)[j])[k]->GetData();
if(k +1 < (*Result)[j]->GetSonsNum())
{
cout<<',';
}
else
{
cout<<endl;
}
}
}
returntrue;
}
else
{
cout<<"Нiчогонезнайдено"<<endl;
returnfalse;
}
}
boolFindByTerm(char* Term, char* SubTerm)
{
Node* ResultTerm = NULL;
Node* ResultSubTerm = NULL;
for(inti = 0; i<this->GlossaryTree->GetRoot()->GetSonsNum(); i++)//якщотермінвжеєвдеревітовононебудестворюватиновийаоновитьужеіснуючий
{
if(!strcmp((*this->GlossaryTree->GetRoot())[i]->GetData(), Term))
{
ResultTerm = (*this->GlossaryTree->GetRoot())[i];
break;
}
}
if( ResultTerm != NULL)
{
for(inti = 0; i<ResultTerm->GetSonsNum(); i++)//якщотермінвжеєвдеревітовононебудестворюватиновийаоновитьужеіснуючий
{
if(!strcmp((*ResultTerm)[i]->GetData(), SubTerm))
{
ResultSubTerm = (*ResultTerm)[i];
break;
}
}
if(ResultSubTerm != NULL)
{
cout<<" - "<<ResultSubTerm->GetData();
for(int k = 0; k <ResultSubTerm->GetSonsNum(); k++)
{
cout<<" стр."<< (*ResultSubTerm)[k]->GetData();
if(k +1 <ResultSubTerm->GetSonsNum())
{
cout<<',';
}
else
{
cout<<endl;
}
}
returntrue;
}
else
{
cout<<"Нiчого не знайдено"<<endl;
returnfalse;
}
}
else
{
cout<<"Нiчого не знайдено"<<endl;
returnfalse;
}
}
private:
Tree* GlossaryTree;
};
Main.cpp
#include"Glossary.h"
void main()
{
setlocale(0,"");
Glossary* Gloss = new Glossary(1000);
int Pages[] = {10,11,12,13};// сторінкитермінів
int Pages1[] = {14,15,16,17};// сторінкитермінів
int Pages2[] = {18,19,20,21};// сторінкитермінів
int Pages3[] = {22,23,24,25};// сторінкитермінів
Gloss->Add("Квантовамеханiка", "СтацiонарнерiвнянняШредiнгера",Pages, 4);//додаюінформаціювглосарій
Gloss->Add("Молекулярнафiзика", "Перший закон термодинамiки",Pages1, 4);
Gloss->Add("Молекулярнафiзика", "Другий закон термодинамiки",Pages2, 4);
Gloss->Add("Квантовамеханiка", "Принцип невизначеностей Гейзенберга",Pages3, 4);
Gloss->PrintWholeGlossary();// виводжу всю інформацію в глосарії
cout<<"Пошукрезультатiв за запитом \"Молекулярнафiзика\":"<<endl;
Gloss->FindByTerm("Молекулярнафiзика");
cout<<"Пошукрезультатiв за запитом \"Оптика\":"<<endl;
Gloss->FindByTerm("Оптика");
cout<<"Пошукрезультатiв за запитом \"Молекулярнафiзика\", \"Другий закон термодинамiки\":"<<endl;
Gloss->FindByTerm("Молекулярнафiзика","Другий закон термодинамiки");
Glossary* Gloss1 = newGlossary(1000);//створююще один порожнійглосарій
Gloss->LoadFromFile("Gloss.txt");//заповнююйого з файла
Gloss->PrintWholeGlossary();// вивожу всю інформацію в глосарії
return;
}