1.Виділення та звільнення пам’яті при роботі з вказівниками.

Звільнення пам’яті

Для типізованих вказівників визначена процедура Dispose(Ідентифікатор вказівника)

Var Ptr :^integer; ............ new(ptr); ............ dispose(ptr);

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

нетипізованих вказвників:

Процедура

GetMem

– Формат виклику: GetMem(P,Size); Виділяє вказівнику P

блок пам'яті заданого розміру Size. За одне звертання мож-

на виділити не більш 65521 байт пам'яті. Якщо немає віль-

ного блоку пам'яті придатного розміру, то при виклику

GetMem виникає помилка.

Процедура

FreeMem

– Формат виклику: FreeMem(P,Size); Звільняє виділений

вказівнику P блок пам'яті. Примітка – Звільнятися повинно

рівно стільки пам'яті, скільки було виділено процедурою

GetMem, інакше відбувається помилка.

   

Виділення пам'яті здійснюється спеціальним оператором New, наприклад:

New(T);

Після цієї операції вказівник Т придбає значення адреси пам'яті для дійсної змінної. Щоб отримати доступ до цієї області пам'яті, треба знак ^ записати після вказівника, наприклад:

Т^;=16.4;

Writeln(T^);

Оскільки динамічна змінна не має імені (а отже не описується в блоці var), то на початку роботи програми пам’ять під дану змінну не виділяється. А відповідна змінна-вказівник ні нащо не вказує. Коли змінна-вказівник ні нащо не вказує, то говорять, що вона вказує на nil.

Щоб виділити пам’ять, необхідно виконати процедуру new(x), де х – змінна-вказівник.

Після виконання даної процедури (new(x)) вказівник x буде вказувати на комірку пам’яті відповідного типу.

Н априклад,

V ar x:^integer;

Begin

……..

New(x);

…….

2. Поняття об’єктно-орієнтованого програмування, класу, об’єкта. (див. Білет № 30 , питання 2)

Білет № 28

1. Класифікація динамічних структур даних.

Стек - Динамічна структура даних, що являє собою впорядкований набір елементів, в якій додавання нових елементів і видалення існуючих виробляється з одного кінця, званого вершиною стека.

За визначення, елементи витягуються з стека в порядку, зворотному їх додаванню в цю структуру, тобто діє принцип "останній прийшов - перший пішов ".

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

Стек можна організувати на базі будь-якої структури даних, де можна зберігати кількох однотипних елементів і де можна реалізувати визначення стека: лінійний масив, типізований файл, односпрямований або двонаправлений список. У нашому випадку найбільш відповідним для реалізації стека є односпрямований список, причому як вершини стека виберемо початок цього списку.

Виділимо типові операції над стеком і його елементами:

додавання елемента в стек;

видалення елемента з стека;

перевірка, чи порожній стек;

Черга в програмуванні — динамічна структура даних, що працює за принципом "перший прийшов - перший пішов" (англ. FIFO — first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові.

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

Деревом називається динамічна структура, у якій кожен вузол містить не один, а декілька вказівників на декілька інших вузлів.

Кореневий вузол (корінь дерева) – це самий верхній вузол (вузол a – кореневий) . Якщо з деякого вузла (наприклад, вузла а) вказівники вказують на інші вузли (в нашому випадку на вузли b та c), то такий вузол називають предком. Вузли ж на які вказують вказівники від предка називаються потомками.

Лівий потомок вузла а – вузол b

Правий потомок – вузол c.

Вузли b та c мають спільного предка – вузол а

Якщо вузол не має потомків, то такий вузол називають листком дерева

Списки - це дискретні, зв'язані, динамічні, рекурсивні інформаційні структури.

Для списків характерно:

• Складаються з елементів того самого типу. Тип елементів може бути будь-яким.

• Зв'язок між елементами і доступ до списків здійснюється за допомогою типізованих вказівників. При цьому, на ряду з інформацією кожен елемент списку повинний мати вказівники на наступний чи попередній, або на наступний і попередній елементи списку.

• Кількість елементів списку заздалегідь не задається. Воно може змінюватися в процесі виконання програми. Розмір одного елемента списку не може перевищувати 64 Кбайт.

• При описі типу - список, використовується рекурсія.

• Доступ до елементів списку послідовний.

Лінійний та циклічний однозв'язаний список. Кожний окремий елемент такої структури містить крім одного або декількох інформаційних полів поле, в якому зберігається адреса наступного елементу. Останній елемент лінійного списку містить порожнє посилання (nil), тоді як останній елемент циклічного списку містить посилання на перший елемент. Такі структури утворюються та змінюються тільки під час роботи програми.

Двозв'язний список - такий, кожний елемент якого містить два посилання - на попередній та на наступний елементи. Перший елемент містить пусте посилання на попередній елемент, а останній - пусте посилання на наступний елемент. Такий список також можна зробити циклічним.

Існування подвійного посилання (на попередній та наступний елементи) надає можливість рухатись по списку як у прямому так і у зворотньому напрямках, але трохи ускладньює процедури вилучення та додавання елементів.

Двійкові дерева можуть також бути побудовані на базі елементів з двома адресними полями. Одне з них містить посилання на ліву, а друге – на праву гілку піддерева, що починається з данного вузла. Якщо одна з гілок відсутня, в адресному полі, призначеному для неї, міститься nil.