із записами, а ребра – з вказівками, поставивши у відповідність цій структурі граф. Ребра такого графа будуть характеризуватися напрямами, що відповідають тим вказівкам, які вони відображають. Такий граф називається орієнтованим. З будь-якого графа завжди можна виділити дерево – сукупність (підмножину) ребер графа, що пов'язує всі вершини, однак не утворює замкнутих контурів (циклів). Дерева можна вибирати багатьма способами.
Для зображення таблиці використовуватимемо двійкові дерева. Двійкове дерево характеризується тим, що з кожної вершини виходить не більше двох стрілок, і є одна вершина – корінь дерева, в який не напрямлена жодна стрілка, У всі ж інші вершини напрямлено по одній стрілці. Приклад двійкового дерева показаний на рис. 25.
Рис. . Двійкове дерево
Ліва і права стрілки не є взаємозамінними, тому наступні два двійкові дерева різні (рис. 26).
Рис. . Незбіжні елементи двійкового дерева
Під час формування дерева записів ліва стрілка відповідає вказівці на запис з меншим ключем, права – на запис з більшим ключем.
1. Зображення таблиці двійковим деревом. У цьому випадку кожна вершина дерева – це запис, що містить чотири поля: ключ запису, вказівку на ліву вершину, вказівку на праву вершину і вказівку на текст запису, який зберігається окремо (як прийнято для таблиць).
Двійкове дерево наведемо у вигляді таких описів типу:
type
Tekst={ім'я або задания типу запису з текстом};
RT=^Tekst;
L=^Node;
Nodearecord
Key: Char;
Left, Right: L;
TXT: RT;
end;
2. Шукання запису в дереві. Опишемо логічну функцію шукання запису в дереві за ключем з побічним ефектом " вказівкою на вершину, що містить відшуканий запис. Формальні параметри функції: k – ключ; Tree – вказівка на дерево, у якому ведуть шукання; Res – вказівна змінна, що містить вказівку на знайдений вузол.
program Form9;
type
Tekst=Char;
RT=^Tekst;
L=^Node;
Node=record
Key: Char;
Left, Right; L;
TXT: RT;
end;
function SeekTree(k; Char; Tree: L; var Res: L): Boolean;
var p, q: L;
b; Boolean;
begin
b:=false;
p:=Tree;
If ponil then
repeat If p^.key=k then
b:=True
else
If p^.key<k then
p:=p^.Right
else p:=p^.Left
until b or (p=nil);
SeekTree:=b; Res:=p;
end;
begin
end.
Наведена функція побудована на ітеративному методі.
Зображення таблиці у вигляді двійкового дерева дає змогу значно прискорити шукання потрібного запису. У випадку збалансованого дерева, тобто такого, коли з кожної вершини відходить по два ребра, кількість перебирань вершин пропорційне, як і у випадку дихотомічному шукання, до log2N.
Приклад збалансованого двійкового дерева показаний на рис. 27.
Рис. . Збалансоване двійкове дерево
Чим більше в дереві поодиноких стрілок, тим більша кількість перебирань. У граничному випадку двійкове дерево має одну гілку. Це трапляється, коли записи надходили в таблицю в порядку зростання ключів. Тоді кількість перебирань, як і для однонапрямленого списку, пропорційне до N/2.
Є програми, які дають змогу незбалансоване дерево зводити до збалансованого.
Висновки
Отже, використання при програмуванні статичних об'єктів (об'єкти, породжувані безпосередньо перед виконанням програми, які існують на протязі всього часу її виконання і розмір значень яких (об'єм машинної пам'яті) не змінюється по ходу виконання програми) може викликати певні труднощі, особливо з погляду отримання ефективної програми, а також ефективність буває надзвичайна важливою при рішенні ряду задач. Річ у тому, що іноді ми наперед (тобто на етапі складання програми) не знаємо не тільки розміру значень того або іншого програмного об'єкту, але навіть і того, чи буде потрібен в тій ситуації цей об'єкт чи ні.
Такого роду програмні об'єкти, які виникають в процесі виконання програми або розмір яких визначається (або змінюється) при виконанні програми, називаються динамічними об'єктами (або динамічними змінними).
У мові програмування Паскаль для роботи з динамічними об'єктами передбачений спеціальний тип значень – так званий посилальний тип. Значенням цього типу є посилання на який-небудь програмний об'єкт, по якому здійснюється безпосередній доступ до цього об'єкту. На машинній мові таке посилання якраз і представляється покажчиком місця в пам'яті (адреси), відповідного об'єкту.
У Паскалі з метою підвищення надійності програм в задаванні посилального типу обов'язково повинен фігурувати тип значень тих динамічних програмних об'єктів, на які вказуватимуть змінні задаваного посилального типу.
У мові Паскаль є засоби створення динамічних структур даних, які дозволяють під час виконання програми:
утворювати об'єкти;
виділяти для них пам'ять;
знищувати, коли в них зникає необхідність.
Інша назва динамічної пам'яті – купа.
Дані в динамічній пам'яті розміщують із використанням покажчиків. Покажчик – це посилання на певний елемент пам'яті, починаючи з якого записується значення змінної, тому дані такого типу називаються ще й посилальним типом даних.
Проте в Турбо Паскалі можна повідомляти покажчик і не пов'язувати його з конкретним типом даних. Такий покажчик називається нетипізованим. Для його повідомлення служить стандартний тип pointer. Структура і тип таких даних можуть змінюватися під час виконання програми.
При роботі з покажчиками обов'язкові два етапи:
1. повідомлення покажчика;
2. формування динамічних даних, пам'ять яких відводиться під час виконання програми.
Для роботи з покажчиками використовуються наступні процедури:
New(P) – процедура, яка створює в динамічній пам'яті нову змінну. Р – покажчик змінної того типа, якого треба створити. Кожна окрема процедура new може створити тільки одну динамічну змінну.
Dispose(P) – процедура, що дозволяє повернути в купу ділянку пам'яті, зайняту об'єктом з покажчиком Р.
Параметрами процедур new і dispose може бути тільки типізований покажчик. Для роботи з нетипізованими покажчиками використовуються аналогічні процедури:
GetMem(P,Size) – резервування пам'яті;
FreeMem(P,Size) – звільнення пам'яті.
Тут Р – нетипізований покажчик, Size – розмір у байтах необхідної або звільненої частини купи ( до 65521 байт).
Посилальною змінною може бути привласнене «порожнє» значення адреси, позначене службовим словом nil, що означає, що посилальна змінна не вказує ні на один динамічний об'єкт. Це привласнення можна робити до виконання процедури new. Значення nil