Використання вільної пам'яті у Паскалі
1. Адреси та вказівники
Пам'ять комп'ютера можна розглядати як послідовність байтів, номери яких 0, 1, 2, … називаються адресами. Кожна змінна в пам'яті займає залежно від її типу деяку кількість послідовних байтів. Наприклад, змінні типу char займають 1 байт, а величезні масиви – тисячі й десятки тисяч байтів.
Адресою змінної вважається адреса її першого байта. Не кожна адреса може бути адресою змінної. Наприклад, змінні типу integer можуть мати лише парні адреси. Усі можливі адреси даних якогось типу T утворюють носій типу адрес, що позначається виразом ^T. Наприклад, ^integer позначає множину адрес цілих, ^array[1..100] of char – множину адрес масивів, складених сотнею символів, ^record fld1, fld2 : real end – множину адрес записів із двох дійсних. Типом T може бути довільний тип, окрім типу файла. Тип, означений як ^T, називається адресним, а тип T – базовим для нього.
У стандарті мови Паскаль немає сталих для явного позначення адрес, але є в діалектах. Значення адресного типу ^T задаються викликом функції ADDR вигляду addr(x), де x – ім'я змінної типу T. У мові Турбо Паскаль означено операцію @: замість addr(x) можна писати @x. Ім'я nil позначає адресу 0, що належить до всіх можливих типів ^T. Ця адреса не може бути адресою жодної змінної, тобто є "нічийною", фіктивною. До однотипних адрес застосовні операції порівняння на рівність = і нерівність <>.
Змінні, значеннями яких є адреси, називаються вказівниками. У стандарті мови Паскаль вживаються так звані типізовані вказівники – змінні типу ^T. Вони ще називаються вказівниками типу T. Їм можна присвоювати адреси змінних тільки типу T або значення nil. Присвоювання адреси змінної вказівнику називається встановленням його на змінну.
Приклад 16.1. За дії означень
type Ari = array[1..5]of integer; var x : Ari; p : ^Ari;
результат присвоювання p:=addr(x) можна подати так:
До вказівників застосовна специфічна операція розіменування зі знаком "^": якщо p – вказівник типу T, то вираз p^ задає змінну типу T, на яку встановлено p.
Якщо p встановлено на змінну x, то вирази x і p^ еквівалентні. У прикладі 16.1 елемент масиву з індексом k задається як виразом x[k], так і виразом p^[k], тобто замість присвоювання x[1]:=1 можна написати p^[1]:=1, або замість x[2]:=2*x[1] – p^[2]:=2*p^[1].
Розіменування нікуди не встановленого вказівника або вказівника зі значенням nil призводить до аварійного закінчення програми.
Нині в більшості комп’ютерів адреси незалежно від їх базових типів займають 4 байти. Таким чином, і адреси типу ^char, і адреси типів ^array[1..100] of char або ^^integer (адреси адрес цілих) займають по 4 байти. Неважко зрозуміти, що 4 байти можуть мати 232=4294967296=4Г різних станів, якими подається стільки ж адрес.
2. Вільна пам'ять
Основним застосуванням вказівників є робота з вільною пам'яттю. Пам'ять процесу виконання програми поділяється на кілька різних за призначенням частин. Ними є:
пам'ять для операторів програми,
статична пам'ять – для глобальних і статичних змінних програми й модулів,
автоматична пам'ять, або програмний стек – для локальних змінних при виконанні викликів підпрограм.
вільна пам'ять, або купа.
Вільна пам'ять відрізняється від інших тим, що її ділянки виділяються під змінні та звільняються від них за явними на те указаннями в програмі. Змінні в цій пам'яті не мають імен, ідентифікуються за допомогою встановлених на них вказівників й називаються динамічними. Створення та знищення динамічних змінних називається керуванням купою.
Найпростішими засобами керування купою є процедури NEW та DISPOSE. Виклики їх мають вигляд new(p) та dispose(p), де p – вказівник на довільний тип T. Зазначимо одразу, що вказівник може бути як автоматичною чи статичною змінною, так і динамічною. Приклади застосування саме динамічних вказівників ми розглянемо в наступному підрозділі.
За виконання процедури new виділяється вільна, тобто незайнята іншими даними, ділянка купи. Її довжиною є кількість байтів, що займаються даними типу T. Адреса першого байта ділянки присвоюється аргументу p, тобто вказівник p встановлюється на цю ділянку. Наприклад, якщо в програмі означено p : Ari, як у прикладі 16.1, то результат виконання new(p) можна подати так:
Динамічна змінна, на яку встановлено вказівник p, означений у програмі, ідентифікується виразом p^.
Якщо в купі немає вільної ділянки потрібного розміру, то результат визначається конкретною системою програмування (найвірогідніше, виконання програми аварійно завершиться).
При виконанні процедури dispose ділянка пам'яті, на яку встановлено аргумент, звільняється, але (увага!) значення аргументу не змінюється.
Спроба звільнити вже звільнену ділянку пам'яті призводить до аварійного закінчення виконання програми.
Приклад 2. Програма з такою послідовністю операторів закінчується аварійно (p, q – однотипні вказівники):
new ( p ); q := p; dispose ( p );
dispose ( q ); { ??? }
3. Лінійні зв'язані списки
3.1. Зв'язаний список у купі
Поняття про лінійні списки та найпростіші дії над ними (додавання та вилучення елементів) пояснимо на прикладі.
Задача. З клавіатури задається послідовність прізвищ непорожніми рядками, що можуть повторюватися. Ознакою кінця є порожній рядок. Надрукувати прізвища кожне один раз із виконанням однієї з умов:
(1) порядок прізвищ не суттєвий;
(2) прізвища друкуються в лексикографічному порядку.
Розглянемо спочатку задачу, що визначається умовою (1). Нехай s позначає черговий рядок, а ss – послідовність прочитаних рядків. Спочатку ss порожня, що позначимо символами <>. Задамо розв'язання алгоритмом:
ss := <>;
readln ( s );
while s <> '' do
begin
if not ( s належить ss ) then (16.1)
додати s до ss;
readln ( s )
end;
надрукувати елементи ss.
Умова задачі