зв’язкові списки

Зв'язний список - це різновид лінійних структур даних, що представляє собою послідовність елементів, зазвичай відсортовану відповідно до заданого правилом. Послідовність може містити будь-яку кількість елементів, оскільки при створенні списку використовується динамічний розподіл пам'яті.

Кожен елемент зв'язного списку є окремим об'єктом, що містить поле для зберігання інформації і покажчик на наступний елемент списку (а в разі двусвязного списку в об'єкті зберігається також покажчик на попередній елемент).

Схема, яка зображує зв'язний і двусвязний списки з трьох елементів:

Пересування по списку здійснюється за вказівниками, які вказують на сусідні елементи списку. При додаванні нового елемента до списку необхідно динамічно виділити під нього пам'ять і присвоїти відповідні значення вказівниками сусідніх елементів, а також вказівниками самого створеного елемента.

Створення простого зв'язного списку

Як приклад розглянемо зв'язний список, який зберігає цілі числа. Елементи списку сортуються за зростанням залежно від величини числа, яке зберігається в даному елементі.
Кожен елемент списку є екземпляром структури, яка описується в такий спосіб: Тут pnext - покажчик на наступний елемент списку, а value - поле для зберігання інформації.

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

Вивести спискок на екран можна за допомогою функції print (): Оскільки пам'ять для елементів списку виділяється динамічно, після закінчення роботи зі списком необхідно явно видалити всі його елементи. Функція видалення елементів списку може бути реалізована так: Протестувати функції для роботи зі зв'язковим списком можна наступним чином:
Створення двусвязного списку

Тепер наведемо приклад реалізації стека з використанням двусвязного списку.
Визначимо структуру, що описує елемент списку: Це визначення відрізняється від визначення елемента простого однозв'язного списку тільки наявністю покажчика на попередній елемент списку (pprev).

Визначення класу стека буде виглядати наступним чином: plast вказує на останній елемент, поміщений в стек. count - кількість елементів в стеку.
Функція push () поміщає новий елемент в стек, функція pop () витягує елемент з стека, а функція top () повертає значення верхнього елементу, не витягуючи його.

Реалізація функцій для роботи зі стеком: Протестуємо функції push () і pop ().
На головну