Лабораторна робота № 7
Тема: Покажчики. Зв'язані списки
Мета: Оволодіння практичними прийомами й навичками розробки програм з динамічними змінними, типу покажчики.
Покажчики
Часто виникає необхідність використовувати в програмі такі структури даних, форма й розмір яких змінюються в процесі виконання програми. У таких випадках використовуються динамічні змінні. Явно динамічні змінні не оголошуються. Замість цього використовується спеціальна змінна, котра містить адресу пам'яті, починаючи з якої розміщується динамічна змінна. Така змінна називається змінною-покажчиком.
В оголошенні типу покажчика слідом за символом покажчика (^ - капа) записується ідентифікатор типу динамічних змінних, називаємий базовим типом. Якщо базовий тип ще не оголошений, то він повинен бути оголошений у тій же самій частині оголошення, у якій оголошений тип покажчика. Наприклад:
type
PersonPointer = ^PersonRecord;
PersonRecord = record
Name: String[50];
Job : String[5];
Next: PersonPointer;
end;
var
FirstPerson, LastPerson, NewPerson: PersonPointer;
Тут тип PersonPointer оголошується як покажчик на змінні типу PersonRecord. Таким чином, змінні FirstPerson, LastPerson і NewPerson є змінними покажчиками, які можуть вказувати на записи типу PersonRecord.
Посилання на динамічну змінну записується як ідентифікатор змінної-покажчика, за яким слідує символ покажчика (^). Наприклад, FirstPerson^.
Виділення пам'яті для динамічної змінної й збереження адреси пам'яті, починаючи з якого розміщається динамічна змінна, у змінної-покажчику виконується за допомогою стандартної процедури New. Наприклад, New(NewPerson);
Змінні, створені за допомогою стандартної процедури New, розміщаються в області пам'яті, що називається “купа”. “Купа” займає всю або частину вільної пам'яті, що залишилася після завантаження програми.
Звільнення пам'яті, раніше зайнятої динамічною змінною, виконується за допомогою стандартної процедури Dispose.
Наприклад: Dispose(LastPerson);
Зв’язані списки записів
Зв’язані списки є ефективним засобом зберігання даних у випадку, коли заздалегідь невідомо, скільки даних треба зберігати в оперативній пам'яті. Зв’язані списки складаються з одного або більше "вузлів", розміщених в "купі". За кількістю зв'язків розрізняють односпрямовані й двоспрямовані списки. За типом зв'язків розрізняють лінійні й кільцеві списки. Кожний вузол односпрямованого списку містить покажчик на наступний вузол цього списку. Покажчик в останньому вузлі містить nil. На рисунку 1 наведений приклад односпрямованого лінійного зв’язаного списку.
Рисунок 1 – Односпрямований зв’язаний список
На рисунку 2 наведений приклад кільцевого зв’язаного списку.
Рисунок 2 – Кільцевий зв’язаний список
Кожний вузол двунаправленного списку містить покажчик на наступний вузол цього списку й на попередній вузол цього списку. Покажчик на наступний вузол в останньому вузлі містить nil. Покажчик на попередній вузол у першому вузлі містить nil. На рисунку 3 наведений приклад двунаправленного лінійного зв'язкового списку.
Рисунок 3 – Двоспрямований зв’язаний список
Керування зв'язаним списком записів (на прикладі)
Припустимо, що необхідно написати програму для ведення особистих рахунків. Можна зберігати всі дані про рахунки в записах, таких як запис типу Tcheck.
type
TCheck = record
Amount: Real;
Month: 1..12;
Day: 1..31;
Year: 1990..2000;
Payee: string[39];
end.
Але при написанні програми важко припустити, з якою кількістю рахунків прийдеться мати справу. Одне з рішень полягає в створенні великого масиву записів рахунків, але це призведе до зайвих витрат пам'яті. Більш гнучке рішення полягає в розширенні визначення запису й включенні в нього покажчика на наступний запис списку, що призведе до утворення зв'язаного списку з елементів типу TCheck.
type
PCheck = ^TCheck;
TCheck = record
Amount: Real;
Month: 1..12;
Day: 1..31;
Year: 1990..2000;
Payee: string[39];
Next: PCheck; {вказує на наступний запис}
end.
Тепер можна зчитати кожний запис рахунку з файлу й виділити для нього пам'ять. Якщо запис перебуває наприкінці списку, поле Next варто зробити рівним nil. У програмі потрібно відслідковувати тільки два покажчики: покажчик на перший рахунок у списку й покажчик на поточний рахунок.
Побудова списку
Нижче наведена процедура, що будує зв'язаний список записів, зчитуючи їх з файлу. Тут мається на увазі, що відкрито файл записів TCheck з ім'ям CheckFile, що містить, принаймні один запис.
var ListOfChecks, CurrentCheck: PCheck;
procedure ReadChecks;
begin
New(ListOfChecks); {виділити пам'ять для першого запису}
Read(CheckFile, ListOfChecks^); {зчитати перший запис}
CurrentCheck := ListOfChecks; {зробити перший запис поточним}
while not Eof(CheckFile) do
begin
New(CurrentCheck^.Next); {виділити пам'ять для наступного запису}
Read(CheckFile, CurrentCheck^.Next^); {зчитати наступний запис}
CurrentCheck := CurrentCheck^.Next; {зробити наступний запис поточним}
end;
CurrentCheck^.Next = nil; {після останнього зчитаного запису наступного немає}
end.
Переміщення за списком
Коли список уже є, можна легко виконувати пошук у ньому конкретного запису. Нижче показана функція, що знаходить перший рахунок з конкретною сумою й повертає покажчик на нього.
function FindCheckByAmount(AnAmount: Real): PCheck;
var Check: PCheck;
begin
Check := ListOfChecks; {вказує на перший запис}
while (Check^.Amount <> AnAmount) and (Check^.Next <> nil) do
Check := Check^.Next;
if Check^.Amount = AnAmount then
FindCheckByAmount := Check {повертає покажчик на знайдений запис}
else FindCheckByAmount:= nil; {або nil, якщо таких записів немає}
end;
Звільнення виділеної для списку пам'яті
У процедурі DisposeChecks показано, як можна перебрати список, дійшовши до кожного елемента й звільнивши його.
procedure DisposeChecks;
var Temp: PCheck;
begin
CurrentCheck := ListOfChecks; {вказує на перший запис}
while CurrentCheck <> nil do
begin
Temp := CurrentCheck^.Next {зберегти покажчик Next}
Dispose(CurrentCheck); {звільнення поточного запису}
CurrentCheck:= Temp; {зробити збережений запис поточним}
end;
end;
Процедури й функції для роботи з динамічною пам'яттю
Функції:
Addr(X) -повертає результат типу Pointer, у якому утримується адреса аргументу.
Тут Х - будь-який об'єкт програми (ім'я будь-якої змінної, процедури, функції). Адреса, що повертається, сумісна з покажчиком будь-якого типу. Відзначимо, що аналогічний результат повертає операція @.
CSeg - повертає значення, що зберігається в регістрі CS мікропроцесора (на початку роботи програми в регістрі CS утримується сегмент початку коду програми). Результат повертається в слові типу Word.
Dseg - повертає значення, що зберігається в регістрі DS мікропроцесора (на початку роботи програми в регістрі DS утримується сегмент початку даних програми). Результат вертається в слові типі Word.
MaxAvail - повертає розмір у байтах найбільшої безперервної ділянки купи. Результат має тип LongInt. За один виклик процедури New або GetMem не можна зарезервувати пам'ять більше, ніж значення, що повертається цією функцією.
MemAvail - повертає розмір у байтах загального вільного простору купи. Результат має типу LongInt.
Ofs(x) - повертає значення типу Word, що містить зсув адреси зазначеного об'єкта. Х - вираз будь-якого типу або ім'я процедури.
Ptr(Seg , Ofs) -повертає значення типу Pointer за заданим сегментом Seg і зсувом Ofs. Тут Seg - вираз типу Word, що утримує сегмент, Ofs - вираз типу Word, що містить зсув. Значення, що повертається функцією, сумісне з покажчиком будь-якого типу.
Seg(X) - повертає значення типу Word, що містить сегмент адреси зазначеного об'єкта. Тут Х - вираз будь-якого типу або ім'я процедури.
SizEof(X) - повертає довжину в байтах внутрішнього подання зазначеного об'єкта. Тут Х - ім'я змінної, функції або типу. Наприклад: замість константи скрізь SizeOfReal можна було б використовувати звернення SizEof(Real).
Процедури:
DisPose(TP) - повертає в купу фрагмент динамічної пам'яті, що раніше був зарезервований за типізованим покажчиком.
Тут TP - типізований покажчик. При повторному використанні процедури стосовно до вже звільненого фрагмента виникає помилка періоду виконання. При звільненні динамічних об'єктів можна вказувати другим параметром звертання до DisPose ім'я деструктора.
FreeMem(P,Size) - повертає в купу фрагмент динамічної пам'яті, що раніше був зарезервований за нетипізованим покажчиком. Тут Р - нетипізований покажчик. Size - довжина в байтах фрагмента, що звільняється.
При повторному використанні процедури стосовно до вже звільненого фрагмента виникає помилка періоду виконання.
GetMem(P,Size) - резервує за нетипізованим покажчиком фрагмент динамічної пам'яті необхідного розміру.
За одне звертання до процедури можна зарезервувати не більше 65521 байта динамічної пам'яті. Якщо немає вільної пам'яті необхідного розміру, виникає помилка періоду виконання. Якщо пам'ять не фрагментована, послідовні звертання до процедури будуть резервувати послідовні ділянки пам'яті, так що початок наступного буде розташовуватися відразу за кінцем попереднього.
Mark(Ptr) - запам'ятовує поточне значення покажчика купи HeapPtr. Тут Ptr - покажчик будь-якого типу, у якому буде повернуте поточне значення HeapPtr. Використовується разом із процедурою Release(Ptr) для звільнення частини купи.
New(TP) - резервує фрагмент купи для розміщення змінної. Тут ТР - типізований покажчик. За одне звертання до процедури можна зарезервувати не більше 655521 байта динамічної пам'яті. Якщо немає вільно пам'яті необхідного розміру, виникає помилка періоду виконання. Якщо пам'ять не фрагментована, послідовні звертання до процедури будуть резервувати послідовні ділянки пам'яті, так що початок наступного буде розташовуватися відразу за кінцем попередні.
Процедура New може викликатися як функція. У цьому випадку параметром звертання до неї є тип змінної, розташовуваної в купі, а функція New повертає значення типу покажчик. Наприклад:
Type Pint = ^integer;
Var P: Pint;
…
p:= New(Pint);
При розміщенні в динамічній пам'яті об'єкт розміщауться як другий параметр звертання до New указувати ім'я конструктора.
Release(Ptr) - звільняє ділянку купи. Тут Ptr - покажчик, будь-якого типу, у якому попередньо було збережено процедурою Mark значення покажчика купи. Звільняється ділянка купи від адреси, що зберігається в Ptr, до кінця купи. Одночасно знищується список всіх вільних фрагментів, які, можливо, були створені процедурами DisPose або FreeMem.