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

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

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

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

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

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

Коментарі

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

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

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!
Нічого не вибрано
0%

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

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

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

Admin

26.02.2023 12:38

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