Реферат на тему:

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

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. Присвоювання адреси змінної вказівнику називається встановленням його на змінну.

Приклад 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 байти можуть мати 2³²=4294967296=4Г різних станів, якими подається стільки ж адрес.

2. Вільна пам'ять

Основним застосуванням вказівників є робота з вільною пам'яттю. Пам'ять процесу виконання програми поділяється на кілька різних за призначенням частин. Ними є:

• пам'ять для операторів програми,

• статична пам'ять – для глобальних і статичних змінних програми й модулів,

• автоматична пам'ять, або програмний стек – для локальних змінних при виконанні викликів підпрограм.

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

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

Найпростішими засобами керування купою є процедури 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 := <>;

readln ( s );

while s <> '' do

begin

if not ( s належить ss ) then (16.1)

додати s до ss;

readln ( s )

end;

надрукувати елементи ss.

Умова задачі не обмежує кількість елементів у послідовності ss, тому для її зберігання масив непридатний. Скористаємося лінійним зв'язаним списком рядків у вільній пам'яті. Елементами списку є структури вигляду

Рядок

Вказівник на наступний рядок

Вони утворюють послідовність, показану на рис.16.1.

Перший елемент називається головою списку. Поле-вказівник кожного (крім останнього) елемента списку ідентифікує наступний елемент, тобто "прив'язує" його до попереднього.

Якщо розірвати цей зв'язок, змінивши значення вказівника, то наступний елемент списку і всі за ним стають неідентифікованими і перетворюються на "сміття" у вільній пам'яті.

Наприклад, якщо вказівник у першому елементі списку встановити не на другий елемент, а на якусь іншу ділянку пам'яті (пунктирна стрілка на рис.16.1), то на другий елемент (і всі за ним) вже немає посилань. А якщо на щось немає посилань, то його ніби й немає.

За останнім елементом списку немає наступного, тому його вказівник установлений на "ніщо".

Для ідентифікації першого елемента (і списку як структури в цілому) потрібен окремий вказівник, означений у програмі й розташований у її статичній або автоматичній пам'яті. Його називають вказівником на голову списку.

Розглянемо означення та операції, за допомогою яких створюється та обробляється лінійний список. По-перше, нам потрібен тип для елементів лінійного списку. Очевидно, вони являють собою структури, одне з полів яких є вказівником на значення цього самого типу структур. Таким чином, незрозуміло, який же тип слід означити спочатку – тип структур чи вказівників на них? Вихід із цього "замкненого кола" дає така властивість мови Паскаль:

означення типу ^T вказівників дозволяється записувати вище від означення самого типу T.

Ця властивість мови грунтується на тім, що вказівники будь-якого типу мають той самий розмір.

Отже, означимо спочатку тип Tple вказівників, а потім тип елементів Tle зв'язаного списку рядків. Нехай str є ім'ям типу рядків у таких означеннях:

type TPle = ^Tle;

Tle = record

v : str; next : TPle

end

Якщо вказівник p типу TPle установлений на деякий елемент списку, то його можна позначити p^. Вирази p^.v і p^.next задають відповідно змінні типів str та Tple – їх значеннями є рядок, що зберігається в елементі списку, і адреса наступного елемента.

2. Найпростіші операції над списками

За допомогою введених означень почнемо уточнювати алгоритм (16.1). Подамо послідовність ss зв'язаним списком рядків. Для його ідентифікації означимо вказівник pss типу TPle.

Присвоювання ss := <> можна записати як pss := nil.

Опишемо додавання рядка s до послідовності ss. Найпростіший спосіб – додавати елемент з голови списку, тобто рядок ніби записується перед послідовністю. Для цього треба одержати ділянку вільної пам'яті під новий елемент списку, записати в нього новий рядок, "прив'язати" голову списку до нового елемента і зробити цей елемент головою:

procedure add ( s : str; var h : TPle );

var p : TPle;

begin

new ( p ); p^.v := s; p^.next := h; h := p

end

В результаті виконання процедури add у списку з'являється новий перший елемент, і вказівник h на голову списку змінюється. Тому він обов'язково повинен бути параметром-змінною. Оскільки послідовність представлено вказівником pss, саме він повинен бути аргументом у викликах цієї процедури: add ( s, pss ).

