Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 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 («виштовхнути елемент»): повертає елемент з верхівки стека. При цьому він видаляється зі стека і його місце у верхівці стека займає наступний з...
