Динамічні структури даних

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Міністерство освіти і науки України

Національний університет „ Львівська політехніка ”

Кафедра ЕОМ

Розрахункова робота на тему

" Динамічні структури даних "

з дисципліни

" Обчислювальний практикум "

Варіант №7

Козак Н.Б.

Львів

2014

ТЕОРЕТИЧНА ЧАСТИНА

Абстрактний тип даних (АТД, 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)

Лінійний список - це скінчена послідовність однотипних елементів (вузлів), можливо, з повтореннями. Список розташовується в пам'яті довільним чином. Кожний вузол однонаправленого лінійного зв'язаного списку містить вказівник на наступний вузол списку, що дозволяє переміщатися вперед по списку. Кожний вузол двонаправленоголінійного зв'язаного списку містить вказівники на попередній і наступний вузли списку, що дозволяє переміщатися по списку вперед та назад.

Вставка і видалення вузлів списку реалізовані ефективно: змінюються тільки вказівники. З іншого боку, довільний доступ до вузлів списку підтримується погано: щоб прийти до певного вузла списку, треба відвідати всі попередні вузли. Крім того, на відміну від стеків або черг, додатково витрачається пам'ять під один або два вказівники на кожний елемент списку.

Список росте дуже просто: додавання кожного нового елемента приводить до того, що вказівники на попередній і наступний вузли списку, між якими вставляється новий вузол, міняють свої значення. У новому елементі таким вказівникам присвоюється значення адрес сусідніх елементів. Список використовує тільки такий об'єм пам'яті, який потрібний для наявної кількості елементів. Підтримується робота з ітератором.



Таблиця 1.4.1. Основні операції над списком

Операція	Дія
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)

має бути виведена таблиця виду:

Дужки

відкриваюча закриваюча

12

-3

56

4-

Прочерки в таблиці означають відсутність відповідної дужки

Опис алгоритму

Користувач вводить вираз. Для завершення введення виразу потрібно натиснути клавішу Enter. Потім ми проходимо по всьому рядку, якщо зустрічається відкриваюча дужка то ми заштовхуємо її в стек . Якщо закриваюча дужка(і стек не порожні) і якщо тип відкриваючої і закриваючої дужки співпадає то виводим ці дужки і видаляємо їх з стеку, а у випадку коли стек був порожній то на місце відкриваючої дужки ставим прочерк, виводимо закриваючу дужку і встановлюємо що балансу дужок немає.

Якщо після того як ми ввели у стек всі закриваючі дужки і вивели їх на екран а стек залишився не порожнім то на екран виводиться повідомлення що переважає кількість відкриваючих дужок. Після цього виводимо ці дужки і на місце закриваючих дужок ставимо прочерк. А якщо кількість закриваючих і відкриваючих дужок співпадає то програма завершує своє виконання і на екран виводиться повідомлення що баланс дужок було дотримано.

Результат виконання програми

На рис.5 показано, як програма перевіряє тип дужки у виразі та виводить результат.

Рис.5. Результат виконання тестової програми

Блок-схема алгоритму



Рис.6.Блок-схема алгоритму вирішення завдання

Завдання 2

Дано позначення двох полів шахівниці (наприклад, A5 і C2). Знайти мінімальне число ходів, які потрібні шаховому коневі для переходу з першого поля на друге.

Вказівки до розв'язання задачі: Ідея рішення ґрунтується на використанні черги. Спочатку в чергу міститься елемент, що визначає вихідне положення шахового коня, а відповідна клітка поля позначається як така, яку відвідали.

На кожному з наступних кроків алгоритму (поки черга не порожня або не позначена кінцева клітка) виконуються наступні дії.

Із черги вилучається черговий елемент, що визначає деяку позицію (x,y).

Знаходяться клітки в межах поля, які досяжні з (x,y) одним ходом шахового коня, і які ще не позначені.

Елементи, що відповідають знайденим кліткам, додаються в чергу, а клітки позначаються як такі, яких відвідали.

При цьому спочатку всі клітки повинні бути непозначені, а мітку бажано ставити таку, щоб можна було відновити шлях між полями. Для цього мітку поля можна визначити як позицію поля, з якої вона була позначена.

Опис алгоритму

Програма зчитує файл. За допомогою функції NumberOfRows рахує кількість рядків і відповідне виділяє 1/3 к-ті рядків для масивів структур buy i sell. Якщо перший символ рядка “Z”, то обраховується загальна вартість закупленої партії і елемент масиву заноситься до черги типу buy; якщо ж “P”, то множник збільшення ціни збільшується на 0,2 (20%), обраховується ціна, по якій був проданий товар, а також, за допомогою функції DigSymb, - кількість товару, проданого з кожної партії. Якщо кількість купленого товару менша, ніж кількість проданого, то сума, на яку були продані товари з кожної партії буде рівна к-ті куплених товарів, помножених на їх ціну, інакше к-ті проданих товарів, помножених на їх ціну, і в обох випадках показник загальної кількості проданих товарів збільшується на відповідну величину. Загальна сума грошей, отриманих за продані товари збільшується на суму, на яку були продані товари з кожної партії, обчислюється сума отриманого прибутку і цей елемент заноситься до черги sell.

Результат виконання програми

Результат виконання даної програми показаний на рисунку нижче (Рис.7). Як бачимо програма шукає найкоротший шлях між двома полями шахівниці.

Рис. 7. Результат виконання програми



Блок-схема алгоритму

Рис.8. Блок-схема алгоритму вирішення завдання



Завдання 3

Написати програму для роботи з розрідженими матрицями, представленими у вигляді зв'язаних списків:

Додавання двох матриць.

Опис алгоритму

Створюються дві матриці.розмір матриці задається в самому коді програми,в даному випадку наша матриця розміру 5:4. Далі відбуваєть занулення всіх елементів кожної матриці а деяким окремим елементам надається якесь значення. Сьворюємо об'єкти R_Matrix.

bool R_Matrix::AddR_Matrix - функція яка додає дві матриці.вона проходить по всій матриці і ненульові координати заносить в список.

R_Matrix res-функція яка виводить результат додавання двох матриць.

bool R_Matrix::Check-функція яка шукає потрібну нам координату в списку для додавання.

Спочатку на екран виводяться дві матриці а потім результат додавання матриць.

Результат виконання програми

Із скріншота нижче (рис. 9), маємо результат додавання матриці:

Рис. 9. Результат виконання програми



Блок-схема алгоритму

Рис. 10. Блок-схема алгоритму розв'язання задачі



Завдання 4

N кісточок доміно за правилами гри викладаються в прямий ланцюжок, починаючи з кісточки, обраної довільним чином, в обидва кінці доти, поки це можливо. Змоделювати гру в доміно і написати програму

а) побудови самого довгого ланцюжка;

б) знаходження такого варіанта викладання кісточок, при якому до моменту, коли ланцюжок не можна далі продовжити, "на руках" залишиться максимальне число очок.

Приклад: Вхідні дані Результат

N= 5 5

1 2 56:62:21:13:36

1 3

2 6

3 6

5 6

Опис алгоритму

Користувач вводить послідовність. Далі за допомогою кількох функцій будується послідовність коли послідовність побудована ми перевертаємо фішки та знову будуємо послідовність.

ArrayReverse-функція яке перевертає фішки.

TryAppend-функція яка додає нову фішку до послідовності.

CanContinue-функція яка перевіряє чи можливе продовження побудови послідовності.

ComputeSum-функція яка визначає суму на фішках які невикористані.

На екран виводиться максимальна довжина послідовності фішок та максимальна сума на фішках які залишаються після побудови послідовності.

Результат виконання програми

Як видно із скріншота (рис.11), послідовність успішно побудована.

Рис. 11. Результат виконання програми



Блок-схема алгоритму

Рис. 12. Блок-схема алгоритму розв'язання задачі

стек список програма дані



ВИСНОВКИ

Виконуючи дану розрахункову роботу, я ознайомився із динамічними структурами даних, зокрема стеком, чергою, списком та деревом, удосконалив свої знання щодо створення та написання алгоритмів, навчився реалізовувати основні методи даних АТД, застосовувати їх до розв'язання різноманітних задач.



СПИСОК ЛІТЕРАТУРИ

Х. М. Дейтел, П. Дж. Дейтел Как программировать на С++: Пятое издание. Пер. с англ. -- М.: ООО «Бином-Пресс», 2008 г. -- 1456 с.: ил.

Cormen T. H., C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Second Edition, Prentice Hall of India Pvt. Ltd., New Delhi, 2003.

Deo N., GraphTheorywithApplication to Engineering and Computer Science, Prentice Hall of India Pvt. Ltd., New Delhi, 2000.

Horowitz E., S. Sahni and S. Rajasekaran, Computer Algorithms, Galgotia Publications Pvt. Ltd., New Delhi, 2004.

Knuth D. E., The Art of Computer Programming (Volume 1): Fundamental Algorithms, Third Edition, Addition Wesley: An Imprint of Pearson Education, Delhi, 2002.

Седжвик Роберт,Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск, 2001.

ГОСТ 19.701-90

http://interactivepython.org/runestone/static/pythonds/index.html#basic-data-structures

Лисак Т.А., Методичні вказівки до лабораторної роботи "Структура даних "БІНАРНЕ ДЕРЕВО ПОШУКУ"" з дисципліни «Програмування. Частина IIІ»для підготовки студентів напрямку 6.0915 “Комп'ютерна інженерія”/
Львів: Видавництво НУ “Львівська політехніка”, 2010 - 16 с.



ДОДАТОК А. КОД ПРОГРАМИ ДО ЗАВДАННЯ 1

#include <iostream>

#include <string>

#include "stack.h"

using namespace std;

int main()

{

setlocale(0, "Ukr");

string str;

cout << "Введiть вираз: ";

cin >> str;

bool is = true;

Stack<char> st;

for (unsigned i = 0; i < str.size(); ++i)

{

if (str[i] == '(' || str[i] == '[' || str[i] == '<')

{

st.push(str[i]);

continue;

}

if (str[i] == ')' || str[i] == ']' || str[i] == '>')

{

if (!st.empty()){

if ( (str[i] == ')' && st.top() == '(') || (str[i] == '>' && st.top() == '<') || (str[i] == ']' && st.top() == '['))

{

cout << st.top() << '\t' << str[i] << endl;

st.pop();}

else

{

cout << "-\t" << str[i] << endl;

is = false;

}

}

else

{

cout << "-\t" << str[i] << endl;

is = false;

}

}

}

string msg;

if (!st.empty())

{

is = false;

msg = "Переважає кiлькiсть вiдкриваючих дужок.\n";

}

else

msg = "Переважає кiлькiсть закриваючих дужок.\n";

while (!st.empty())

{

cout << st.top() << '\t' << "-\n";

st.pop();

}

if (is)

cout <<"Баланс дужок дотримано.\n";

else

cout << msg;

system("pause");

return 0;

}



ДОДАТОК Б. КОД ПРОГРАМИ ДО ЗАВДАННЯ 2

#include <iostream>

#include <vector>

#include <limits>

#include <string>

#include <algorithm>

#include <queue>

using namespace std;

int main(){

int n = 8;

//cin >> n;

int x[8] = {1, 1, -1, -1, 2, 2, -2, -2};

int y[8] = {2, -2, 2, -2, 1, -1, 1, -1};

queue <pair<int, int> > q;

pair <int, int> start, end, temp, nan = make_pair(-1, -1);

vector <vector <pair<int, int> > > p(n, vector <pair<int, int> > (n, nan));

cout << "Enter two rect: ";

char ch1, ch2;

cin >> ch1 >> start.second >> ch2 >> end.second;

start.first = ch1 - 'A';

end.first = ch2 - 'A';

q.push(start);

p[start.first][start.second] = start;

while (!q.empty()) {

temp = q.front();

q.pop();

if (temp == end) {

cout << "The way is : \n";

vector <pair <int, int> > way;

while (temp != start) {

way.push_back(temp);

temp = p[temp.first][temp.second];

}

way.push_back(start);

for (int i = way.size() - 1; i >= 0; i--) {

cout << (char) (way[i].first + 'A') << way[i].second << " ";

}

cout << endl;

system("pause");

return 0;

}

for (int i = 0; i < 8; i++) {

int nx = temp.first + x[i];

int ny = temp.second + y[i];

if (nx >= 0 && ny >= 0 && nx < n && ny < n && p[nx][ny] == nan) {

p[nx][ny] = temp;

q.push(make_pair(nx, ny));

}

}

}

cout << "No way";

cout << endl;

system("pause");

return 0;

}



ДОДАТОК В. КОД ПРОГРАМИ ДО ЗАВДАННЯ 3

#include <iostream>

#include <list>

using namespace std;

typedef int UserType;

struct data

{

UserType val;

unsigned i;

unsigned j;

};

class R_Matrix

{

private:

list<data> lst;

unsigned rows;

unsigned columns;

bool Check(const unsigned i, const unsigned j) const;

public:

R_Matrix();

R_Matrix(UserType **mtr, const unsigned columns, const unsigned rows);

R_Matrix(const R_Matrix &mtr);

~R_Matrix();

bool AddR_Matrix(UserType **mtr, const unsigned columns, const unsigned rows);

R_Matrix operator+(const R_Matrix &mtr);

void operator=(const R_Matrix &mtr);

friend ostream & operator<<(ostream & os, const R_Matrix &mtr);

};

