Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лінійні однозв’язні та двозв’язні списки
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ
імені ІГОРЯ СІКОРСЬКОГО”
ЗВІТ
з лабораторної роботи №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";
}
}
}
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора