Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лінійні однозв’язні та двозв’язні списки
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 5
з дисципліни «Програмування складних алгоритмів»
Тема «Лінійні однозв’язні та двозв’язні списки»
Варіант № 11
Лабораторна робота № 5:
Лінійні однозв’язні та двозв’язні списки
Мета: ознайомитися з основами роботи з двозв’язним списком, однозв’язним списком, стеком та чергою.
Завдання до лабораторної роботи
Створити лінійний однозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його, а попередній та наступні поміняти місцями. Виконати завдання згідно варіанту.
Створити двозв’язний список, вивести його. Якщо в списку є елемент із заданим ключем, вилучити його. Виконати завдання згідно варіанту з двозв’язним списком.
№ варіанту
Метод пошуку
11
В послiдовностi чисел знайти останнє максимальне та перше мiнiмальне, помiняти їх мiсцями.
Теоретичні відомості
Зв'язаний список — одна з найважливіших структур даних, в якій елементи лінійно впорядковані, але порядок визначається не номерами елементів, а вказівниками, які входять до складу елементів списку та вказують на наступний за даним елемент (в однозв'язаних або однобічно зв'язаних списках) або на наступний та попередній елементи (в двозв'язаних або двобічно зв'язаних списках). Список має «голову» — перший елемент та «хвіст» — останній елемент.
Зв'язані списки мають серію переваг порівняно з масивами. Зокрема, в них набагато ефективніше (за час О(1), тобто незалежно від кількості елементів) виконуються процедури додавання та вилучення елементів. Натомість, масиви набагато кращі в операціях, які потребують безпосереднього доступу до кожного елементу, що у випадку зі зв'язаними списками неможливо та потребує послідовного перебору усіх елементів, які передують даному.
Різновиди зв'язаних списків
Однобічно зв'язані списки
/
В однобічно зв'язаному списку, який є найпростішим різновидом зв'язаних списків, кожний елемент складається з двох полів: data або даних, та вказівника next на наступний елемент. Якщо вказівник не вказує на інший елемент (інакше: next = NULL), то вважається, що даний елемент — останній в списку.
Приклад реалізації вузла:
struct Node
{
int value; // певна інформативна частина
Node * next; // вказівник (pointer) на наступну структуру-вузол у списку
};
Node * head = NULL; // вказівник на голову списку, спочатку він нікуди не вказує, бо список порожній
Двобічно зв’язаний список
/
У двобічно зв'язаному списку елемент складається з трьох полів — вказівника на попередній елемент prev, поля даних data та вказівника next на наступний елемент. Якщо prev=NULL, то в елемента немає попередника (тобто він є «головою» списку), якщо next=NULL, то в нього немає наступника («хвіст» списка).
Приклад реалізації вузла:
struct List
{
char name[30];
List *next;
List *prev;
};
List *head; // голова списку
Кільцевий список
/
В кільцевому списку перший та останній елемент зв'язані. Тобто, поле prev голови списка вказує на хвіст списка, а поле next хвоста списка вказує на голову списка.
Застосування списків
Списки інтенсивно застосовуються в програмуванні як самостійні структури. Також на їх основі можуть будуватись складніші структури даних, такі як дерева. На базі списків також можуть бути реалізовані стеки та черги.
Стек — різновид лінійного списку, структура даних, яка працює за принципом «останнім прийшов — першим пішов» (LIFO). Всі операції (наприклад, видалення елемента) в стеку можна проводити тільки з одним елементом, який міститься на верхівці стека та був уведений в стек останнім.
Операції над стеком:
push («заштовхнути елемент»): елемент додається в стек та розміщується в його верхівці. Розмір стека збільшується на одиницю. При перевищенні граничної величини розміру стека, відбувається переповнення стека;
pop («виштовхнути елемент»): повертає елемент з верхівки стека. При цьому він видаляється зі стека і його місце у верхівці стека займає наступний за ним відповідно до правила LIFO, а розмір стека зменшується на одиницю. При намаганні «виштовхнути» елемент зі вже пустого стека, відбувається ситуація «незаповненість» стека.
Додаткові операції (присутні не у всіх реалізаціях стека):
isEmpty: перевірка наявності елементів у стеку; результат: істина (true), коли стек порожній;
isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе;
clear: звільнити стек (видалити всі елементи);
top: отримати верхній елемент (без виштовхування);
size: отримати розмір (кількість елементів) стека;
swap: поміняти два верхніх елементи місцями.
Черга — динамічна структура даних, що працює за принципом «перший прийшов — перший пішов» (FIFO). У черги є голова (head) та хвіст (tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові.
Основні операції над чергою:
enqueue — «поставити в чергу». Операція додавання елемента в «хвіст» черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення.
dequeue — «отримання з черги». Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація «незаповненість».
Результати роботи
Однозв’язний список
Створено структуру List, у якій знаходиться інформативна частина data та вказівник на наступний вузол списку *next. Також створюємо вказівник на голову списку *head. Далі розробляються функції для роботи із списком.
Функція Push() додає елемент у список. Створюємо вказівник на новий вузол. Якщо в голові *head нічого немає, записуємо дані туди. В іншому випадку head здвигаємо на наступний елемент і записуємо нову структуру.
Функція Create() створює список та циклом for() заповнює псевдовипадковими числами в діапазоні від 1 до 20. Також уводимо розмірність списка, який має бути більшим за 1.
Функція Print_List() виводить дані на екран. Створюємо вказівник на початок списку (голову) і перевіряємо: якщо початок пустий, то у списку немає елементів, виводимо відповідне повідомлення; в іншому випадку, поки вказівник не буде пустим, виводимо дані.
Функція Find_key() перевіряє чи є вказаний елемент (ключ) у списку. Створюємо вказівник та змінну find_key типу bool. Проходимо весь список. Якщо такий елемент знайдено, то повертаємо істину.
Функція Search_key() шукає заданий елемент (ключ). Створюємо вказівник, проходимо весь список. Якщо елемент знайдено, то повертаємо вказівник на цей елемент.
Функція Change_places() змінює місцями два елементи. Нехай один елемент вказує на наступний після себе і дорівнює наступному за інший. А наступний за інший дорівнює першому. Створюємо вказівник, проходимо весь список та змінюємо елементи місцями.
Функція Remove() видаляє елемент. Якщо потрібний вузол стоїть на першому місці, здвигаємо голову на наступний, а цей елемент видаляємо. Якщо потрібний вузол стоїть на першому місці і він єдиний, то видаляємо його і тепер наш список пустий. У іншому випадку проходимо весь список та видаляємо знайдене значення.
Функція Remove_Swap() знаходить, видаляє ключ та змінює місцями елементи. Спочатку уводимо ключ. Якщо такий вузол наявний у списку (тут викликається функція Find_key()), то створюємо вказівники: на знайдений елемент (викликаємо функцію Search_key()) та на наступний після знайденого. Викликаємо функцію Remove(), видаляємо ключ. Тепер викликаємо функцію Change_places() та змінюємо елементи місцями. Якщо ж заданого ключа немає у списку, виводимо відповідне повідомлення.
Функція Exchange_MaxMin() здійснює пошук мінімального та максимального елементів і змінює їх місцями. Створюємо вказівники. Нехай мінімальний та максимальний елементи знаходяться в початковому вузлі. Проходимо весь список. Якщо якийсь вузол більший за максимальний, то змінюємо їх місцями. Пошук мінімального елемента здійснюється за таким самим принципом. Уводимо додаткову змінну для їх обміну.
Двозв’язний список
Створено структуру List, у якій знаходиться інформативна частина data та вказівники на попередній *previous та наступний *next вузли. Також створюємо вказівник на голову списку *head та його кінець *tail. Далі розробляються функції для роботи із списком.
Функція Push() додає елемент у список. Створюємо вказівник на новий вузол. Якщо в голові *head нічого немає, записуємо дані на початок та в кінець (у даному випадку це одне й те саме). В іншому випадку наступний елемент є head, а початковий є попереднім.
Функції Create(), Print_List(), Find_key(), Search_key() та Exchange_MaxMin() ідентичні до однозв’язного списку.
Функція Remove() видаляє елемент. Якщо потрібний вузол стоїть на першому місці, здвигаємо голову на наступний і тепер head вважатимемо попереднім, елемент видаляємо. Якщо потрібний вузол стоїть на останньому місці, то кінцем є попередній вузол, елемент видаляємо. Якщо потрібний вузол стоїть на першому місці і він єдиний, то видаляємо його і тепер наш список пустий. У іншому випадку вузли здвигаємо місцями.
Функція Remove_KeyElen() видаляє елемент за ключем. Спочатку уводимо ключ. Якщо такий вузол наявний у списку (тут викликається функція Find_key()), то створюємо вказівники: на знайдений елемент (викликаємо функцію Search_key()), та на наступний після знайденого. Викликаємо функцію Remove() та видаляємо вузол.
1.4. Висновок
У ході лабораторної роботи було ознайомлено з основами роботи з двозв’язним та однозв’язним списком, стеком та чергою. Отримано практичні навички додавання та видалення елементі списку, пошук необхідного значення та обміну елементів.
Лістинг програми
Однозв’язний список
#include <iostream>
#include <ctime>
using namespace std;
struct List
{
int data = 0;
List* next = NULL;
};
List* head;
void Push(int data);
void Create();
void Print_List();
bool Find_key(int key);
List* Search_key(int key);
void Change_places(List* first, List* second);
void Remove(List* del);
void Remove_Swap();
void Exchange_MaxMin();
int main()
{
cout << "Single List" << endl;
Create();
Print_List();
Remove_Swap();
Print_List();
Exchange_MaxMin();
Print_List();
return 0;
}
//Функція додавання елементу до списка
void Push(int data)
{
List* point = new List;
point->data = data;
if (head == NULL)
{
head = point;
point->next = NULL;
}
else
{
point->next = head;
head = point;
}
}
//Функція заповнення списка
void Create()
{
srand(time(NULL));
int size = 0, data;
do
{
cout << "Enter the size of the matrix: ";
cin >> size;
if (size < 1)
cout << "Error! Try again!";
} while (size < 1);
for (int i = 0; i < size; i++)
{
data = rand() % 20 + 1;
Push(data);
}
}
//Функція виведення списка на екран
void Print_List()
{
List* point = head;
if (point == NULL)
cout << "The list is empty!\n";
while (point != NULL)
{
cout << point->data << " ";
point = point->next;
}
}
//Функція перевірки заданого елемента (ключа) на наявність у списку
bool Find_key(int key)
{
bool find_key = false;
List* point;
for (point = head; !find_key && point != NULL; point = point->next)
{
if (point->data == key)
find_key = true;
}
return find_key;
}
//Функція пошуку заданого елемента (ключа) в списку
List* Search_key(int key)
{
List* point;
for (point = head; point != NULL; point = point->next)
{
if (point->data == key)
break;
}
return point;
}
//Функція зміни місцями двох елементів
void Change_places(List* first, List* second)
{
first->next = second->next;
second->next = first;
List* point;
for (point = head; point != NULL; point = point->next)
{
if (point->next == first)
{
point->next = second;
break;
}
}
}
//Функція видалення
void Remove(List* del)
{
if (del == head)
{
head = del->next;
delete del;
}
else if (!head->next && del == head)
{
head = NULL;
delete del;
}
else
{
List* point;
for (point = head; point != NULL; point = point->next)
{
if (point->next == del)
point->next = del->next;
}
delete del;
}
cout << "\nItem removed!";
}
//Функція видалення та обміну елементів
void Remove_Swap()
{
int key;
cout << "\nEnter the key: ";
cin >> key;
if (Find_key(key))
{
List* find = Search_key(key), * swap = find->next;
Remove(find);
if (swap && swap->next)
{
cout << "Items changed in places!" << endl;
Change_places(swap, swap->next);
}
else
cout << "Items can`t be changed in places!" << endl;
}
else
cout << "Items not found!" << endl;
}
//Функція знаходження max i min елементів у списку та їх обмін місцями
void Exchange_MaxMin()
{
List* point, * min = head, * max = head;
for (point = head; point != NULL; point = point->next)
{
if (point->data > max->data)
max = point;
if (point->data < min->data)
min = point;
}
cout << "\n\nThe minimum element: " << min->data << endl;
cout << "The maximum element: " << max->data << endl;
cout << "\nExchange of elements: " << endl;
int tmp = max->data;
max->data = min->data;
min->data = tmp;
}
Двозв’язний список
#include <iostream>
#include <ctime>
using namespace std;
struct List
{
int data = 0;
List* previous = NULL;
List* next = NULL;
};
List* head = NULL, * tail = NULL;
void Push(int data);
void Create();
void Print_List();
bool Find_key(int key);
List* Search_key(int key);
void Remove_KeyElen();
void Exchange_MaxMin();
int main()
{
cout << "Double List" << endl;
Create();
Print_List();
Remove_KeyElen();
Print_List();
Exchange_MaxMin();
Print_List();
return 0;
}
//Функція додавання елементу до списка
void Push(int data)
{
List* point = new List;
point->data = data;
if (head == NULL)
{
head = point;
tail = point;
point->previous = NULL;
point->next = NULL;
}
else
{
point->next = head;
head->previous = point;
head = point;
}
}
//Функція заповнення списка
void Create()
{
srand(time(NULL));
int size = 0, data;
do
{
cout << "Enter the size of the matrix: ";
cin >> size;
if (size < 1)
cout << "Error! Try again!";
} while (size < 1);
for (int i = 0; i < size; i++)
{
data = rand() % 20 + 1;
Push(data);
}
}
//Функція виведення списка на екран
void Print_List()
{
List* point = head;
if (point == NULL)
cout << "The list is empty!\n";
while (point != NULL)
{
cout << point->data << " ";
point = point->next;
}
}
//Функція перевірки заданого елемента (ключа) на наявність у списку
bool Find_key(int key)
{
bool find_key = false;
List* point;
for (point = head; !find_key && point != NULL; point = point->next)
{
if (point->data == key)
find_key = true;
}
return find_key;
}
//Функція пошуку заданого елемента (ключа) в списку
List* Search_key(int key)
{
List* point;
for (point = head; point != NULL; point = point->next)
{
if (point->data == key)
break;
}
return point;
}
//Функція видалення
void Remove(List* del)
{
if (del == head)
{
head = del->next;
head->previous = NULL;
delete del;
}
else if (del == tail)
{
tail = del->previous;
tail->next = NULL;
delete del;
}
else if (!head->next && del == head)
{
head = NULL;
delete del;
}
else
{
del->next->previous = del->previous;
del->previous->next = del->next;
delete del;
}
cout << "\nItem removed!\n";
}
//Функція видалення ключа списку
void Remove_KeyElen()
{
int key;
cout << "\nEnter the key: ";
cin >> key;
if (Find_key(key))
{
List* find = Search_key(key), * swap = find->next;
Remove(find);
}
}
//Функція знаходження max i min елементів у списку та їх обмін місцями
void Exchange_MaxMin()
{
List* point, * min = head, * max = head;
for (point = head; point != NULL; point = point->next)
{
if (point->data > max->data)
max = point;
if (point->data < min->data)
min = point;
}
cout << "\n\nThe minimum element: " << min->data << endl;
cout << "The maximum element: " << max->data << endl;
cout << "\nExchange of elements: " << endl;
int tmp = max->data;
max->data = min->data;
min->data = tmp;
}
Результат
/ /
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора