Реалізація списку в послідовній пам'яті

У послідовній пам'яті список реалізується за допомогою двох погоджених масивів, перший з яких використовується для запису елементів, а другий -для запису вказівників. Наприклад:

D - масив, для запису елементів, L - масив, для запису вказівників, 0 – вказівник кінця списку.

Будемо вважати, що: L[1] буде вказувати на перший елемент функціонального списку, L[2] - на перший елемент вільного списку.

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

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

5. Структура даних типу «циклічний лінійний список» реалізується за схемою, поданною на рис. 5.3.

Рис. 5.3. Схема структури даних лінійний циклічний список

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

Операції для роботи із циклічним лінійним списком ті самі, що й для однозв'язного лінійного списку.

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

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

Набір допустимих операцій для СД типу «двозв'язний лінійний список»:

- ініціалізація;

- зробити список порожнім;

- перевірка: список порожній / список не порожній;

- встановити вказівник у кінець списку / початок списку (дві окремі про­цедури);

- пересунути вказівник уперед / назад на один крок;

- включити елемент у список до вказівника / після вказівника;

- виключити елемент зі списку до вказівника / після вказівника.

При цьому для включення елемента в список необхідно розпізнати наступні три ситуації:

- список порожній;

- включення елемента в середину списку;

- включення елемента в список як першого.

Для спрощення операції включення / виключення реалізують циклічні двозв'язні списки. При реалізації такого списку формують вказівники (замість маркерів кінця й початку списку), що вказують на перший і останній елементи списку. Допустимі операції для СД типу «циклічний двозв'язний список» аналогічні операціям для лінійного двозв'язного списку.

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

Приклад 5.1. Кожний елемент багатозв'язного списку може входити одночасно в кілька однозв'язних списків. Тобто багатозв'язний список «прошитий» у декількох напрямках.

Наприклад, необхідно організувати дані про абітурієнтів, але крім організації всіх відомостей, необхідно із загального списку вибрати абітурієнтів, що характеризуються деякими загальними даними (абітурієнти-медалісти, абітурієнти, що проживають в одному місті; абітурієнти, що здали іспит на «відмінно»).

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

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

Приклад 4.2. Розглянемо нелінійний зв'язний список, що зручний для подання діаграм стану дискретних систем.

Маємо діаграму із трьох станів. Дуги показують зміну поточного стану. Зміна стану здійснюється під дією вхідного сигналу X, при цьому система переходить у новий стан і видає вихідний сигнал У. Подібна діаграма може бути використана в діалоговій обчислювальній системі, де вхідні сигнали є командами, що вводять у систему з термінала користувача, а вихідні є іменами підпрограм. Отже, одержавши команду Xі відшукавши у списку за поточним станом відповідний цій команді елемент описування вихідної дуги системи, виконується підпрограма, зазначена в знайденому елементі. Тим самим реалізується необхідна реакція Y. Після цього система переходить в інший стан, і із цього моменту цей стан стає поточним.

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

1. Опишіть вказівний тип, яка його фізична суть?

2. Які операції визначені над вказівним типом?

3. Для чого використовуємо вказівник, який ні на що не вказує?

4. Які змінні називають статичними, динамічними?

5. Яка різниця між доступом до статичних та динамічних змінних?

6. Опишіть основні дії над динамічними змінними.

7. Як перевірити існування фрагментарності пам’яті?

8. Які недоліки структур, що відображаються на масив?

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

10. Як у мовах програмування реалізовано вказівку на кінець списку?

11. Які операції визначають СД типу "Лінійний однозв’язний список"?

12. Опишіть як реалізувати операції включення і виключення елементів списку.

13. Як реалізовують список в послідовній пам’яті?

14. Як реалізовують СД типу "циклічний лінійний список"?

15. Яка схема СД типу "двозв’язний лінійний список"?

16. Опишіть набір допустимих операцій для СД типу "двозв’язний лінійний список".

17. Як реалізовано операції включення та виключення елементів у СД типу "двозв’язний лінійний список"?

18. Наведіть приклади багатозв’язних списків.