R_Matrix::R_Matrix()

{

this->rows = 0;

this->columns = 0;

}

R_Matrix::R_Matrix(UserType **mtr, const unsigned columns, const unsigned rows)

{

this->rows = rows;

this->columns = columns;

data dt;

for (unsigned i = 0; i < this->columns; ++i)

for (unsigned j = 0; j < this->rows; ++j)

{

if (mtr[i][j])

{

dt.i = i;

dt.j = j;

dt.val = mtr[i][j];

lst.push_back(dt);

}

}

}

R_Matrix::R_Matrix(const R_Matrix &mtr)

{

this->lst = mtr.lst;

this->columns = mtr.columns;

this->rows = mtr.rows;

}

R_Matrix::~R_Matrix()

{

}

bool R_Matrix::AddR_Matrix(UserType **mtr, const unsigned columns, const unsigned rows)

{

this->rows = rows;

this->columns = columns;

data dt;

for (unsigned i = 0; i < this->columns; ++i)

for (unsigned j = 0; j < this->rows; ++j)

{

if (mtr[i][j])

{

dt.i = i;

dt.j = j;

dt.val = mtr[i][j];

lst.push_back(dt);

}

}

return true;

}

bool R_Matrix::Check(const unsigned i, const unsigned j) const

{

list<data>::const_iterator c_itr;

for (c_itr = this->lst.cbegin(); c_itr != this->lst.cend(); c_itr++) списку

{

if ( (*c_itr).i == i && (*c_itr).j == j)

return true;

}

return false;

}

R_Matrix R_Matrix::operator+(const R_Matrix &mtr)

{

R_Matrix res(*this);

list<data>::const_iterator c_itr;

for (c_itr = mtr.lst.cbegin(); c_itr != mtr.lst.cend(); c_itr++)

{

if (Check( (*c_itr).i, (*c_itr).j))

for (list<data>::iterator itr = res.lst.begin(); itr != res.lst.end(); itr++)

{

if ( (*itr).i == (*c_itr).i && (*itr).j == (*c_itr).j)

{

(*itr).val += (*c_itr).val;

}

}

else

{

data dt;dt.i = c_itr->i;

dt.j = c_itr->j;

dt.val = c_itr->val;

res.lst.push_back(dt);

}

}

return res;

}

void R_Matrix::operator=(const R_Matrix &mtr)

{

this->lst = mtr.lst;

this->columns = mtr.columns;

this->rows = mtr.rows;

}

ostream & operator<<(ostream & os, const R_Matrix &mtr)

