Списки.
Лінійний масив довільного розміру, в якому включення і виключення елементів можуть виконуватись в довільних точках, називається списком. Для доступу до елементів списку як правило, обмежуються першим елементом і наступним (іноді попереднім по відношенню до даного елементу). Отже, можливий доступ до любих елементів списку, але лише шляхом прокручування елементів списку починаючи з першого. Самим простим типом даних динамічної структури є зв’язаний список. Оскільки можливі довільні включення і виключення змінних, зв'язане представлення є майже неминучим для списку.
Розглянемо дві форми зв'язних списків, які найчастіше зустрічаються.
1. Зв'язне представлення з одним зв'язком.
Тут кожен елемент зв'язаний з наступним по відношенню до нього елементом. Є вказівник на перший елемент, що зазвичай знаходиться в окремій комірці, що називається початком списку. Це представлення ідентичне представленню, що використовується для стеків.
2. Зв'язані представлення з двома зв'язками.
Кожен елемент зв'язаний як з наступним, так і з попереднім елементом списку. На початку списку є вказівники і на перший, і на останній елементи списку:
-
Вказівник на перший елемент списку;
- вказівник на останній елементу списку.
Зв'язане представлення з одним зв'язком має той недолік, що список можливо переглянути тільки в одному напрямку. Легко просуватись від початку з першого елементу - згідно вказівникам, що зберігаються разом з кожним елементом, але неможливо просуватись по списку в зворотньому напрямку., до елементу, який уже пройшли Зв'язане представлення з двома зв'язками використовується в основному в тих випадках, коли це обмеження на напрямок перегляду дуже трудоємке.
3В’язані списки.
Самим простим типом даних динамічної структури є зв 'язаний список. Компоненти зв'язаного списку можна вставляти та виключати довільним чином. Розглянемо структуру даних, побудовану на основі однієї зсилочної змінної (початок) та трьох компонентів типу об'єкт
(Мал.1)
Дані такої структури і називаються зв'язаним списком. Припустимо, що зсилочна змінна (початок) сприймається в якості вхідної точки для побудови списку. Спочатку список повинен бути пустим, тому
Початок: =nil;
Тепер потрібно вставити в список одну компоненту. Компоненти створюються динамічно за допомогою стандартної процедури NEW., аргументом якої є зсилка. Опишемо
Var P:зв'язок;
Та звернемось до процедури
NEW(P);
Цим самим ми створюємо компоненту типу об'єкт з іменем Р^. Одержемо
Присвоємо новій компоненті деяке значення. Так як Р - це запис, то поле даних цього запису Р^ можливо записати як
Р^.дані;
а припустивши, що в поле даних можливо помістити одиночний символ запишемо
Р^.дані: = 'х';
Наступним кроком повинно бути виконання оператора
Р^. наступний:= ^початок;
До цього у змінній початок було записано значення NIL, тому в результаті виконання оператору з'ясується, що наступне значення поля Р^. буде те, яке показане на малюнку
початок
Р^. наст : =початок; Необхідно ще виконати оператор
початок: =Р; Після цього ми одержимо результат
Побудований список побудований із однієї компоненти. Але послідовність операторів
Р^.наступний:=початок; початок: =Р;
використана при створенні першої компоненти є частиною загального алгоритму додавання компоненти в початок списку.