МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” / Кафедра ЕОМ " Список" ЗВІТ до лабораторної роботи № 6 з "Програмування. Частина III. Структури даних та алгоритми" МЕТА РОБОТИ Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач. ВИБІР ІНДИВІДУАЛЬНОГО ЗАВДАННЯ Змоделюйте чергу (або дек) згідно з завданням. Перепишіть основні операції для роботи з чергою (деком), і продемонструйте їх застосування для операцій додавання і вилучення елементів в чергу (дек). Для цього задайте послідовність з N цілих чисел. Всі додатні числа послідовно заносяться в чергу (дек), кожне від’ємне число вилучає з черги (деку) один елемент (при роботі з деком, парні числа працюють з одним кінцем деку, а непарні – з іншим). Показувати всі зміни, що будуть відбуватись у черзі (деку). Перша літера П (11)-> I 9 Перша літера прізвища  Номер студента в списку групи Варіант А, І, С Б, Ї, Т В, Й, У Г, К, Ф Д, Л, Х Е, М, Ц Є, Н, Ч Ж,О,Ш,Щ З, П, Ю И, Р, Я   10, 20, 30 І1 І2 І3 І4 І5 І6 І7 І8 І9 І10   9, 19, 29 І1 І2 І3 І4 І5 І6 І7 І8 І9 І10   8, 18, 28 І1 І2 І3 І4 І5 І6 І7 І8 І9 І10   7, 17, 27 І1 І2 І3 І4 І5 І6 І7 І8 І9 І10   6, 16, 26 І1 І2 І3 І4 І5 І6 І7 І8 І9 І10   5, 15, 25 І1 І2 І3 І4 І5 І6 І7 І8 І9 І10   4, 14, 24 І1 І2 І3 І4 І5 І6 І7 І8 І9 І10   3, 13, 23 І1 І2 І3 І4 І5 І6 І7 І8 І9 І10   2, 12, 22 І1 І2 І3 І4 І5 І6 І7 І8 І9 І10   1, 11, 21 І1 І2 І3 І4 І5 І6 І7 І8 І9 І10   9. Написати програму, яка будує лінійний зв’язаний список, що містить N великих букв латинського алфавіту, які задаються випадковим чином, і перевіряє, чи перший елемент списку містить букву “А”, якщо це так, то додається ще одна буква “А” в кінець списку, якщо ні – то зі списку вилучаються всі букви “А”. Вивести отриманий результат. (Примітка: великі букви латинського алфавіту в таблиці ASCII мають номери від 65 до 90 ). Код програми List.h #pragma once #include <iostream> using namespace std; template <class T> class List { private: struct Element { T data; Element *next; Element *prev; }; Element *begin; Element *end; int length; public: List(); // instead init() ~List(); // clear() bool contains(T); bool isEmpty(); int size(); void push_front(T); void push_back(T); void push_after(T, T); void push_before(T, T); void delFromData(T); void printStraight(); void printReverse(); void clear(); void taskVar9(); }; template <class T> List<T>::List() { begin = NULL; end = NULL; length = 0; } template <class T> List<T>::~List() { clear(); } template <class T> bool List<T>::isEmpty() { return begin == NULL; } template <class T> int List<T>::size() { return length; } template <class T> void List<T>::delFromData(T newData) { if (!isEmpty()) { if (newData == begin->data && begin->next) { Element *temp = begin; begin = begin->next; begin->prev = NULL; delete temp; length--; return; } else if (newData == begin->data && begin == end) { begin->next = begin->prev = begin = NULL; delete begin; length = 0; return; } if (newData == end->data) { Element *temp = end; end = end->prev; end->next = NULL; delete temp; length--; return; } Element *temp = begin; while (temp) { if (temp->data == newData) { temp->prev->next = temp->next; temp->next->prev = temp->prev; delete temp; length--; break; } temp = temp->next; } } else cout << "\nList is empty" << endl; } template <class T> void List<T>::push_back(T data) { Element *temp = new Element; temp->next = NULL; temp->data = data; if (!isEmpty()) { temp->prev = end; end->next = temp; end = temp; } else { temp->prev = NULL; begin = end = temp; } length++; } template <class T> void List<T>::push_front(T data) { Element *temp = new Element; temp->prev = NULL; temp->data = data; if (!isEmpty()) { temp->next = begin; begin->prev = temp; begin = temp; } else { temp->next = NULL; begin = end = temp; } length++; } template <class T> void List<T>::push_after(T adr, T newData) { if (!isEmpty()) { Element *t = begin; Element *newEl = new Element; while (t) { if (t->data == adr) { newEl->data = newData; newEl->next = t->next; t->next->prev = newEl; t->next = newEl; newEl->prev = t; length++; return; } t = t->next; } cout << "The arddess didn't found" << endl; } } template <class T> void List<T>::push_before(T adr, T newData) { if (!isEmpty()) { Element *t = begin; Element *newEl = new Element; while (t) { if (t->data == adr) { newEl->data = newData; newEl->next = t; newEl->prev = t->prev; t->prev->next = newEl; t->prev = newEl; length++; return; } t = t->next; } cout << "The arddess didn't found" << endl; } } template <class T> void List<T>::printStraight() { if (!isEmpty()) { Element *tempCar = begin; for (int i = 0; i < length; i++) { cout << tempCar->data << " "; tempCar = tempCar->next; } cout << "\n"; } else cout << "List is empty\n"; } template <class T> void List<T>::printReverse() { if (!isEmpty()) { Element *tempCar = end; for (int i = 0; i < length; i++) { cout << tempCar->data << " "; tempCar = tempCar->prev; } cout << "\n"; } else cout << "List is empty\n"; } template <class T> void List<T>::clear() { if (isEmpty()) return; Element *p = begin; Element *t; while (p) { t = p; p = p->next; delete t; } begin = end = NULL; length = 0; } template <class T> bool List<T>::contains(T data) { if (!isEmpty()) { Element *tempCar = begin; for (int i = 0; i < length; i++) { if (tempCar->data == data) return true; tempCar = tempCar->next; } } return false; } template <class T> void List<T>::taskVar9() { if (!isEmpty()) { if (begin->data == 'A') push_back('A'); else while (contains('A')) delFromData('A'); } else cout << "List is empty!"; } Source.cpp #include <ctime> #include "List.h" using namespace std; int main() { srand(time(0)); List<char> l; int N = 0; cout << "Input nuber of elements: "; cin >> N; for (int i = 0; i < N; i++) l.push_back(rand()%(90 - 65+ 1) + 65); cout << "Print list: "; l.printStraight(); cout << "Print reverse list: "; l.printReverse(); cout << "Add S after F\n"; l.push_after('F', 'S'); cout << "Add H before S\n"; l.push_before('S', 'H'); cout << "Print list: "; l.printStraight(); cout << "Delete S, H from list\n"; l.delFromData('S'); l.delFromData('H'); cout << "Print list: "; l.printStraight(); cout << "Size of list: " << l.size() << endl; cout << "\nExecuting task according to variant 9\n"; l.taskVar9(); cout << "Print list: "; l.printStraight(); getchar(); getchar(); return 0; } Скріншот виконання / Висновок На даній лабораторній роботі я набув практичних навичок побудови черги, дослідив динаміку його вмісту та використання для розв'язання прикладних задач.