НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №5 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «Лінійні однозв’язні та двозв’язні списки» Варіант № 15 Дата « 12 » червня 2022 Мета роботи: Метою лабораторної роботи є ознайомитися з основами роботи з двозв’язним списком, однозв’язним списком, стеком та чергою. Теоретична частина: Однозв'язний список — вид зв’язного списку, який складається з вузлів, кожен з яких містить у собі дані (інформаційну частину) та посилання на наступний вузол. / Двобічно зв'язаний список — вид зв’язного списку, у якому посилання в кожному вузлі вказують на попередній і на подальший вузол у списку. Якщо в списку після останнього елемента йде перший, то такий список називається кільцевим двобічно зв'язаним списком. Тобто, поле prev голови списку вказує на хвіст списку, а поле next хвоста списку вказує на голову списку. По двобічно зв'язаному списку можна пересуватися в будь-якому напрямку — як від початку до кінця, так і навпаки. Для нього простіше проводити видалення і перестановку елементів, оскільки завжди відомі адреси тих елементів списку, вказівник яких спрямований на змінюваний елемент. / Найчастіше вузлом списку вважають структурний тип (структуру), який зберігає у собі певну інформаційну частину (іншу структуру або тип даних) та посилання (вказівник) на наступний вузол у списку. Список має «голову», тобто вказівник на початок списку та інколи має кінець, проте найчастіше його не використовують. Мабуть найголовнішою перевагою списку є набагато зручніша робота із динамікою. Наприклад, при створенні динамічного масиву, коли місце у ньому кінчається приходиться копіювати всі елементи, свторювати новий, більший за розміром, а старий видаляти. У спискам набагато зручніше додавати нові елементи. Але в той же час, його набагато складніше контролювати у порівнянні із звичайним масивом. Стек являє собою об’єкт, робота з яким – додавання і видалення – здійснюється за принципом LIFO (last-in first-out – останнім прийшов – першим пішов). Додавання об’єктів в стек може здійснюватися в будь-який момент, видаляється ж лише об’єкт, доданий останнім. / Черга (queue) – лінійний список, у якому всі видалення відбуваються на одному кінці списку, а всі включення (і звичайно всякий доступ) робляться на іншому його кінці. Інакше кажучи, у черги є голова (head) і хвіст (tail). Елемент, що додається в чергу, виявляється в її хвості У черзі новий елемент додається тільки з одного кінця. Видалення елемента відбувається на іншому кінці. Черга (queue), це по суті однонаправлений список, тільки додавання й видалення елементів відбувається на кінцях списку. / Завдання роботи: 1. Створити лінійний однозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та настуні поміняти місцями. Виконати завдання згідно варіанту. 2. Створити двозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його. Виконати завдання згідно варіанту з двозвязним спмском. / Результат: Заповнити стек можна за допомогою меню, натискаючи кнопку 1 – вам запропонують ввести елемент який потрібно покласти в стек. За допомогою кнопки 2, у вас буде можливість порівняти суму від’ємних та додатніх чисел у стеку. А за допомогою клавіші 3 – ви зможете роздрукувати стек у консоль. Клавіша 0 – вихід із програми. / / Посилання на Replit: https://replit.com/join/dkxvcxvkts-tr-15fundamient Висновок: Під час виконання даної лабораторної роботи ознайомлено на практиці з роботою з однозв’язними та двозв’язними списками, стеком та чергою. У результаті виконання роботи було написано реалізацію стеку, та реалізацію завдання, відповідного до много варіанту. Усе працює згідно вимог. Копія коду: #include<iostream> #include <math.h> using namespace std; struct Node { int data; struct Node* next; }; struct Node* head; class stack { int size; public: void push(struct Node New); struct Node pop(); int isEmpty(); stack(); void print(); int positiveSum(); int negativeSum(); int getsize(); }; int stack::getsize(){return size;} void stack::print() { struct Node* temp = head; if (head == NULL) cout << "Stack is empty!"; else { cout << head->data << " "; while (temp->next != NULL) { temp = temp->next; cout << temp->data << " "; } } cout << endl; } int stack::isEmpty() { return (head == NULL ? 1 : 0); } void stack::push(struct Node New) { if (isEmpty()) { head = new struct Node; head->data = New.data; head->next = NULL; } else { struct Node *temp = head; while (temp->next != NULL) temp = temp->next; struct Node *t = new struct Node; t->data = New.data; t->next = NULL; temp->next = t; } size++; } int stack::positiveSum() { if (isEmpty()) { return -1; } else { int sum = 0; struct Node *temp = head; while(temp != NULL) { if(temp->data > 0) { sum += temp->data; } temp = temp->next; } return sum; } } int stack::negativeSum() { if (isEmpty()) { return -1; } else { int total = 0; struct Node *temp = head; while(temp != NULL) { if(temp->data < 0) { total += fabs(temp->data); } temp = temp->next; } return total; } } struct Node stack::pop() { size--; if (!isEmpty()) { struct Node* temp = head; struct Node temp2; if (temp->next == NULL) { struct Node t = *head; head = NULL; return t; } else { while (temp->next->next != NULL) temp = temp->next; temp2 = *temp->next; temp->next = NULL; return temp2; } } else cout << "Stack is empty.\n"; } stack::stack() { head = NULL; size=0; } int main() { stack s; int ch = 1; while (ch != 0) { struct Node temp; int num, sumPos, sumNeg; cout << "Stack:\n1.Push\n2.Compare sum of negative and positive number\n3.Print stack.\n0.Exit\n"; cin >> ch; switch (ch) { case 0: return 0; case 1: cout << "Enter a num to push "; cin >> num; temp.data = num; s.push(temp); break; case 2: sumPos = s.positiveSum(); sumNeg = s.negativeSum(); cout << "Sum of positive: "<< sumPos << ", Sum of negative: " << sumNeg << endl; if(sumPos > sumNeg) { cout << "The sum of positive numbers is greater than negative ones!\n"; } else if(sumNeg > sumPos) { cout << "The sum of negative numbers is greater than positive ones!\n"; } else { cout << "They are the same\n"; } break; case 3: s.print(); break; default: cout << "Bad option\n"; } } }