Перелік усіх робіт

Обробка зв’язного списку

Мета роботи

Отримати навички роботи з типами даних в мовах програмування C та С++

Обладнання

Персональний комп’ютер, Visual Studio 2008 або інша середа розробки для мови C++

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

Що таке зв’язний список

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

Типи зв’язних списків

• Однозв’язний список — кожен вузол містить покажчик лише на наступний елемент.
• Двозв’язний список — кожен вузол містить покажчики на попередній і наступний елементи.
• Кільцевий список — останній елемент вказує на перший (може бути як одно-, так і двозв’язним).

Порівняння з масивами

Масиви	Зв’язні списки
Фіксований розмір	Динамічний розмір
Швидкий доступ за індексом	Послідовний доступ
Вставка/видалення — повільно (зсув)	Вставка/видалення — швидко (зміна покажчиків)
Дані розташовані послідовно в пам’яті	Дані можуть бути розкидані в пам’яті

Структура вузла

struct Node {
    string val;
    Node* next;
    Node(string _val) : val(_val), next(nullptr){}
};

Повна реалізація списку

Основні операції над списком

• Додавання елемента (на початок, в кінець, у довільне місце)
• Видалення елемента (з початку, з кінця, за значенням)
• Пошук елемента
• Вивід усіх елементів
• Очищення списку (звільнення пам’яті)

Особливості роботи з пам’яттю

• Для кожного нового вузла пам’ять виділяється динамічно (new у C++ або malloc у C).
• Після видалення вузла пам’ять необхідно звільняти (delete у C++ або free у C).
• Важливо уникати “витоків пам’яті” (memory leaks) — не забувати видаляти всі вузли при завершенні роботи зі списком.

Переваги та недоліки зв’язних списків

Переваги:

• Динамічний розмір, немає обмежень на кількість елементів (обмеження — лише обсяг оперативної пам’яті).
• Легке додавання та видалення елементів.

Недоліки:

• Витрати пам’яті на зберігання покажчиків.
• Відсутність прямого доступу за індексом (доводиться ітерувати список).
• Можливість помилок при неправильному керуванні пам’яттю.

Двозв’язний список (коротко)

У двозв’язному списку кожен вузол має два покажчики: на наступний і попередній вузол. Це дозволяє ефективно переміщатися в обох напрямках, але ускладнює реалізацію та збільшує витрати пам’яті.

struct DNode {
    string val;
    DNode* prev;
    DNode* next;
    DNode(string _val) : val(_val), prev(nullptr), next(nullptr) {}
};

Кільцевий список (коротко)

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

Очищення всього списку

void clear() {
    while (!is_empty()) {
        remove_first();
    }
}

Візуалізація однозв’язного списку

[дані|*] -> [дані|*] -> [дані|*] -> nullptr

Хід роботи

1. Завантажити Visual Studio 2008. Знайдіть на робочому столі ярлик з Visual Studio 2008 або Пуск → Всі програми→ Microsoft → Microsoft Visual Studio 2008.

2. Створити новий проект «Visual C++ (консольное приложение Win32)». Файл → Cтворити → Проект, тип проекту «Консольное приложение Win32».

3. Перевірити роботу прикладів, пояснити їх роботу

   Приклад 1 Приклад 2

4. Змінити приклад настуним чином:
   • у якості даних у вузол записувати ПІБ людини та її вік
   • реалізувати функцію друку всіх записів списку для віку 25 та вище

