Лекция: Динамічні структури даних

Дані, які використовуються у програмі, поділяються на статичні й динамічні.

Статичні структури даних розміщуються у статичній пам’яті, виділеній компілятором у процесі компіляції програми. Їх взаєморозміщення, взаємозв’язки елементів і кількість завжди залишаються сталими в процесі виконання програми.

Динамічні структури даних розміщуються у динамічній пам’яті, яка виділяється на етапі виконання програми. Їх внутрішня побудова формується за деяким законом, а їх взаєморозміщення, взаємозв’язки елементів і кількість можуть динамічно змінюватися в процесі виконання програми. Для роботи з динамічними даними використовуються вказівники.

Вказівник – це статична змінна, значенням якої є адреса пам’яті. За допомогою вказівників можна розміщувати в динамічній пам’яті будь-які типи даних (цілі, дійсні, логічні, символьні, символьні рядки, масиви, записи та інші). Такі вказівники називаються типізованими. Для опису типізованого вказівника використовується знак ^, який записується перед відповідним типом. Наприклад,

Type Tank = record

p, i, b: string[15];

rn: word;

ps: string[20];

end;

Var v1, s1; ^integer;

v2: ^double;

v3: ^Tank;

Можна описати вказівник і не зв’язувати його з конкретним типом даних. Для цього є стандартний тип Pointer, наприклад:

Var p1, p2: pointer;

Такі вказівники називають нетипізованими. З їх допомогою зручно працювати з динамічними даними, структура і тип яких змінюється при виконанні програми.

Вказівник може бути у трьох станах:

визначений, містить адресу змінної, для якої виділена пам’ять;

невизначений (до першого присвоєння або після звільнення пам’яті);

помічений зарезервованим словом NIL (не вказує ні на які дані).

Значеннями вказівників є адреси змінних, розміщених у динамічній пам’яті. Для них допустима операція присвоєння, якщо вони вказують на один і той же тип даних. Типізованому вказівнику можна присвоювати значення нетипізованого. Наприклад, присвоєння v1:=s1; і p1:=p2; – допустимі, а присвоєння v1:=v2 і p1:=v3; – недопустимі.

Для звернення до даних, на які вказує вказівник, за його іменем зразу ставиться знак ^. Наприклад, v1^:=5; або s1^:=v1^.

Вся динамічна пам’ять розглядається як суцільний масив байтів, який називається купою. Для виділення і звільнення динамічної пам’яті використовуються процедури:

Procedure New(Var P: Pointer); – резервує фрагмент купи динамічної пам’яті для розміщення змінної і записує в типізований вказівник P адресу першого байта.

Procedure Dispose(Var P: Pointer); – повертає в купу фрагмент динамічної пам’яті, який був зарезервований за типізованим вказівником P. Якщо вказівник P невизначений, то фіксується помилка.

Procedure GetMem(Var P: Pointer; Size: Integer); – резервує за нетипізованим вказівником P фрагмент динамічної пам’яті розміру Size (в байтах) і присвоює йому адресу цієї області.

Procedure FreeMem(Var P: Pointer; Size: Integer); – повертає в купу фрагмент динамічної пам’яті, який був зарезервований за нетипізованим вказівником P. Звільняти потрібно такий розмір пам’яті, який був виділений.