{

for (unsigned i = 0; i < mtr.columns; ++i)

{

for (unsigned j = 0; j < mtr.rows; ++j)

{

if (! mtr.Check(i, j))

os << "0 ";

else

{

for (list<data>::const_iterator c_itr = mtr.lst.cbegin(); c_itr != mtr.lst.cend(); c_itr++)

{

if (i == c_itr->i && j == c_itr->j)

os << c_itr->val << " ";

}

}

os << endl;

}

return os;

}

int main()

{

const unsigned n = 5;

const unsigned m = 4;

UserType **mtr1;

UserType **mtr2;

#pragma region

mtr1 = new UserType*[n];mtr2 = new UserType*[n];

for (int i = 0; i < n; ++i)

{

mtr1[i] = new UserType[m];

mtr2[i] = new UserType[m];

}

#pragma endregion

#pragma region

for (int i = 0; i < n; ++i)

for (int j = 0; j < m; ++j)

{

mtr1[i][j] = 0;

mtr2[i][j] = 0;

}

mtr1[0][2] = 4;

mtr1[0][1] = 3;

mtr1[1][3] = 1;

mtr1[3][2] = 7;

mtr1[4][0] = 3;

mtr1[3][1] = 2;

mtr2[0][0] = 12;

mtr2[0][3] = 5;

mtr2[2][3] = 2;

mtr2[3][3] = 15;

mtr2[4][0] = 3;

#pragma endregion

R_Matrix r_mtr1(mtr1, n, m);

R_Matrix r_mtr2;

r_mtr2.AddR_Matrix(mtr2, n, m);

R_Matrix res;

res = r_mtr1 + r_mtr2;

cout << "Firs matrix: " << endl << r_mtr1 << endl;

cout << "Second matrix: " << endl << r_mtr2 << endl;

cout << "Result matrix: " << endl << res << endl;

system("pause");

return 0;

}



ДОДАТОК Г. КОД ПРОГРАМИ ДО ЗАВДАННЯ 4

#include <iostream>

#include <string>

using namespace std;

struct Domino{

int left,right;

};

struct DominoSeq{

Domino* seq;

int count;

int length;

int sum;

};

static DominoSeq maxLength;

static DominoSeq maxSum;

//ф-ція визначення суми на фішках, що не використані

int ComputeSum(Domino* pack, int* usingDomino, int count){

int sum=0;

for (int i = 0; i < count; i++)

{

if(usingDomino[i]==0)

sum+=pack[i].left + pack[i].right;

}

return sum;

}

void PrintDominoSeq(DominoSeq ds){

cout<<" Послiдовнiсть - ";

for(int i = 0; i<ds.length; i++)

cout<<ds.seq[i].left<<"|"<<ds.seq[i].right<<" ";

cout<<endl;

}

//ф-ції перевірки та додання нової фішки до послідовності

int TryAppend(Domino a, Domino b){

if(a.right==b.left || a.right == b.right)

return 1;

return 0;

}

void Append(Domino* pack, int a, int b, int* usingDomino, DominoSeq &ds){

if(pack[a].right == pack[b].right){

int tmp = pack[b].left;

pack[b].left = pack[b].right;

pack[b].right = tmp;

}

ds.seq[ds.length++]=pack[b];

usingDomino[b]=1;

}

//перевірка можливості продовження

int CanContinue(Domino* pack, int startDominoIndex, int* usingDomino, int count){

for(int i=0; i<count; i++)

if(usingDomino[i]!=1 && i!=startDominoIndex && TryAppend(pack[startDominoIndex],pack[i]))

return 1;

return 0;

}

void Compute(Domino* pack, int startDominoIndex, int* usingDomino, int count, DominoSeq &ds){

for(int j=0; j<count; j++){

if(!CanContinue(pack, startDominoIndex, usingDomino, count)){

if(ds.length>maxLength.length)

maxLength=ds;

ds.sum=ComputeSum(pack,usingDomino,count);

if(ds.sum>maxSum.sum)

maxSum=ds;

}

if(j==startDominoIndex)

continue;

if(usingDomino[j]!=1 && TryAppend(pack[startDominoIndex],pack[j])){

int* tmpUsingDomino = new int[count];

memcpy(tmpUsingDomino,usingDomino,count*sizeof(int));

Domino* tmpDominoPack = new Domino[count];//так як фішки можуть обертатися (2|3 -> 3|2) потрібно зберігати проміжні масивии фішок

memcpy(tmpDominoPack,pack,count*sizeof(Domino));

DominoSeq tmpDS;

tmpDS.count = count;

tmpDS.length = ds.length;

tmpDS.seq = new Domino[count];//зберігання поточної послідовності фішок

memcpy(tmpDS.seq,ds.seq,count*sizeof(Domino));

Append(tmpDominoPack, startDominoIndex, j, tmpUsingDomino, tmpDS);

Compute(tmpDominoPack, j, tmpUsingDomino, count, tmpDS);

}

}

}

void ArrayReverse(Domino* pack, int count){ //поворот масиву фішок

for (int i = 0; i < count; i++)

{

int tmp = pack[i].left;

pack[i].left = pack[i].right;

pack[i].right = tmp;

}

}

int main()

{

setlocale(0,".1251");

int count=0;

cin>>count;

Domino* pack = new Domino[count];

for (int i = 0; i < count; i++)

cin>>pack[i].left>>pack[i].right;

maxLength.length=0;

maxSum.sum=-1;

for(int steps=0;steps<2;steps++){

for (int i = 0; i < count; i++)

{

//ініціалізація масиву використаних фішок

int* usingDomino = new int[count];

for(int j=0; j<count; j++)

usingDomino[j]=0;

usingDomino[i]=1;

//-----

DominoSeq ds;

ds.count=count;

ds.seq = new Domino[count];

ds.length=1;

ds.sum = ComputeSum(pack, usingDomino, count);

ds.seq[0]=pack[i];

Compute(pack, i, usingDomino, count, ds);

delete[] usingDomino;

}

//поворот перших фішок та повтор

ArrayReverse(pack,count);

}

cout<<"Макс. довжина : "<<maxLength.length;

PrintDominoSeq(maxLength);

cout<<"Макс. сума : "<<maxSum.sum;

PrintDominoSeq(maxSum);

delete[] pack;

system("pause");

return 0;

}

Размещено на Allbest.ru