p align="justify">. створити (відвести місце в динамічній пам'яті);
. працювати за допомогою покажчика;
. видалити (звільнити зайняте структурою місце).
Динамічні структури широко застосовують і для більш ефективної роботи з даними, розмір яких відомий, особливо для вирішення завдань сортування.
Одним з видів динамічної структури є - список.
Зв'язні лінійні списки
лінійний пам'ять програма машинний
Списком називається впорядкована множина, що складається із змінного числа елементів, до яких застосовні операції включення, винятку. Список, що відображає відносини сусідства між елементами, називається лінійним. Лінійні зв'язні списки є найпростішими динамічними структурами даних.
Довжина списку дорівнює числу елементів, що містяться в списку, список нульової довжини називається порожнім списком. Списки являють собою спосіб організації структури даних, при якій елементи деякого типу утворюють ланцюжок. Для зв'язування елементів у списку використовують систему покажчиків. У мінімальному випадку, будь-який елемент лінійного списку має один покажчик, який вказує на наступний елемент у списку або є порожнім покажчиком, що інтерпретується як кінець списку.
Графічно зв'язку в списках зручно зображувати за допомогою стрілок. Якщо компонента не пов'язана ні з якою іншою, то в полі покажчика записують значення, не вказується ні на який елемент. Таке посилання позначається спеціальним ім'ям - nil.
Машинне уявлення зв'язкових лінійних списків
На малюнку наведена структура одинзв'язного списку. На ньому поле INF - інформаційне поле, дані, NEXT - покажчик на наступний елемент списку. Кожен список повинен мати особливий елемент, званий покажчиком початку списку або головою списку, який зазвичай за форматом відмінний від решти елементів. У полі покажчика останнього елемента списку знаходиться спеціальний ознака nil, що свідчить про кінець списку.
Структура одинзв'язного списку
Однак, обробка одинзв'язного списку не завжди зручна, оскільки відсутня можливість просування в протилежну сторону. Таку можливість забезпечує двохзв'язной список, кожен елемент якого містить два покажчика: на наступний і попередній елементи списку. Структура лінійного двохзв'язной списку наведена на малюнку, де поле NEXT - покажчик на наступний елемент, поле PREV - покажчик на попередній елемент. У крайніх елементах відповідні покажчики повинні містити nil,.
Для зручності обробки списку додають ще один особливий елемент - покажчик кінця списку. Наявність двох покажчиків в кожному елементі ускладнює список і призводить до додаткових витрат пам'яті, але в той же час забезпечує більш ефективне виконання деяких операцій над списком.
Структура двохзв'язной списку
Різновидом розглянутих видів лінійних списків є кільцевої список, який може бути організований на основі як одинзв'язного, так і двохзв'язной списків. При цьому в одинзв'язного списку покажчик останнього елемента повинен вказувати на перший елемент; в двохзв'язной списку в першому і останньому елементах відповідні покажчики перевизначаються, як показано на малюнку.
При роботі з такими списками кілька спрощуються деякі процедури, що виконуються над списком. Однак, при перегляді такого списку слід прийняти деяких запобіжних заходів, щоб не потрапити в нескінченний цикл.
Структура кільцевого двохзв'язной списку
У пам'яті список являє собою сукупність дескриптора і однакових за розміром і форматом записів, розміщених довільно в деякій області пам'яті і пов'язаних один з одним в лінійно впорядковану ланцюжок за допомогою покажчиків. Запис містить інформаційні поля і поля покажчиків на сусідні елементи списку, причому деякими полями інформаційної частини можуть бути покажчики на блоки пам'яті з додатковою інформацією, що відноситься до елемента списку. Дескриптор списку реалізується у вигляді особливої ??запису і містить таку інформацію про список, як адресу початку списку, код структури, назву списку, поточне число елементів у списку, опис елемента і т.д., і т.п. Дескриптор може знаходитися в тій же області пам'яті, в якій розташовуються елементи списку, або для нього виділяється якесь інше місце.
Реалізація операцій над зв'язковими лінійними списками
Нижче розглядаються деякі прості операції над лінійними списками. Виконання операцій ілюструється в загальному випадку малюнками зі схемами зміни з...
