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

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

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

type TPle = ^Tle;

Tle = record

v : str; next : TPle

end

Якщо вказівник p типу TPle установлений на деякий елемент списку, то його можна позначити p^. Вирази p^.v і p^.next задають відповідно змінні типів str та Tple – їх значеннями є рядок, що зберігається в елементі списку, і адреса наступного елемента.

2. Найпростіші операції над списками

За допомогою введених означень почнемо уточнювати алгоритм (16.1). Подамо послідовність ss зв'язаним списком рядків. Для його ідентифікації означимо вказівник pss типу TPle.

Присвоювання ss := <> можна записати як pss := nil.

Опишемо додавання рядка s до послідовності ss. Найпростіший спосіб – додавати елемент з голови списку, тобто рядок ніби записується перед послідовністю. Для цього треба одержати ділянку вільної пам'яті під новий елемент списку, записати в нього новий рядок, "прив'язати" голову списку до нового елемента і зробити цей елемент головою:

procedure add ( s : str; var h : TPle );

var p : TPle;

begin

new ( p ); p^.v := s; p^.next := h; h := p

end

В результаті виконання процедури add у списку з'являється новий перший елемент, і вказівник h на голову списку змінюється. Тому він обов'язково повинен бути параметром-змінною. Оскільки послідовність представлено вказівником pss, саме він повинен бути аргументом у викликах цієї процедури: add ( s, pss ).

Для визначення належності s до ss треба рухатися по елементах списку від його початку доти, поки не натрапимо на елемент із рядком s або не дістанемось останнього елемента. Нехай h^ – черговий елемент списку. Умову переходу до наступного елемента в пошуках s можна виразити так:

( h^.next <> nil ) { черговий елемент не є останнім }

and

( h^.v <> s ) { і зберігає рядок, не рівний s }

Перехід до наступного елемента задає оператор h:=h^.next. Якщо послідовність порожня, то відповідь одержується тривіально. Отже, визначення належності s до ss задається функцією isin:

function isin ( s: str; h: TPle ) : boolean;

begin

if h = nil then isin := false

else

begin

while ( h^.next <> nil ) and ( h^.v <> s ) do

h := h^.next;

{ ( h^.next = nil ) or ( h^.v = s ) }