Використання вільної пам'яті, Детальна інформація

dispose ( q ); { ??? }

3. Лінійні зв'язані списки

Мов мавпи, скуті ланцюгом,

ми крокували низкою.

О.Уайльд

3.1. Зв'язаний список у купі

Поняття про лінійні списки та найпростіші дії над ними (додавання та вилучення елементів) пояснимо на прикладі.

Задача. З клавіатури задається послідовність прізвищ непорожніми рядками, що можуть повторюватися. Ознакою кінця є порожній рядок. Надрукувати прізвища кожне один раз із виконанням однієї з умов:

(1) порядок прізвищ не суттєвий;

(2) прізвища друкуються в лексикографічному порядку.

Розглянемо спочатку задачу, що визначається умовою (1). Нехай s позначає черговий рядок, а ss – послідовність прочитаних рядків. Спочатку ss порожня, що позначимо символами <>. Задамо розв'язання алгоритмом:

ss := <>;

readln ( s );

while s <> '' do

begin

if not ( s належить ss ) then (16.1)

додати s до ss;

readln ( s )

end;

надрукувати елементи ss.

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

Рядок Вказівник на наступний рядок

Вони утворюють послідовність, показану на рис.16.1.

Перший елемент називається головою списку. Поле-вказівник кожного (крім останнього) елемента списку ідентифікує наступний елемент, тобто "прив'язує" його до попереднього.

Якщо розірвати цей зв'язок, змінивши значення вказівника, то наступний елемент списку і всі за ним стають неідентифікованими і перетворюються на "сміття" у вільній пам'яті.

Наприклад, якщо вказівник у першому елементі списку встановити не на другий елемент, а на якусь іншу ділянку пам'яті (пунктирна стрілка на рис.16.1), то на другий елемент (і всі за ним) вже немає посилань. А якщо на щось немає посилань, то його ніби й немає.

За останнім елементом списку немає наступного, тому його вказівник установлений на "ніщо".

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

Розглянемо означення та операції, за допомогою яких створюється та обробляється лінійний список. По-перше, нам потрібен тип для елементів лінійного списку. Очевидно, вони являють собою структури, одне з полів яких є вказівником на значення цього самого типу структур. Таким чином, незрозуміло, який же тип слід означити спочатку – тип структур чи вказівників на них? Вихід із цього "замкненого кола" дає така властивість мови Паскаль:

означення типу ^T вказівників дозволяється записувати вище від означення самого типу T.