Така ситуація не відновлює дані, хоча Heap ptr вказує на вершину раніше зайнятої кучі. Утворюються пустоти, в яких не вдасться розмістити нові динамічні змінні.
При розміщенні динамічних змінних у пам'яті, потрібно враховувати, що неможливість чергової операції створення динамічної змінної із-за відсутності місця в кучі, призводить до зупинки програми, тому потрібно контролювати стан динамічної пам'яті на наявності вільного простору. Для цього Pascal має стандартні функції без параметрів.
MemAvail:longint;
MaxAvail:longint;
MemAvail повертає своїм значенням загальний розмір вільної пам'яті в перерахунку на 8-мибайтні блоки. Цей розмір видається в байтах.
MaxAvail повертає своїм значенням розмір максимальної неперервної вільної ділянки в кучі в перерахунку на 8-мибайтні блоки. Таким чином при операціях багатократного створення динамічних змінних варто користуватися наступною перевіркою
if MaxAvail>=sizeof(<базовий тип>) then New(…)
else writeln(‘немає місця’);
Тема: Динамічні структури даних.
Використання вказівники та динамічних змінних дозволяє будувати нові структури даних, які називаються динамічними. Вони розміщуються в динамічній частині пам'яті і можуть як завгодно змінювати свій розмір, тобто кількість елементів, таким чином дечим подібні до типізованих файлів, які теж можуть змінювати свій розмір. Проте є деякі принципові відмінності:
1. Файли розміщуються в зовнішній пам'яті, а динамічні структури в оперативній.
2. Типізовані файли фактично є файлами прямого доступу, що означає довільний доступ до елементів. В динамічних структурах доступ до елементів виключно послідовний.
Зв’язок між елементами в динамічних структурах реалізуються при допомозі вказівників, кожен елемент такої структури в свою чергу є складеною структурою: інформаційна частина містить корисні дані, а вказівна містить адресу наступного елемента.
Тема: Списки. Атрибути списків.
Згадані вище динамічні структури даних в програмуванні називають списками. Під списком розуміється деяка послідовна структура даних, кожен елемент якої містить два компоненти: інформаційне поле та вказівні поля. Саме через вказівники здійснюється зв’язок елементів у списку.
Доступ до всього списку реалізується через фіксований вказівник у вигляді статичної змінної на перший елемент списку – голова списку. Всі решта елементів утворюють так званий хвіст списку. Останній елемент списку переважно вказує в nil – це є ознака кінця списку.
В залежності від кількості вказівних полів в кожному елементі списку, розрізняють однозв’язні списки (один вказівник) п-зв’язні списки (п вказівників).
Крім такого поділу по зв’язності, списки бувають лінійними, деревами, графами та ін.
В двонапрямлених списках доступ до елементів однаково здійснюється при русі від першого до останнього за вказівником next, або від останнього до першого за вказівником prev.
Якщо елементи списку мають два вказівних поля, але список не лінійних, а розгалужений, то отримується список у вигляді бінарного дерева.
Тема: Лінійні однонапрямлені списки.
Такі списки складаються з елементів, які є комбінацією двох полів: інформаційного та вказівного на наступний елемент.
Вказівне поле матиме тип вказівника на базовий тип, що є типом всього елемента списку, при цьому допускається рекурсивність оголошення типу списку.
TYPE
list1=^el_list1;
el_list1=record
inf:integer;
next:list1
END;
В програмі доступ до таких однонапрямлених змінних здійснюється через фіксований вказівник – статичну змінну. Ця змінна не може змінювати свого значення, оскільки може призвести до втрати адреси всього списку. Останній елемент списку вказує в nil.
Формування списку здійснюється при допомозі процедур створення динамічних змінних, при цьому кожний новий елемент зв’язується вказівником з попереднім елементом або своїм вказівником із наступним. Формування списку може здійснюватися за двома принципами:
Стек.
Черга.
При формуванні списку за правилом стеку: кожен новий елемент ставиться у список в якості голови.
Якщо список формується за правилом черги, то кожен новий елемент добавляється у хвіст списку. Фіксований вказівник вказує на один і той же елемент, при цьому потрібно мати ще один фіксований вказівник на останній елемент списку.
Відмінність між списками чергами і стеками лише у порядку заповнення елементами. Всі решта операцій по переміщенню, вставці, видаленню абсолютно однакові.
Традиційно, над лінійними списками виконують наступні дії:
Дата добавления: 2015-09-11; просмотров: 23 | Поможем написать вашу работу | Нарушение авторских прав |