Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Динамічні структури даних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2014
Тип роботи:
Розрахункова робота
Предмет:
Обчислювальний практикум
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ ЛЬВІВСЬКА ПОЛІТЕХНІКА ”
Кафедра ЕОМ
Розрахункова робота на тему
" Динамічні структури даних "
з дисципліни
" Обчислювальний практикум "
Варіант №7
ЗМІСТ
1. ТЕОРЕТИЧНА ЧАСТИНА 3
1.1. Абстрактний тип даних (АТД, ADT) 3
1.2. Стек (Stack) 3
1.3. Черга (Queue) 3
1.4. Список (List) 4
1.5. Дерево (Tree) 5
2. ПОБУДОВА АТД 7
2.1. Абстрактний тип даних «Стек» 7
2.1.1. Реалізація стеку 7
2.1.2. Тестова програма 8
2.1.3. Результат тестування 8
2.2. Абстрактний тип даних «Черга» 9
2.2.1. Реалізація черги 9
2.2.2. Тестова програма 10
2.2.3. Результат тестування 11
2.3. Абстрактний тип даних «Список» 12
2.3.1. Реалізація списку 12
2.3.2. Тестова програма 14
2.3.3. Результат тестування 14
2.4. Абстрактний тип даних «Дерево» 15
2.4.1. Реалізація дерева 15
2.4.2. Тестова програма 17
2.4.3. Результат тестування 17
3. ЗАСТОСУВАННЯ АТД 18
3.1. Завдання 1 18
3.1.1. Опис алгоритму 18
3.1.2. Результат виконання програми 18
3.1.3. Блок-схема алгоритму 19
3.2. Завдання 2 21
3.2.1. Опис алгоритму 21
3.2.2. Результат виконання програми 21
3.2.3. Блок-схема алгоритму 22
3.3. Завдання 3 24
3.3.1. Опис алгоритму 24
3.3.2. Результат виконання програми 24
3.3.3. Блок-схема алгоритму 24
3.4. Завдання 4 26
3.4.1. Опис алгоритму 26
3.4.2. Результат виконання програми 26
3.4.3. Блок-схема алгоритму 27
ВИСНОВКИ 29
СПИСОК ЛІТЕРАТУРИ 30
ДОДАТОК А. КОД ПРОГРАМИ ДО ЗАВДАННЯ 1 31
ДОДАТОК Б. КОД ПРОГРАМИ ДО ЗАВДАННЯ 2 32
ДОДАТОК В. КОД ПРОГРАМИ ДО ЗАВДАННЯ 3 33
ДОДАТОК Г. КОД ПРОГРАМИ ДО ЗАВДАННЯ 4 37
ТЕОРЕТИЧНА ЧАСТИНА
Абстрактний тип даних (АТД, ADT)
Абстрактний тип даних – математична модель із сукупністю операторів, визначених в рамках цієї моделі. Простим прикладом можуть служити множини цілих чисел з операторами об’єднання, перетину та різниці множин. В моделі АТД оператори можуть мати операндами не лише дані, визначені цим АТД, але і дані інших типів: стандартних типів, визначених мовою програмування чи визначених в інших АТД.
АТД можна розглядати як узагальнення простих типів даних. Він інкапсулює типи даних в тому сенсі, що визначення типу і всі оператори, виконувані над даними цього типу, поміщаються в один розділ програми. Якщо необхідно змінити реалізацію АТД, ми знаємо, де знайти і що змінити в одному невеликому розділі програми.
Термін «реалізація АТД» передбачає наступне: переведення в оператори мови програмування оголошень, що визначають змінні цього абстрактного типу даних, плюс процедури для кожного оператора, виконуваного над об’єктами АТД. Реалізація залежить від структури даних, що представляє АТД. Кожна з них будується на основі базових типів даних застосовуваної мови програмування, використовуючи доступі засоби структурування.
Різницяміжабстрактними типами даних і структурами даних, які реалізують абстрактні типи, можна пояснити на наступному прикладі. Абстрактний тип данихсписок може бути реалізований за допомогою масиву або лінійного списку, з використанням різних методів динамічного виділення пам'яті. Однак кожна реалізація визначає один і той же набір функцій, який повинен працювати однаково (по результату, а не по швидкості) для всіх реалізацій.
Абстрактнітипиданихдозволяютьдосягтимодульності програмнихпродуктів і матикількаальтернативнихвзаємозаміннихреалізаційокремого модуля.
Стек (Stack)
З англ. stack - стопка - структура даних, в якій доступ до елементів організований за принципом LIFO (англ. last in - firstout , "Останнім прийшов - першим вийшов"). Найчастіше принцип роботи стека порівнюють зі стопкою тарілок: щоб взяти другу зверху, потрібно зняти верхню. В цифровому обчислювальному комплексі стек називається магазином - по аналогії з магазином у вогнепальній зброї (стрільба почнеться з патрона, зарядженого останнім).
Таблиця 1.2.1. Основні операції над стеком
Операція
Дія
empty()
Повертає true, якщо стек порожній, і false у противному випадку
sіze()
Повертає розмір стека
pop()
Видаляє вершину стека
top()
Повертає значення вершини стека
push(T item)
Додає новий елемент у стек, де Т – тип даних стека
swap(stack& x)
Обмінюється вмістом двох стеків
Черга (Queue)
Черга(queue) – впорядкований контейнер елементів, в якому додавання нового здійснюється в кінець (чи як його ще називають «хвіст» (tail, rear)) і видалення елементів здійснюється з іншого боку, тобто початку (голови (head, front)). Як тільки елемент встане в чергу, він опиняється в її кінці і прямує до голови, очікуючи видалення елемента, що стоїть перед ним.Такий принцип ще називають «Перший прийшов – перший пішов» (FiFo – first-infirstout).
Найпростішим прикладом черги є звичайна «людська» черга, в якій ми опиняємось практично кожен день. Ми стоїмо на касі в супермаркеті, в черзі за кавою, чекаємо потрібного сеансу в кінотеатрі тощо.
Черга (як структура даних) є обмежена тим, що є лише один вхід і один вихід з неї. Не можна просто взяти та зайти в середину черги чи покинути її, не дочекавшись потрібного часу, щоб дістатись до її голови.
Перевагою такої структури для зберігання даних можна вважати її динамічність – обмежується тільки об’ємом пам’яті. Недоліком – складну процедуру пошуку і додавання елементів при великих об’ємах даних, що зберігаються.
Таблиця 1.3.1. Основні операції над чергою
Операція
Дія
empty()
Повертає true, якщо черга порожня, і false у противному випадку
sіze()
Повертає розмір черги
front()
Повертає значенняпершого елементу
back()
Повертає значення останнього елементу
pop()
Видаляє елемент із черги, але не повертає його значення
push(T item)
Додає новий елемент у чергу
swap(queue& x)
Обмінюється вмістом двох стеків
Дек - особливий вид черги. Дек (від англ. deque - doubleendedqueue, тобто черга із двома кінцями) - це така послідовність, у якій як додавання, так і вилучення елементів може здійснюватися з кожного із двох кінців. Окремий випадок дека - дек з обмеженим входом і дек з обмеженим виходом. Логічна й фізична структури дека аналогічні логічній і фізичній структурі кільцевої FіFO-черги. Однак, стосовно до дека доцільно про лівий і правий кінці. Динамічна реалізація дека є об'єднанням стека і черги.
Прикладом дека може бути, наприклад, якийсь термінал, у який вводяться команди, кожна з яких виконується якийсь час. Якщо ввести наступну команду, не дочекавшись, поки закінчиться виконання попередньої, то вона встане в чергу й почне виконуватися, як тільки звільниться термінал. Це FІFO черга. Якщо ж додатково ввести операцію скасування останньої введеної команди, то отримаємо дек. Дек підтримує роботу з літератором, відповідно є доступ до будь-якого його елемента.
Таблиця 1.3.2. Основні операції над деком
Операція
Дія
empty()
Повертає true, якщо дек порожній, і false у противному випадку
sіze()
Повертає розмір деку
front()
Повертає значенняпершого елементу
back()
Повертає значенняостаннього елементу
pop_front()
Видаляє перший елемент
pop_back()
Видаляє останній елемент
push_front(T item)
Додає новий елемент в початок деки
push_back(T item)
Додає новий елемент в кінець деки
Список (List)
Лінійний список – це скінчена послідовність однотипних елементів (вузлів), можливо, з повтореннями. Список розташовується в пам'яті довільним чином. Кожний вузол однонаправленого лінійного зв'язаного списку містить вказівник на наступний вузол списку, що дозволяє переміщатися вперед по списку. Кожний вузол двонаправленоголінійного зв'язаного списку містить вказівники на попередній і наступний вузли списку, що дозволяє переміщатися по списку вперед та назад.
Вставка і видалення вузлів списку реалізовані ефективно: змінюються тільки вказівники. З іншого боку, довільний доступ до вузлів списку підтримується погано: щоб прийти до певного вузла списку, треба відвідати всі попередні вузли. Крім того, на відміну від стеків або черг, додатково витрачається пам'ять під один або два вказівники на кожний елемент списку.
Список росте дуже просто: додавання кожного нового елемента приводить до того, що вказівники на попередній і наступний вузли списку, між якими вставляється новий вузол, міняють свої значення. У новому елементі таким вказівникам присвоюється значення адрес сусідніх елементів. Список використовує тільки такий об'єм пам'яті, який потрібний для наявної кількості елементів. Підтримується робота з ітератором.
Операція
Дія
empty()
Повертає true, якщо список порожній, і false у противному випадку
sіze()
Повертає розмір списку
front()
Повертає значенняпершого елементу
back()
Повертає значенняостаннього елементу
pop_front()
Видаляє перший елемент
pop_back()
Видаляє останній елемент
push_front(T item)
Додає новий елемент в початок деки
push_back(T item)
Додає новий елемент в кінець деки
insert(it pos, T item)
Вставляє елемент в позицію/проміжок, задані ітератором (itpos)
erase(it pos, T item)
Видаляє елемент(и) з позиції/проміжку, заданої ітератором (itpos)
Таблиця 1.4.1. Основні операції над списком
Дерево (Tree)
Дерево - в інформатиці та програмуванні одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з однієї або більше вершин (вузлів, nodes), яке задовольняє наступним вимогам:
існує один виокремлений вузол - корінь (root) дерева
інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множинT1.Tm і кожна з цих множин в свою чергу є деревом. Дерева T1.Tm мають назву піддерев (subtrees) даного кореня.
З цього визначення випливає, що кожна вершина є в свою чергу коренем деякого піддерева. Кількість піддерев вершини має назву ступеня (degree) цієї вершини. Вершина ступеню нуль має назву кінцевої (terminal) або листа (leaf). Некінцева вершина також має назву вершини розгалуження (branchnode). Нехай x - довільна вершина дерева з коренем r. Тоді існує єдиний шлях з r до x. Усі вершини на цьому шляху називаються предками (ancestors) x; якщо деяка вершина y є предком x, то x називається нащадком (descendant) y. Нащадки та предки вершини x, що не співпадають з нею самою, називаються власними нащадками та предками. Кожну вершину x, в свою чергу, можна розглядати як корень деякого піддерево, елементами якого є вершини-нащадки x. Якщо вершини x є предком y та не існує вершин поміж ними (тобто x та y з'єднані одним ребром), а також існують предки для x (тобто x не є коренем), то вершина x називається батьком (parent) до y, а y - сином (child) x. Коренева вершина єдина не має батьків. Вершини, що мають спільного батька, називаються братами (siblings). Вершини, що мають нащадків, називаються внутрішніми (internal). Глибиною вершини x називається довжина шляху від кореня до цієї вершини. Максимальна глибина вершин дерева називається висотою.
Важливим окремим випадком кореневих дерев є бінарні дерева, які широко застосовуються в програмуванні і визначаються як множина вершин, яка має виокремлений корінь та два піддерева (праве та ліве), що не перетинаються, або є пустою множиною вершин (на відміну від звичайного дерева, яке не може бути пустим).
Важливими операціями на деревах є:
обхід вершин в різному порядку
перенумерація вершин
пошук елемента
додавання елемента у визначене місце в дереві
видалення елемента
видалення цілого фрагмента дерева
додавання цілого фрагмента дерева
знаходження кореня для будь-якої вершини
Найбільшого розповсюдження ці структури даних набули в тих задачах, де необхідне маніпулювання з ієрархічними даними, ефективний пошук в даних, їхнє структуроване зберігання та модифікація.
В програмуванні бінарне дерево - дерево, в якому кожна вершина має не більше двох синів. Зазвичай такі сини називаються правим та лівим. На базі бінарних дерев будуються такі структури, як бінарні дерева пошуку та бінарні купи.
Різновиди бінарних дерев :
Повне (закінчене) бінарне дерево - таке бінарне дерево, в якому кожна вершина має нуль або двох синів.
Ідеальне бінарне дерево -- це таке повне бінарне дерево, в якому листя (вершини без синів) лежать на однаковій глибині (відстані від кореня).
Бінарне дерево на кожному n-му рівні має від 1 до 2n вершин.
Часто виникає необхідність обійти усі вершини дерева для аналізу інформації, що в них знаходиться. Існують декілька порядків такого обходу, кожний з яких має певні властивості, важливі в тих чи інших алгоритмах: прямий (preorder), симетричний (simetric) та зворотній (postorder).
Бінарне дерево пошуку:
Бінáрнедéревопóшуку (англ. binarysearchtree, BST) в інформатиці - бінарне дерево, в якому кожній вершині xспівставлене певне значення val[x].При цьомутакізначенняповиннізадовольнятиумовівпорядкованості:
нехай x - довільнавершина бінарного дерева пошуку;
якщо вершина y знаходиться в лівоміпіддеревівершини x, то val[y] ≤ val[x];
якщо у знаходиться у правому піддереві x, то val[y] ≥ val[x].
Такеструктуруваннядозволяєнадрукуватиусізначення у зростаючому порядку за допомогою простого алгоритма центрованого обходу дерева. Бінарні дерева пошукунабагатоефективніші в операціяхпошуку, аніжлінійніструктури, в якихвитрати часу на пошукпропорційні O(n), де n -- розмірмасивуданих, тоді як в повномубінарномудеревіцей час пропорційний в середньому O(log2n) або O(h), де h - висота дерева (хочагарантувати, що h не перевищує log2n можналише для збалансованих дерев, які є ефективнішими на пошукових алгоритмах, аніжпростібінарні дерева пошуку).
ПОБУДОВА АТД
Абстрактний тип даних «Стек»
Змоделювати АТД «Стек». Оформити АТД у вигляді класу. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів з АТД.
Я вирішив реалізувати стек на основі статичного масиву з такими методами : перевірка на порожній вміст, повернення розміру, виштовхування, зштовхування, повернення верхнього елементу, друк вмісту стеку.
Реалізація стеку
--Stack.h--
#include<iostream>
usingnamespacestd;
classStack
{
private:
int array[20];
int iterator;
public:
Stack(){ iterator = -1; };
bool empty();
int size() { return iterator + 1; };
void pop();
int top();
void push(int);
void show();
~Stack() {};
};
--Stack.cpp--
#include"Stack.h"
boolStack:: empty(void)
{
if(iterator==-1)
returntrue;
elsereturnfalse;
}
voidStack:: pop(void)
{
if(iterator!=-1)
iterator--;
}
intStack:: top(void)
{
if(iterator!=-1)
return array[iterator];
}
voidStack:: push(inta)
{
iterator++;
array[iterator]=a;
}
voidStack:: show(void)
{
if(iterator!=-1)
{
int i=iterator;
while(i!=-1)
{
cout<<array[i]<<" ";
i--;
}
}
elsecout<<"Stack empty"<<endl;
}
Тестова програма
#include"Stack.h"
void main()
{
Stackst;
intar[10] = { 2, 2, 4, 5, 7, 6, 8, 9, 4, 3 };
cout<<"Your array: ";
for(int i=0;i<10;i++)
cout<<ar[i]<<" ";
cout<<endl;
for(int i=0;i<10;i++)
{
cout<<"Element:" <<ar[i] <<endl;
cout<<"Stack now:";
if(ar[i]%2==0)
st.push(ar[i]);
elsest.pop();
st.show();
}
}
Результат тестування
Як бачимо на рис. 1, парні елементи заносяться у стек, непарні – видаляють вершину стека. Відповідно зміни відображені на рисунку нижче :
/
Рис..1. Результат виконання тестової програми
Абстрактний тип даних «Черга»
Змоделювати АТД «Queue». Оформити АТД у вигляді класу. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів з АТД.
Я реалізував чергу на основі двохзв’язних вузлів з наступними методами: додавання та видалення елементів, повернення першого та останнього елементів, розміру, перевірки її на порожність та виведення вмісту черги.
Реалізація черги
--queue.h--
#include<iostream>
usingnamespacestd;
classQueueEmptyException
{
public:
QueueEmptyException(){cout<<"Queueempty"<<endl;}
};
structNode
{
intdata;
Node* next;
Node* prev;
};
classQueue
{
private:
Node* front;
Node* rear;
intcount;
public:
Queue()
{
front = NULL;
rear = NULL;
count = 0;
}
voidPop()
{
if (isEmpty())
thrownewQueueEmptyException();
// Deletethefrontnodeandfixthelinks
Node* tmp = front;
if (front->next != NULL)
{
front = front->next;
front->prev = NULL;
}
else
front = NULL;
count--;
deletetmp;
}
voidPush(intelement)
{
// Create a newnode
Node* tmp = newNode();
tmp->data = element;
tmp->next = NULL;
tmp->prev = NULL;
if (isEmpty())
front = rear = tmp;
else
{
// Appendtothelistandfixlinks
rear->next = tmp;
tmp->prev = rear;
rear = tmp;
}
count++;
}
intFront()
{
if (isEmpty())
thrownewQueueEmptyException();
return front->data;
}
intBack()
{
if (isEmpty())
thrownewQueueEmptyException();
return rear->data;
}
intSize(){returncount;}
boolisEmpty(){returncount == 0 ? true : false;}
voidShowQueue()
{
Node * p = front;
if (isEmpty())
thrownewQueueEmptyException;
else
for (int i = 0; i <count; i++)
{
cout<< p->data<<" ";
p = p->next;
}
cout<<endl;
}
~Queue()
{
deletefront;
deleterear;
}
};
Тестова програма
#include"queue.h"
#include<math.h>
voidmain()
{
setlocale(LC_ALL, "Ukrainian");
Queuetest;
int k;
cout<<"Вводьте елементи, якi бажаєте внести в чергу"<<endl;
cout<<"Додатнє число додається в чергу, вiд'ємне вилучає елемент"<<endl;
cout<<"Введiть -999 для завершення введення"<<endl;
do
{
cin>> k;
if (k == -999)break;
if (k >= 0)
{
test.Push(k);
cout<<"Додаємо: "<< k <<endl;
test.ShowQueue();
}
else
{
if (!test.isEmpty())
{
cout<<"Вилучаємо "<<test.Front() <<endl;
test.Pop();
test.ShowQueue();
}
elsethrownewQueueEmptyException();
}
} while (k != -999);
system("pause");
}
Результат тестування
Як бачимо з рис.2, додатні елементи заносяться у чергу, від’ємні елементи – вилучають перший елемент із черги. Динаміку вмісту показано на цьому ж рисунку.
/
Рис. 2. Результат виконання тестової програми
Абстрактний тип даних «Список»
Змоделювати АТД «Список». Оформити АТД у вигляді класу. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів з АТД.
Я реалізував однозв’язний список на базі однозв’язних вузлів (кожен з яких містить вказівник лише на наступний елемент списку) та написав для нього наступні методи : додавання в початок, кінець списку та в певну позицію, пошук вузла за значенням, «інверсія» та друк списку.
Реалізація списку
--List.h--
#include<iostream>
usingnamespace std;
classList
{
private:
structNode
{
int value; // певна інформативна частина
Node * next; // вказівник на наступну структуру-вузол у списку
};
Node * head = NULL; // вказівник на голову списку
public:
void addToBegin(intv)
{
Node * n = newNode;
n->value = v;
n->next = head;
head = n;
}
void addToEnd(intv)
{
Node * n;
if (!head)
{
head = newNode;
head->value = v;
head->next = NULL;
return;
}
else
{
n = head;
while (n->next)
n = n->next;
Node * newNode = newNode;
newNode->value = v;
newNode->next = NULL;
n->next = newNode;
return;
}
}
void deleteNode(Node * n)
{
cout <<"Видаляємо елемент "<<n->value << endl;
Node * k = head;
if (head == n)
{
deleten;
head = NULL;
return;
}
while (k->next != n)
k = k->next;
k->next = n->next;
deleten;
}
void insert(constintv, Node * n)
{
Node * newNode = newNode;
newNode->value = v;
newNode->next = n->next;
n->next = newNode;
}
Node * find(constintv)
{
Node * n = head;
while (n)
{
if (n->value == v)
return n;
n = n->next;
}
returnNULL;
}
void Show()
{
cout <<"Список зараз : ";
Node *n = head;
while (n != NULL)
{
cout << n->value <<" ";
n = n->next;
}
cout << endl;
}
void reverse()
{
cout <<"Iнверсiя списку: ";
Node *temp, *tmp, *var;
temp = head;
var = NULL;
while (temp != NULL)
{
tmp = var;
var = temp;
temp = temp->next;
var->next = tmp;
}
head = var;
}
};
Тестова програма
void main()
{
setlocale(LC_ALL, "Ukrainian");
List list;
int N, p;
cout <<"Введiть число N"<< endl;
cin >> N;
cout <<"Введiть "<< N <<" елементiв"<< endl;
for (int i = 0; i < N; i++)
{
cin >> p;
list.addToEnd(p);
list.Show();
}
list.deleteNode(list.find(10));
list.deleteNode(list.find(25));
list.Show();
list.reverse();
list.Show();
system("pause");
}
Результат тестування
На рисунку 3. показано динаміку вмісту списку при внесенні до нього елемента. Як бачимо, елемент додається у кінець списку. Результат виконання методів видалення елементів та інвертування списку також продемонстровано на даному рисунку.
/
Рис.3. Результат виконання тестової програми
Абстрактний тип даних «Дерево»
Змоделювати АТД «Дерево». Оформити АТД у вигляді класу. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів з АТД.
Я реалізував дерево на основі вузлів, кожен з яких містить поле для значення вузла, вказівник на ліве та праве піддерева та написав наступні методи для нього: додавання та видалення елемента, видалення дерева цілком, перевірка на пустоту, повернення кореня та методи обходу дерева в трьох варіантах.
Реалізація дерева
--Tree.h--
#include<iostream>
usingnamespace std;
classTree
{
private:
structNode {
int data;
Node *left;
Node *right;
};
Node *p;
int k;
Node *root;
public:
Tree() {root = NULL; }
~Tree() { clear(); }
Node * getRoot() { return root; }
bool isEmpty() const { return root == NULL; }
void addNode(intd)
{
Node* t = newNode;
Node *parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;
if (isEmpty())
root = t;
else
{
Node *current;
current = root;
while (current)
{
parent = current;
if ((t->data) > (current->data))
current = current->right;
else
current = current->left;
}
if (t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}
void clear() { recursive_delete(root); }
void recursive_delete(Node* node)
{
if (node != NULL)
{
recursive_delete(node->left);
recursive_delete(node->right);
deleteNode(node);
}
}
void deleteNode(Node* node)
{
deletenode;
node = NULL;
}
void printInOrder()
{
cout <<"Inorder: ";
inorder(root);
cout << endl;
}
void inorder(Node* p)
{
if (p != NULL)
{
if (p->left)
inorder(p->left);
cout <<" "<<p->data <<" ";
if (p->right)
inorder(p->right);
}
elsereturn;
}
void printPostOrder()
{
cout <<"Postorder: ";
postorder(root);
cout << endl;
}
void postorder(Node* p)
{
if (p != NULL)
{
if (p->left) postorder(p->left);
if (p->right) postorder(p->right);
cout <<" "<<p->data <<" ";
}
elsereturn;
}
void printPreOrder()
{
cout <<"Preorder: ";
preorder(root);
cout << endl;
}
void preorder(Node* p)
{
if (p != NULL)
{
cout <<" "<<p->data <<" ";
if (p->left) preorder(p->left);
if (p->right) preorder(p->right);
}
elsereturn;
}
};
void print(Tree&k)
{
k.printPreOrder();
k.printInOrder();
k.printPostOrder();
}
void create(Tree&k)
{
int x;
cout <<"type 10 elements"<< endl;
for (int i = 0; i <10; i++)
{
cin >> x;
k.addNode(x);
}
}
Тестова програма
#include"Tree.h"
void main()
{
setlocale(LC_ALL, "Ukrainian");
Tree t1;
create(t1);
print(t1);
}
Результат тестування
На основі введених десяти чисел програма побудувала дерево та здійснила обхід у трьох напрямах, що показано на рис. 4.Вхідні дані взяті з книгиХ. М., П. Дж. Дейтела.
/
Рис. 4. Результат виконання тестової програми
ЗАСТОСУВАННЯ АТД
Завдання 1
Написати програму синтаксичного аналізу відповідностей відкриваючих і закриваючих дужок в арифметичному виразі, що має три набори дужок "(" i ")", "<" i ">", "[" i "]". Роздрукувати таблицю відповідностей дужок, причому в таблиці повинно бути зазначено, для яких дужок відсутні парні їм дужки. Для ідентифікації дужок використати їх порядкові номери у виразі.
Приклад: Для арифметичного виразу:
1 2 3 4 5 6
(a+b1)/2+6.5]*{4.8+sin(x)
має бути виведена таблиця виду:
Дужки
відкриваюча закриваюча
1 2
- 3
5 6
4 -
Прочерки в таблиці означають відсутність відповідної дужки
Опис алгоритму
Користувач вводить вираз. Для завершення введення виразу потрібно натиснути клавішу Enter. Потім ми проходимо по всьому рядку, якщо зустрічається відкриваюча дужка то ми заштовхуємо її в стек . Якщо закриваюча дужка(і стек не порожні) і якщо тип відкриваючої і закриваючої дужки співпадає то виводим ці дужки і видаляємо їх з стеку, а у випадку коли стек був порожній то на місце відкриваючої дужки ставим прочерк, виводимо закриваючу дужку і встановлюємо що балансу дужок немає.
Якщо після того як ми ввели у стек всі закриваючі дужки і вивели їх на екран а стек залишився не порожнім то на екран виводиться повідомлення що переважає кількість відкриваючих дужок. Після цього виводимо ці дужки і на
16.05.2015 18:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора