Материал: Динамічні структури даних

Реалізація списку

-List.h--

#include<iostream>std;

{:

{

int value; // певна інформативна частина* next; // вказівник на наступну структуру-вузол у списку

};* head = NULL; // вказівник на голову списку

public:addToBegin(intv)

{* n = newNode;>value = v;>next = head;= n;

}addToEnd(intv)

{* n;(!head)

{= newNode;>value = v;>next = NULL;;

}

{= head;(n->next)= n->next;* newNode = newNode;>value = v;>next = NULL;>next = newNode;;

}

}deleteNode(Node * n)

{<<"Видаляємо елемент "<<n->value << endl;* k = head;(head == n)

{;= NULL;;

}(k->next != n)= k->next;>next = n->next;;

}insert(constintv, Node * n)

{* newNode = newNode;>value = v;>next = n->next;>next = newNode;

}* find(constintv)

{* n = head;(n)

{(n->value == v)n;= n->next;

};

}Show()

{<<"Список зараз : ";*n = head;(n != NULL)

{<< n->value <<" ";= n->next;

}<< endl;

}reverse()

{<<"Iнверсiя списку: ";*temp, *tmp, *var;= head;= NULL;(temp != NULL)

{= var;= temp;= temp->next;>next = tmp;

}= var;

}

};

Тестова програма

void main()

{(LC_ALL, "Ukrainian");list;N, p;<<"Введiть число N"<< endl;>> N;<<"Введiть "<< N <<" елементiв"<< endl;(int i = 0; i < N; i++)

{>> p;.addToEnd(p);.Show();

}.deleteNode(list.find(10));.deleteNode(list.find(25));.Show();.reverse();.Show();("pause");

}

Результат тестування

На рисунку 3. показано динаміку вмісту списку при внесенні до нього елемента. Як бачимо, елемент додається у кінець списку. Результат виконання методів видалення елементів та інвертування списку також продемонстровано на даному рисунку.

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

Абстрактний тип даних «Дерево»

Змоделювати АТД «Дерево». Оформити АТД у вигляді класу. Переписати основні операції роботи з АТД і продемонструвати їх застосування при додаванні та вилученні елементів з АТД.

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

Реалізація дерева

-Tree.h--

#include<iostream>std;

{:{data;*left;*right;

};*p;k;*root;:() {root = NULL; }

~Tree() { clear(); }* getRoot() { return root; }isEmpty() const { return root == NULL; }addNode(intd)

{* t = newNode;*parent;>data = d;>left = NULL;>right = NULL;= NULL;(isEmpty())= t;

{*current;= root;(current)

{= current;((t->data) > (current->data))= current->right;= current->left;

}(t->data < parent->data)>left = t;>right = t;

}

}clear() { recursive_delete(root); }recursive_delete(Node* node)

{(node != NULL)

{_delete(node->left);_delete(node->right);(node);

}

}deleteNode(Node* node)

{;= NULL;

}printInOrder()

{<<"Inorder: ";(root);<< endl;

}inorder(Node* p)

{(p != NULL)

{(p->left)(p->left);<<" "<<p->data <<" ";(p->right)(p->right);

};

}printPostOrder()

{<<"Postorder: ";(root);<< endl;

}postorder(Node* p)

{(p != NULL)

{(p->left) postorder(p->left);(p->right) postorder(p->right);<<" "<<p->data <<" ";

};

}printPreOrder()

{<<"Preorder: ";(root);<< endl;

}preorder(Node* p)

{(p != NULL)

{<<" "<<p->data <<" ";(p->left) preorder(p->left);(p->right) preorder(p->right);

};

}

};print(Tree&k)

{.printPreOrder();.printInOrder();.printPostOrder();

}create(Tree&k)

{x;<<"type 10 elements"<< endl;(int i = 0; i <10; i++)

{>> x;.addNode(x);

}

}

Тестова програма

#include"Tree.h"

void main()

{(LC_ALL, "Ukrainian");t1;(t1);(t1);

}

Результат тестування

На основі введених десяти чисел програма побудувала дерево та здійснила обхід у трьох напрямах, що показано на рис. 4.Вхідні дані взяті з книгиХ. М., П. Дж. Дейтела.

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

ЗАСТОСУВАННЯ АТД

Завдання 1

Написати програму синтаксичного аналізу відповідностей відкриваючих і закриваючих дужок в арифметичному виразі, що має три набори дужок "(" i ")", "<" i ">", "[" i "]". Роздрукувати таблицю відповідностей дужок, причому в таблиці повинно бути зазначено, для яких дужок відсутні парні їм дужки. Для ідентифікації дужок використати їх порядкові номери у виразі.

Приклад: Для арифметичного виразу:

2 3 4 5 6

