10. Динамічні змінні. Покажчики. Найпростіші динамічні структури даних. Використання динамічних структур даних.

Розрізняють звичайну (статичну) та динамічну організації пам’яті комп’ютера.

В оперативній пам’яті можна розмістити обмежену кількість даних, зокрема, змінних. Коли змінні оголошують у розділі var, система надає їм певний обсяг пам’яті, навіть якщо не всі змінні будуть використані у програмі. Пам’ять, надана змінним, вивільняється лише після виконання програми. Однак є задачі, де заздалегідь невідомо, скільки змінних потрібно для їхнього розв’язування, а отже, який обсяг пам’яті слід зарезервувати. У цьому випадку, а також, якщо заздалегідь знають, що даних буде багато, застосовують динамічну організацію пам’яті.

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

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

type <назва типу> = ^ <базовий тип>;

Конкретні вказівники на динамічні змінні оголошують, як звичайно, у розділі var:

var <список вказівників на змінні> : <назва типу>;

Пам’ять для даних, про можливість появи яких попереджає вказівник, буде надана на етапі виконання програми за допомогою процедури new:

new(<вказівник на змінну>);

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

<вказівник на змінну>^.

Розрізняють операції над вказівником на динамічну змінну та операції над самою динамічною змінною. З динамічною змінною можна виконувати операції, визначені для даних відповідного базового типу. Над вказівниками визначені дві основні операції: операція взяття адреси та операція розіменування покажчика (вказівника).

Після опрацювання динамічної змінної пам’ять можна вивільнити за допомогою процедури dispose:

dispose(<вказівник на динамічну змінну>);

Найпростіші динамічні структури даних є такі:

1. однозв’язний (однонапрямлений) лінійний список – це динамічна структура даних, кожен елемент якої містить вказівник на наступний елемент;

2. двозв’язний (двонапрямлений) лінійний список – це динамічна структура даних, кожен елемент якої містить вказівник на наступний і попередній елементи.

Список як скінченна сукупність даних одного типу, між якими налагоджено зв’язок, може бути створений у вигляді:

 стеку – це структура даних, у якій елемент, записаний останнім, зчитують (він є доступний до опрацювання) першим; принцип „останній прийшов – перший пішов”;

черги – це структура даних, у якій елемент, записаний першим, зчитують першим; принцип „перший прийшов – перший пішов”.