Для визначення належності s до ss треба рухатися по елементах списку від його початку доти, поки не натрапимо на елемент із рядком s або не дістанемось останнього елемента. Нехай h^ – черговий елемент списку. Умову переходу до наступного елемента в пошуках s можна виразити так:

( h^.next <> nil ) { черговий елемент не є останнім }

and

( h^.v <> s ) { і зберігає рядок, не рівний s }

Перехід до наступного елемента задає оператор h:=h^.next. Якщо послідовність порожня, то відповідь одержується тривіально. Отже, визначення належності s до ss задається функцією isin:

function isin ( s: str; h: TPle ) : boolean;

begin

if h = nil then isin := false

else

begin

while ( h^.next <> nil ) and ( h^.v <> s ) do

h := h^.next;

{ ( h^.next = nil ) or ( h^.v = s ) }

isin := ( h^.v = s )

end

end

Оскільки список починається елементом pss^, то виклик функції має вигляд isin(s, pss). Зміна вказівника h при виконанні процедури не міняє значення pss і не веде до втрати зв'язку з головою списку, оскільки h є параметром-значенням.

Рядки, представлені в списку, друкуються з його початку просуванням по елементах до кінця:

procedure writelst ( h : TPle );

begin

while h <> nil do

begin writeln ( h^.v ); h := h^.next end

end

Зберемо означення типів str, TPle, Tle та наведені підпрограми в модуль strlist, і запишемо розв'язання задачі (1) у вигляді програми namlist1:

program namlist1(input, output);

uses strlist;

var pss : TPle; s : str;

begin

pss := nil; readln ( s );

while s <> '' do

begin

if not isin ( s, pss ) then add ( s, pss );

readln ( s )

end;

writelst ( pss )

end.

3.3. Додавання до упорядкованого списку

Розглянемо тепер задачу про друкування прізвищ із умовою (2), тобто в лексикографічному порядку. Нехай знак < позначає упорядкування елементів деякого типу T, зокрема, лексикографічне упорядкування рядків. Послідовність a₁, a₂, … , a_n елементів типу T називається упорядкованою, якщо n=1, або n>1 і a_i<a_i+1 за i=1, 2, … , n-1. Зв'язаний список називається упорядкованим, якщо подає упорядковану послідовність a₁, a₂, … , a_n, тобто його перший елемент зберігає a₁, другий – a₂ тощо.

Розглянемо таке додавання нового рядка s до упорядкованого списку ss, що його результатом є упорядкований список.

Вставка в порожній список дає упорядкований список із елемента ss₁.

Якщо s<ss₁, то вставити новий елемент перед першим елементом списку, утворивши послідовність <s, ss₁>.

Якщо s>ss₁, то відшукати такий елемент списку ss_k, що

(ss_k<s і s<ss_k+1) або (ss_k<s і ss_k є останнім).

В обох цих випадках s вставляється після елемента ss_k.

Нехай результат лексикографічного порівняння рядків s1 і s2 обчислюється при виконанні виклику функції lt(s1, s2) – див. задачу 12.9.

Скористаємося процедурою створення нового елемента списку Newelem. Аргументами в її виклику є вказівник типу Tple та вираз типу str. За виконання її виклику створюється новий елемент списку, в його поля записуються значення аргументів, після чого аргумент-вказівник установлюється на цей елемент:

procedure newelem(var p : Tple; z : str);

var pp : Tple;

begin

new(pp); pp^.next:=p; pp^.v:=z; p:=pp

end;

З використанням цієї процедури наведений алгоритм уточнюється такою процедурою:

procedure addord ( s : str; var h : TPle );

var p, pp : TPle; stop : boolean;

begin

if h = nil then {Список порожній – створюється новий елемент }

newelem ( h, s ); {і стає головним}

else

if lt ( s, h^.v ) then { Вставка перед першим елементом – }

newelem ( h, s ) {новий елемент стає головним}

else

begin { Пошуки місця для вставки }

stop := false; p := h;

while ( p^.next <> nil ) and not stop do

if lt(s, p^.next^.v) then stop := true

else p := p^.next;

{ Вставка після елемента p^ за умови, }

{ що s не дорівнює p^.v }

if p^.v <> s then newelem ( p^.next, s );

end

end

