МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра САПР Звіт до лабораторної роботи №14 на тему: «Динамічні об’єкти складної структури. Таблиці, бінарні дерева» 1. Мета роботи Ознайомитися із особливостями побудови та застосування динамічних об’єктів складної структури: таблиць і бінарних дерев; з операціями, які виконуються над елементами цих об’єктів. Набути практичних навичок програмування з використанням динамічних об’єктів складної структури зокрема бінарних дерев. 2. Теоретичні відомості Що таке таблиця, які поля містить цей динамічний обєкт ? Таблиця – набір іменованих записів. Найпростіший спосіб подання таблиці – однонапрвлений список: ключ; текст запису; вказівник на наступну ланку. У чому полягає метод дихотомічного пошуку? Над таблицями якого типу він використовується? Пошук, під час якого впорядкована послідовність даних ділиться на дві рівні взаємовиключні частини, одна з яких, що не задовольняє умови пошуку, відкидається, а процес пошуку повторюється на залишеній частині аналогічним чином до завершення пошуку. Тобто, якщо в таблиці є N записів, то для пошуку потрібного ключа необхідно проглянути N/2 записів. Використовується в одно направлених списках. Що таке бінарне дерево? Бінарне дерево — структура даних у вигляді дерева, в якому кожна вершина має не більше двох гілок. Зазвичай такі гілки називаються правим та лівим. Які поля містить динамічний об’єкт, що описує бінарне дерево? Кожна ланка бінарного дерева буде записом з 4-ма полями: ключ запису – KLYTH; PR – вквазіник а вершину вправо-вниз; LV – вказівник на вершину вліво-вниз; ZAP – вказівник на текст запису. Що може бути ключем у бінарному дереві? Ключем може бути будь-який тип змінних. Як формується бінарне дерево? Алгоритм формування бінарного дерева: надходження запису з ключем К. починаючи з кореня дерева, порівнюємо ключ К з ключем чергової вершини, якщо К>Kвер, то переходимо праворуч; якщо К<Квер, то переходимо ліворуч від цієї вершини. якщо стрілки від вершини немає, то приєднюється до цієї вершини нова вершина з ключем К. Для чого перед формуванням дерева необхідно робити вказівник на корінь дерева NIL? Вказівник на наступні елементи робимо пустим, тобто NIL, тому що перед занесенням у елемент, потрібно його перевірити, а доти ми не знаємо, що саме входитиме до наступного елемента. Яка структура бінарного дерева, що таке вершина або корінь дерева, що таке гілки дерева? Структура: набір вершин, з кожної вершини виходить не більше як дві стрілки (гілки), спрямовані вправо-вниз та вліво-вниз. Існує одна вершина, в яку не входить жодна стрілка, ця вершина називається коренем дерева. У всі інші вершини входить лише одна стрілка (гілка). Як визначити по правій чи лівій гілці дерева треба йти? Починаючи з кореня дерева, порівнюємо ключ К з ключем чергової вершини, якщо К>Kвер, то переходимо праворуч; якщо К<Квер, то переходимо ліворуч від цієї вершини. Як вставити вузол у дерево, які процедури або функції можна використати? При вставці нового елемента спочатку необхідно знайти вершину, до якої «підвішується» новий запис. Алгоритм пошуку потрібної вершини такий самий, що й під час пошуку вершини із заданим ключем. Вершину буде знайдено тоді, коли черговий вказівник PR або LV залежно від напрямку буде дорівнювати NIL. Використати функцію PRED не можна, оскільки там не фіксується вершина, вказівник якої PR або LV є NIL. Як видалити відповідний вузол з дерева? Видалення запису із заданим ключем здійснюється просто, якщо вершина є кінцевою або із вершини виходить лише одна гілка. Складніше, коли з вершини, яку необхідно видалити, виходить два ребра. Щоб видалити та замінити елемент, потрібно використати інший елемент, котрий має лише одну гілку, до якого можна під єднати інший елемент. Якщо потрібно приєднати праву гілку лівого піддерева, то необхідно знайти крайній правий елемент цього піддерева, який має значення вказівника вправо NIL. Якщо видалити елемент з правого піддерева, то необхідно знайти крайній лівий елемент, що має вказівник вліво NIL. Як здійснюється пошук елемента у дереві? Як найкраще реалізувати алгоритм пошуку? Пошук конкретного запису в дереві – це пошук вершини із заданим ключем. Функція, яка визначає ще й вказівник на шукану вершину: FUNCTION PDER (K:INTEGER; VAD D, REZVKL): BOOLEAN; VAR P:VKL; B:BOOLEAN; BEGIN B:=FALSE; P:=D; IF D <> NIL THEN REPEAT IF P^.KLYTH=K THEN B:=TRUE ELSE IF K<P^.KLYTH THEN P:=P^.LV ELSE P:=P^.PR UNTIL B OR (P=NIL); PDER:=B; REZ:=P; END.