Проектування та аналіз обчислювальних алгоритмів

Національний технічний університет України

«Київський політехнічний інститут імені Ігоря Сікорського»

Навчально-науковий інститут атомної і теплової енергетики

Кафедра цифрових технологій в енергетиці

Проектування та аналіз обчислювальних алгоритмів

ЗВІТ ДО

КОМП’ЮТЕРНОГО ПРАКТИКУМУ № 3

«Списки»

(Тема роботи)

Варіант № 5

        Виконав: студент 2-го курсу

гр. ТР-11

Барбар Владислав Володимирович

(П.І.Б.)

Оцінка _________        Перевірив: _____________

Дата «___» _________ 202__        _______________________

(П.І.Б., підпис)

Київ – 2022

1.1. Завдання

1. Дослідити особливості створення однонаправлених і двонаправлених списків.

2. Вивчити і реалізувати механізми додавання нових записів у список, пошуку записів у списку за певними полями, видалення записів зі списку та редагування знайдених записів, а також збереження всього списку у файлі та зчитування списку із файлу до пам’яті з відновленням всіх зв’язків.

3. Розробити Блок-схему програмного алгоритму.

4. Оформити ЗВІТ до лабораторної роботи згідно вимог та методичних рекомендацій.

В якості структури даних використати варіанти завдання із Додатку В-3. Завдання обрати згідно свого варіанта.

[pic 1]

1.2. Теоретичні відомості

Однозв’язний список

Однозв’язний список є лінійною структурою даних, що складається з елементів одного типу, зв’язаних між собою за допомогою посилань. Кожен вузол зберігає в собі дані та адресу наступного вузла (рисунок 1.1). Завдяки наявності вказівника вузли можуть перебувати в будь-якому місці в пам’яті і об’єднуватися, створюючи список. Для того, щоб додати елемент, достатньо лише створити новий вузол, що має інформацію і посилання на наступний вузол.

[pic 2]

Рисунок 1.1. Структура однозв’язного списку

Нижче наведено переваги/недоліки у порівнянні з масивами.

Переваги:

1. Динамічність – не потрібно заздалегідь вказувати кількість елементів.
2. Простота вставки/видалення – виконати операцію вставки/видалення можна без зміщення попередніх елементів. Часова складність O(1).

Недоліки:

1. Відсутність довільного доступу – доступ до елементів отримується послідовно, починаючи з голови списку.
2. Кожному елементу списку потрібна додаткова пам’ять для посилання.

Таким чином, якщо завдання передбачає вставку/видалення багатьох елементів, то краще використовувати однозв’язний список, в інших випадках масив буде більш доречним.

Двозв’язний список

Двозв’язний список (DLL, Doubly-Linked List) містить додатковий вказівник, який зазвичай вказує на попередній вузол, разом із наступним вказівником та даними, які є в єдиному зв’язаному списку. Нижче наведено переваги/недоліки подвійно зв’язного списку у порівнянні з однозв’язним списком (рис. 1.2).

[pic 3]

Рисунок 1.2. Структура двозв’язного списку

Переваги перед однозв’язним списком:

1. DLL може проходити як уперед, так і назад.
2. Операція видалення в DLL є більш ефективною.
3. Ми можемо швидко вставити новий вузол перед даним вузлом. У однозв’язаному списку для видалення вузла потрібен вказівник на попередній вузол. Щоб отримати цей попередній вузол, іноді потьрібно обійти весь список. У DLL ми можемо отримати попередній вузол за допомогою попереднього вказівника.

Недоліки в порівнянні з однозв’язним списком:

1. Кожен вузол DLL вимагає додаткового місця для попереднього вказівника.
2. Для всіх операцій потрібен додатковий попередній покажчик, який потрібно підтримувати. Наприклад, під час вставки нам потрібно змінити попередні вказівники разом із наступними вказівниками. У деяких функціях для вставки в різні позиції нам потрібні 1 або 2 додаткові кроки для встановлення попереднього вказівника.

Для двозв’язного списку характерні методи вставки на початок, вкінець, видалення вузлів з початку та кінця списку, видалення вузла за заданими даними, повернення розміру списку (рис. 1.3 - 1.9). Методи можуть змінюватися да доповнюватися в залежності від поставленого завдання. Так у двозв’язному списку, що створено у роботі, додані методи пошуку вузла (в даному випадку об’єкта класа) за його полями.