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

•вільна пам'ять, або купа.

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

Найпростішими засобами керування купою є процедури NEW та DISPOSE. Виклики їх мають вигляд new(p) та dispose(p), де p – вказівник на довільний тип T. Зазначимо одразу, що вказівник може бути як автоматичною чи статичною змінною, так і динамічною. Приклади застосування саме динамічних вказівників ми розглянемо в наступному підрозділі.

За виконання процедури new виділяється вільна, тобто незайнята іншими даними, ділянка купи. Її довжиною є кількість байтів, що займаються даними типу T. Адреса першого байта ділянки присвоюється аргументу p, тобто вказівник p встановлюється на цю ділянку. Наприклад, якщо в програмі означено p : Ari, як у прикладі 16.1, то результат виконання new(p) можна подати так:

Динамічна змінна, на яку встановлено вказівник p, означений у програмі, ідентифікується виразом p^.

Якщо в купі немає вільної ділянки потрібного розміру, то результат визначається конкретною системою програмування (найвірогідніше, виконання програми аварійно завершиться).

При виконанні процедури dispose ділянка пам'яті, на яку встановлено аргумент, звільняється, але (увага!) значення аргументу не змінюється.

Спроба звільнити вже звільнену ділянку пам'яті призводить до аварійного закінчення виконання програми.

Приклад . Програма з такою послідовністю операторів закінчується аварійно (p, q – однотипні вказівники):

new ( p ); q := p; dispose ( p );

dispose ( q ); { ??? }

3. Лінійні зв'язані спискиМов мавпи, скуті ланцюгом,

ми крокували низкою.

О.Уайльд

3.1. Зв'язаний список у купі

Поняття про лінійні списки та найпростіші дії над ними (додавання та вилучення елементів) пояснимо на прикладі.

Задача. З клавіатури задається послідовність прізвищ непорожніми рядками, що можуть повторюватися. Ознакою кінця є порожній рядок. Надрукувати прізвища кожне один раз із виконанням однієї з умов:

(1) порядок прізвищ не суттєвий;

(2) прізвища друкуються в лексикографічному порядку.

Розглянемо спочатку задачу, що визначається умовою (1). Нехай s позначає черговий рядок, а ss – послідовність прочитаних рядків. Спочатку ss порожня, що позначимо символами <>. Задамо розв'язання алгоритмом:

ss := <>;