Використання вільної пам'яті

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.

Ця властивість мови грунтується на тім, що вказівники будь-якого типу мають той самий розмір.

Отже, означимо спочатку тип Tple вказівників, а потім тип елементів Tle зв'язаного списку рядків. Нехай str є ім'ям типу рядків у таких означеннях:

type TPle = ^Tle;