Нехай ця процедура разом із допоміжними до неї міститься в модулі strlist. Як бачимо, вона задає вставку елемента після перевірки його відсутності в списку. Тоді в наступній програмі розв'язання задачі з умовою (2) функція isin не потрібна:

program namlist2(input, output);

uses strlist;

var pss : Tple; s : str;

begin

pss := nil; readln ( s );

while s <> '' do

begin

addord ( s, pss );

readln ( s )

end;

writelst ( pss )

end.

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

3.4. Вилучення елемента зі списку

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

1)Порожній список залишається без змін.

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

3)Якщо значення не зберігається в першому елементі, то треба переміститися по зв'язках списку до елемента A, наступний за яким B зберігає задане значення. Потім треба наступний за B елемент "прив'язати" до A та звільнити пам'ять, зайняту B. Якщо елемента із заданим значенням немає, то список не змінюється. Аналогічно п.2 перед розривом зв'язку з елементом B треба встановити на нього допоміжний вказівник.

Наведений алгоритм уточнюється процедурою del:

procedure del ( s : str; var h : TPle );

var p, pp : TPle; stop : boolean;

begin

if h <> nil then

if h^.v = s then

begin

pp := h; h := h^.next;

dispose ( pp ); pp := nil

end

else

begin

p := h; stop := false;

while ( p^.next <> nil ) and not stop do

if p^.next^.v = s then stop := true

else p := p^.next;

{ p^.next = nil – елемента із заданим значенням немає або }

{ stop = true – треба вилучити елемент p^.next^ }

if stop then

begin

pp := p^.next; p^.next := pp^.next;

dispose ( pp ); pp := nil

end

end

end;

4. Списки як рекурсивні об'єкти

Нехай a позначає довільний елемент множини A. Списки її елементів можна означити рекурсивно, а саме:

порожній список <> є списком;

якщо <L> позначає список, то < a <L> > також є списком.

За цим означенням список складається з головного елемента й підсписку, який сам є списком. Відтворимо рекурсивну природу списків означенням типу зв'язаних списків елементів типу T :

type Plist = ^List;

List = record

v : T; subl : Plist

end

Список ідентифікується вказівником на його головний елемент. Але й кожний наступний елемент, ідентифікований полем subl попереднього, вважається головним елементом підсписку. Порожній список указується значенням nil. Виразимо рекурсивно обробку списку за допомогою обробки головного елемента й підсписку, вважаючи для визначеності, що T = integer.

Перевірку належності елемента списку задає рекурсивна функція

function isinr ( a : integer; lp : Plist ) : boolean;

begin

if lp = nil then isinr := false else

{ обробка голови }

if a = lp^.v then isinr := true else

{ рекурсивно перевірити належність елемента підсписку }

isinr := isinr ( a, lp^.subl )

end

Далі ми запишемо рекурсивну функцію addordr додавання елемента в упорядкований список зі збереженням його упорядкованості та повернення вказівника на список, у який вставлено елемент. Але спочатку напишемо функцію newelemr, подібну процедурі newelem з підр.16.3. На відміну від тієї процедури, вказівник на новий елемент повертається з неї.

function newelemr(p : Plist; z : integer) : Plist;

var pp : Plist;

begin

new(pp); pp^.subl:=p; pp^.v:=z;

newelemr:=pp

end;

Наведена функція використовується в функції addordr:

function addordr ( a : integer; lp : Plist ) : Plist;

var p : Plist;

begin

if (lp = nil) or (a < lp^.v) then

{список, ідентифікований lp, стає підсписком }

{ за новим головним елементом }

addordr := newelemr ( lp, a );

else

begin { рекурсивно додати елемент до підсписку }

lp^.subl := addordr ( a, lp^.subl );

addordr := lp

end

end

Рекурсивна функція delr задає вилучення елемента, що подає задане значення, зі списку та повернення вказівника на список, у якому значення a відсутнє:

function delr ( a : integer; lp : Plist ) : Plist;

begin

if lp = nil then delr := nil

else

if lp^.v = a then

{ обробка голови }

begin

delr := lp^.subl; dispose ( lp )

end

else

{ рекурсивно вилучити елемент із підсписку }

begin

lp^.subl := delr ( a, lp^.subl ); delr := lp

end

end

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

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

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.