Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ

Інформація про роботу

Рік:
2018
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Обчислювальний практикум

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки, молоді та спорту України Національний університет „Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи №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; }
Антиботан аватар за замовчуванням

03.04.2018 21:57

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Нічого не вибрано
0%

Оголошення від адміністратора

Антиботан аватар за замовчуванням

Подякувати Студентському архіву довільною сумою

Admin

26.02.2023 12:38

Дякуємо, що користуєтесь нашим архівом!