27.Організація динамічних структур даних. Двонапрямлені списки. Циклічні списки.

Динамічні структури – структури даних, розмір яких (об’єм пам’яті, що вони займають) може змінюватись у процесі виконання програми. Для організації динамічних структур використовуються динамічні змінні, які створюються та знищуються в процесі виконання програми. Характеризуються: ці змінні явно не описуються, до них неможливо звернутись за допомогою ідентифікатора; пам’ять для цих змінних не виділяється під час формування коду програми, вона виділяється у спеціальній області оперативної пам’яті; доступ до тих змінних виконується за допомогою показників (чи посилань), які стають активними після визначення динамічного об’єкту та містять адресу.

Однозв’язний циклічний список – це однозв’язний лінійний список, в якому останній компонент посилається на перший. Двозв’язний циклічний список – це список, в якому кожен ел. містить посилання на попер. і наст. елемент, в т.ч. останній ел. посилається на перший, а перший – на останній. Двозв’язний лінійний список – скл. з компонентів, що містять 2 покажчика: на попер. і на наст. елемент.

28.Поняття черги і стека. Алгоритм введення та вилучення елементів.

Черга – це однозв’язний лінійний список, в якому компоненти додаються в кінець списку, а вилучаються з вершини, тобто з початку списку. Стек – це однозв’язний лінійний список, в якому компоненти додаються та видаляються лише з його вершини, тобто з початку списку. Максимально допустимі розміри стеку і черги – важливі характеристики реалізації мови програмування, які визначають коло задач, які можна розв’язати. Стеки та черги описують і створюють у пам’яті за допомогою списків. Стек використовують у програмі для реалізації рекурсії. Операції над стеком: додавання елементу до стеку; вилучення елементу із стеку; перевірка на наявність елементів у стеку. Вилучення елементу із черги: nach:=nach^.next; Додавання елемента в поле в черзі:

new(novuy);

readln(<дані>);

novuy^.next:=nil;

kin^.next:=novuy;

kin:=novuy;

29.Графи і дерева.

Дерево – граф, який не містить циклів.

Двійкові дерева можуть бути побудовані на базі елементів з двома адресними полями. Одне з них містить посилання на ліву, а друге – на праву гілку піддерева, що починається з данного вузла. Якщо одна з гілок відсутня, в адресному полі, призначеному для неї, міститься nil. Граф – це складна нелінійна багатозв’язна динамічна структура, яка відображає параметри і зв’язки складного об’єкта. Багатозв’язна структура володіє наступними властивостями: на кожний елемент (вузол, вершину) може бути довільна кількість посилань; кожний елемент може мати зв’язок з

будь – якою кількістю других елементів; кожне ребро, дуга може мати направлення і вагу. Процедури вставки нового вузла в дерево:

Procedure Dob (k:KeyType; var d:TreePtr; zap:data);

{ k - ключ, d - вузол дерева, zap - запись }

Var r,s: TreePtr;

t: DataPtr;

Begin

if not Find(k,d,r) then

begin

new(t); t^:=zap; new(s); s^.key:=k;

s^.ssil:=t; s^.left:=NIL; s^.right:=NIL;

if d = NIL then d:=s

else if k < r^.key

then r^.left:=s

else r^.right:=s;

end; End;