(a+b1)/2+6.5]*{4.8+sin(x)

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

Дужки

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

-

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

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

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

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

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

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

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

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

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

Дано позначення двох полів шахівниці (наприклад, 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.R_Matrix::AddR_Matrix - функція яка додає дві матриці.вона проходить по всій матриці і ненульові координати заносить в список._Matrix res-функція яка виводить результат додавання двох матриць.R_Matrix::Check-функція яка шукає потрібну нам координату в списку для додавання.

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

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

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

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

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

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

Завдання 4

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

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

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

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

2 56:62:21:13:36

3

6

6

6

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

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

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

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

Як видно із скріншота (рис.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.N., GraphTheorywithApplication to Engineering and Computer Science, Prentice Hall of India Pvt. Ltd., New Delhi, 2000.E., S. Sahni and S. Rajasekaran, Computer Algorithms, Galgotia Publications Pvt. Ltd., New Delhi, 2004.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://interactivepython.org/runestone/static/pythonds/index.html#basic-data-structures

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

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

#include <iostream>

#include <string>

#include "stack.h"namespace std;main()

{(0, "Ukr");str;<< "Введiть вираз: ";>> str; is = true;<char> st; (unsigned i = 0; i < str.size(); ++i)

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

{.push(str[i]); ;

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

{(!st.empty()){( (str[i] == ')' && st.top() == '(') || (str[i] == '>' && st.top() == '<') || (str[i] == ']' && st.top() == '['))

{<< st.top() << '\t' << str[i] << endl; .pop();}

{<< "-\t" << str[i] << endl; = false;

}

}

{<< "-\t" << str[i] << endl; = false;

}

}

}msg;(!st.empty())

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

}= "Переважає кiлькiсть закриваючих дужок.\n";(!st.empty())

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

}(is)<<"Баланс дужок дотримано.\n";<< msg;("pause");

return 0;

}

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

#include <iostream>

#include <vector>

#include <limits>

#include <string>

#include <algorithm>

#include <queue>namespace std;main(){ n = 8;

//cin >> n;x[8] = {1, 1, -1, -1, 2, 2, -2, -2};y[8] = {2, -2, 2, -2, 1, -1, 1, -1};<pair<int, int> > q;<int, int> start, end, temp, nan = make_pair(-1, -1);<vector <pair<int, int> > > p(n, vector <pair<int, int> > (n, nan));<< "Enter two rect: ";ch1, ch2;>> ch1 >> start.second >> ch2 >> end.second;.first = ch1 - 'A';.first = ch2 - 'A';.push(start);[start.first][start.second] = start;(!q.empty()) {= q.front();.pop();(temp == end) {<< "The way is : \n";<pair <int, int> > way;(temp != start) {.push_back(temp);= p[temp.first][temp.second];

}.push_back(start);(int i = way.size() - 1; i >= 0; i--) {<< (char) (way[i].first + 'A') << way[i].second << " ";

}<< endl;("pause");0;

}(int i = 0; i < 8; i++) {nx = temp.first + x[i];ny = temp.second + y[i];(nx >= 0 && ny >= 0 && nx < n && ny < n && p[nx][ny] == nan) {[nx][ny] = temp;.push(make_pair(nx, ny));

}

}

}<< "No way";<< endl;

system("pause");0;

}

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

#include <iostream>

#include <list>namespace std;int UserType; data

{val;i;j;

};R_Matrix

{:<data> lst; rows; columns;Check(const unsigned i, const unsigned j) const; :_Matrix(); _Matrix(UserType **mtr, const unsigned columns, const unsigned rows); _Matrix(const R_Matrix &mtr);

~R_Matrix(); AddR_Matrix(UserType **mtr, const unsigned columns, const unsigned rows); _Matrix operator+(const R_Matrix &mtr); operator=(const R_Matrix &mtr); ostream & operator<<(ostream & os, const R_Matrix &mtr);

};_Matrix::R_Matrix()

{>rows = 0;>columns = 0;

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

{>rows = rows;>columns = columns;dt;(unsigned i = 0; i < this->columns; ++i) (unsigned j = 0; j < this->rows; ++j)

{(mtr[i][j])

{.i = i;.j = j;.val = mtr[i][j];.push_back(dt);

}

}

}_Matrix::R_Matrix(const R_Matrix &mtr)

{>lst = mtr.lst; >columns = mtr.columns;>rows = mtr.rows;

}_Matrix::~R_Matrix()

{

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

{>rows = rows; >columns = columns;dt;(unsigned i = 0; i < this->columns; ++i) (unsigned j = 0; j < this->rows; ++j)

{(mtr[i][j])

{.i = i;.j = j;.val = mtr[i][j];.push_back(dt);

}

}true;

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

{<data>::const_iterator c_itr; (c_itr = this->lst.cbegin(); c_itr != this->lst.cend(); c_itr++) списку

{( (*c_itr).i == i && (*c_itr).j == j) true;

}false;

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

{_Matrix res(*this); <data>::const_iterator c_itr; (c_itr = mtr.lst.cbegin(); c_itr != mtr.lst.cend(); c_itr++)

{(Check( (*c_itr).i, (*c_itr).j)) (list<data>::iterator itr = res.lst.begin(); itr != res.lst.end(); itr++)

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

{

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

}

}

{dt;dt.i = c_itr->i;.j = c_itr->j;.val = c_itr->val;.lst.push_back(dt);

}

}res;

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

{>lst = mtr.lst; >columns = mtr.columns;>rows = mtr.rows;