Отже, наведені алгоритми мають скоріше теоретичний, ніж практичний інтерес. Принаймні, ми не можемо рекомендувати їх до практичного застосування.

5. Великі масиви у вільній пам'яті

Подання послідовностей даних списками є досить гнучким. Особливо зручним воно є у випадках, коли дані додаються та вилучаються в процесі виконання програми. Але воно призводить до неефективного використання пам'яті, особливо коли дані, записані в елементах списку, невеликі за розміром. Справді, кожний елемент послідовності потребує додатково 4 байти під вказівник, або навіть 8, коли список двозв'язаний. Крім того, доступність елемента залежить від його розташування в списку. Відсутність прямого доступу до елементів створює незручності програмування і в багатьох випадках веде до того, що при виконанні програми пошук елемента стає занадто довгим.

Існує багато задач, в яких вимагається швидкий пошук значень і не потрібна гнучкість спискового подання. Прикладами є задачі наступних розділів. Там, як правило, не треба додавати чи вилучати довільні елементи з послідовності. Використання масивів там набагато зручніше.

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

Розглянемо засоби системи Турбо Паскаль, за допомогою яких зручно задавати обробку масивів у вільній пам'яті.

По-перше, корисними є функції MEMAVAIL і MAXAVAIL, з яких повертається загальний розмір незайнятої частини купи та найбільший розмір суцільної незайнятої ділянки (у байтах, типу Longint).

Масив у купі повинен ідентифікуватися вказівником, установленим на його перший елемент. В означенні типу масиву головне – задати індекс і тип його першого елемента. Наприклад, type Arl=array[0..0]of longint. Далі означимо тип вказівника на такий масив: Parl=^Arl. Вказівник, який встановлюється на масив у купі, означається як безтиповий– він може мати значеннями адреси даних будь-яких типів і розмірів. Для цього в Турбо Паскаль є тип з іменем Pointer.

"Захоплення" ділянки вільної пам'яті заданого розміру та встановлення безтипового вказівника на її перший байт задається процедурою GETMEM. Першим аргументом у її виклику є ім'я вказівника, другим – вираз типу Longint, що задає довжину ділянки в байтах. Наприклад, якщо

var p : Pointer; num : word = 16383;

то за виконання виклику

getmem(p, num*sizeof(Longint))

вказівник p встановлюється на ділянку вільної пам'яті розміром у

num*sizeof(Longint) = 16383*4 = 65532

байти. Звільнення ділянки задається аналогічним викликом процедури FREEMEM: freemem(p, num*sizeof(Longint)). У програмі слід звільняти ділянки такого самого розміру, що одержувалися, інакше наслідки можуть стати непередбачуваними.

Погляд на ділянку пам'яті як на послідовність елементів типу T реалізується за допомогою безтипового вказівника, перетвореного до типу ^T. Перетворений вказівник позначається виразом вигляду

^T(ім'я-вказівника).

Наприклад, якщо p – безтиповий вказівник, то вираз Parl(p) позначає вказівник, перетворений до типу Parl=^Arl. Тоді вираз Parl(p)^ задає адресу першого байта ділянки, на яку встановлено p. І, нарешті, вираз Parl(p)^[k], 0? k? 16383, позначає елемент масиву з індексом k. Тобто замість імені масиву вживається вираз вигляду ^T(ім'я-вказівника).

Перешкодою є те, що розмір ділянки пам'яті не може бути більше ніж 65532 байти, тобто максимальна кількість елементів масиву типу T – 65532/sizeof(T). Але подолати це обмеження дуже просто за допомогою масиву безтипових вказівників. Наприклад, якщо нам потрібний масив у сто тисяч елементів типу Longint, означимо масив із 10 вказівників та кількість елементів 10000 у одній ділянці вільної пам'яті:

p : array[ 0..9 ]of pointer; num : Longint =10000.

Після встановлення вказівників на 10 ділянок

for cnt:=0 to 9 do getmem(p[cnt], num*sizeof(Longint))

елемент масиву з індексом k, де 0? k? 9, задається виразом

Parl(p[k div num])^[k mod num].

І навпаки, вираз Parl(p[i])^[j] задає елемент масиву з індексом num*(i-1)+j.

Приклад. Наведемо програму, за якою створюється масив із 135 тисяч елементів типу LongInt, тобто по 4 байти. Елементам присвоюються їх порядкові номери. Далі друкуються значення тих елементів, номери яких кратні 4000, а також восьми останніх. Перед захопленням пам'яті та після нього друкуються загальний розмір незайнятої частини купи та найбільший розмір її суцільної незайнятої ділянки. Якщо за якихось причин виконання програми завершується аварійно, слід придивитися саме до останніх величин.

program arrptrfr;

const blocks=9;

type lng=longint; arl=array[0..0]of lng; parl=^arl;

var p : array[0..blocks-1]of pointer;

num, glob : lng ; k : lng; cnt: integer;

begin

num:=15000; glob:=num*blocks;

writeln( 'вільна пам''ять : ', memavail,

'; найбільша ділянка : ', maxavail);

for cnt:=0 to blocks-1 do getmem(p[cnt], num*sizeof(lng));

for k:=0 to glob-1 do

parl(p[k div num])^[k mod num]:=k;

cnt:=0;

for k:=0 to glob-1 do

begin

if (k mod 4000 = 0) or (k>glob-1-8) then

begin

write(k:8, parl(p[k div num])^[k mod num]:8);

cnt:=cnt+1;

end;

if cnt=4 then begin writeln; cnt:=0 end;

end;

writeln;

writeln('вільна пам''ять : ', memavail,

'; найбільша ділянка : ', maxavail);

readln;

end.