5. Розв’язати задачу згідно з варіантом. Створити динамічний однозв’язний список, додати основні операції по роботі зі списком. Використати об’єктно-орієнтований підхід. Для кожного елементу списку обрати структуру відповідно до варіанту.

   Варіант 1. Описати структуру з ім’ям Student, що містить такі поля:

   • прізвище;
   • номер групи;
   • успішність (масив із 5 елементів). Написати програму, яка виконує такі дії:
   • введення з клавіатури даних зв’язний список, що складається з 10 елементів типу Student;
   • записи впорядкувати за зростанням номера групи;
   • вивести прізвища тих студентів, чий середній бал більший за 4,0. Якщо таких студентів немає, вивести відповідне повідомлення.

   Варіант 2. Описати структуру з ім’ям PassengerPlane, що містить такі поля:

   • назву пункту призначення;
   • номер рейсу;
   • тип літака. Написати програму, яка виконує такі дії:
   • введення з клавіатури даних зв’язний список, що складається з 7 елементів типу PassengerPlane;
   • записи впорядкувати за зростанням номера рейсу;
   • вивести номери рейсів та типи літаків, що вилітають до пункту призначення, назва якого збіглася з назвою, введеною з клавіатури. Якщо немає, вивести відповідне повідомлення.

   Варіант 3. Описати структуру з ім’ям Train, що містить такі поля:

   • назву пункту призначення;
   • номер поїзда;
   • час відправлення. Написати програму, яка виконує такі дії:
   • введення з клавіатури даних зв’язний список, що складається з 8 елементів типу Train;
   • записи упорядкувати в алфавітному порядку за назвами пунктів призначення;
   • вивести інформацію про поїзди, що відправляються після введеного з клавіатури часу. Якщо таких поїздів немає, вивести відповідне сполучення.

   Варіант 4. Описати структуру з ім’ям Marsh, що містить такі поля:

   • назву початкового пункту маршруту;
   • назву кінцевого пункту маршруту;
   • номер маршруту. Написати програму, яка виконує такі дії:
   • введення з клавіатури даних зв’язний список, що складається з 8 елементів типу Marsh;
   • записи упорядкувати за номерами маршрутів;
   • вивести інформацію про маршрути, що починаються або закінчуються в пункті, назва якого введена з клавіатури. Якщо таких маршрутів немає, вивести відповідне повідомлення.

   Варіант 5. Описати структуру з ім’ям Note, що містить такі поля:

   • прізвище;
   • номер телефону;
   • день народження (масив із 3 чисел). Написати програму, яка виконує такі дії:
   • введення з клавіатури даних зв’язний список, що складається з 8 елементів типу Note;
   • записи впорядкувати за датами днів народження;
   • вивести інформацію про людину, номер телефону якої введено з клавіатури. Якщо цього немає, вивести відповідне повідомлення.

   Варіант 6. Описати структуру з ім’ям Znak, що містить такі поля:

   • прізвище;
   • знак зодіаку;
   • день народження (масив із 3 чисел). Написати програму, яка виконує такі дії:
   • введення з клавіатури даних зв’язний список, що складається з 8 елементів типу Znak;
   • записи упорядкувати за датами днів народження;
   • вивести інформацію про людину, чиє прізвище введене з клавіатури. Якщо цього немає, вивести відповідне повідомлення.

   Варіант 7. Описати структуру з іменем Price, що містить такі поля:

   • Назва товару;
   • назва магазину, у якому продається товар;
   • вартість товару у рублях. Написати програму, яка виконує такі дії:
   • введення з клавіатури даних зв’язний список, що складається з 8 елементів типу Price;
   • записи впорядкувати за абеткою щодо назви товару;
   • вивести інформацію про товар, назву якого введено з клавіатури. Якщо таких товарів немає, вивести відповідне повідомлення.

   Варіант 8. Описати структуру з ім’ям Order, що містить такі поля:

   • розрахунковий рахунок платника;
   • розрахунковий рахунок отримувача;
   • сума, що перераховується в рублях. Написати програму, яка виконує такі дії:
   • введення з клавіатури даних зв’язний список, що складається з 8 елементів типу Order;
   • записи упорядкувати в алфавітному порядку за розрахунковими рахунками платника;
   • вивести інформацію про суму, зняту з розрахункового рахунку платника, запровадженого з клавіатури. Якщо такого розрахункового рахунку немає, вивести відповідне повідомлення.

   Варіант 9. Описати структуру з ім’ям Student, що містить такі поля:

   • прізвище;
   • номер групи;
   • успішність (масив із 5 елементів). Написати програму, яка виконує такі дії:
   • введення з клавіатури даних зв’язний список, що складається з 10 елементів типу Student;
   • записи впорядкувати за зростанням середнього бала;
   • вивести прізвища студентів, які мають оцінки 4 та 5. Якщо таких студентів немає, вивести відповідне повідомлення.

   Варіант 10. Описати структуру з ім’ям PassengerPlane, що містить такі поля:

   • назву пункту призначення;
   • номер рейсу;
   • тип літака. Написати програму, яка виконує такі дії:
   • введення з клавіатури даних зв’язний список, що складається з 7 елементів типу PassengerPlane;
   • записи упорядкувати в алфавітному порядку за назвами пунктів призначення;
   • вивести пункти призначення та номери рейсів, які обслуговує літак, тип якого введений з клавіатури. Якщо таких рейсів немає, вивести відповідне повідомлення.
6. Для кожного етапу роботи зробити знімки екрану та додати їх у звіт з описом кожного скіншота
7. Додати програмний код завдання для самомтійного виконання
8. Дати відповіді на контрольні запитання
9. Зберегти звіт у форматі PDF

Контрольні питання

1. Дайте характеристику основних типів даних у мові програмування C++.
2. Які існують види зв’язних списків? Охарактеризуйте їх.
3. Які основні операції можна виконувати над зв’язним списком?
4. Поясніть різницю між масивом і зв’язним списком.
5. Для чого потрібні структури в мові C++? Як вони використовуються у зв’язних списках?
6. Як оголошується структура у програмі? Наведіть приклад.
7. Який оператор використовується для доступу до членів структури через покажчик?
8. Як ініціалізувати структуру? Наведіть приклад.
9. Як виділяється та звільняється пам’ять для вузлів зв’язного списку у C++?
10. Які переваги та недоліки зв’язних списків порівняно з масивами?
11. Як реалізувати пошук елемента у зв’язному списку?
12. Як очистити (видалити всі елементи) зв’язний список?
13. Які помилки можуть виникати при роботі зі зв’язними списками?
14. Як реалізувати двозв’язний або кільцевий список? У чому їх особливості?

Приклади

1. Зв’язний список на мові С
2. Зв’язний список на мові С++ (структури та ООП)

Довідники та додаткові матеріали

1. C++ List: How To Add, Assign, Delete List In C++
2. Структура даних зв’язаного списку на C ++ з ілюстрацією
3. Списки в C++. Односвязный список
4. Список list в С++: полный материал