Програмування Pascal / лабараторна робота 14

1. МЕТА РОБОТИ

Мета роботи – ознайомитись із особливостями побудови та застосування динамічних об’єктів складної структури: таблиць і бінарних дерев; з операція­ми, які виконуються над елементами цих об’єктів. Набути практичних навичок програмування з використанням динамічних об’єктів складної структури зокрема бінарних дерева.

2. ТЕОРЕТИЧНІ ВІДОМОСТІ

1. Що таке таблиця, які поля містить цей динамічний об’єкт?

Використання комп’ютерної техніки набуло широкого розповсюдження в Автоматизованих інформаційно-пошукових системах (АІПС).

Основне завдання у разі створення таких систем полягає у тому, щоб організувати зберігання великої кількості різних записів та видавати будь-який запис при запиті. Черги та стеки для такого виду робіт не повною мірою задовольняють потреби.

При роботі з Автоматизованою інформаційно-пошуковою системою най­часті­ше використовуються операції пошуку та видачі потрібного запису.

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

Таблиця – це набір іменованих записів. Ім’я запису в таблиці називається ключем.

• Як ключ найчастіше використовуються або цілі додатні числа, або рядки символів однакової

2. Що таке бінарне дерево?

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

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

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

Бінарне дерево можна зобразити так (рис. 2): маємо набір вершин, з кожної вершини виходить не більше як дві стрілки (гілки), спрямовані вліво-вниз та вправо-вниз. Існує одна-єдина вершина, в яку не входить жодна стрілка, ця вершина називається коренем дерева. У всі інші вершини входить лише одна стрілка.

4. Які поля містить динамічний об’єкт, що описує бінарне дерево?

Пошук конкретного запису в дереві – це пошук вершини із заданим ключем.

Запишемо логічну функцію, яка буде ще й визначати вказівник на

шукану вершину. Формальними параметрами функції будуть К – ключ, D –

дерево, у якому ведеться пошук, REZ – параметр-змінна вказівникового типу,

якій присвоюється вказівник на знайдену ланку.

5. Що може бути ключем у бінарному дереві?

Як ключ найчастіше використовуються або цілі додатні числа, або рядки символів однакової

6. Як формується бінарне дерево?

Алгоритм формування дерева такий:

• Надходить черговий запис з ключем К.

• Починаючи з кореня дерева, порівнюємо ключ К з ключем черговоївершини, якщо К > Квер , то переходимо праворуч; якщо К < Квер , то переходимо ліворуч від цієї вершини.

• Якщо стрілки від вершини немає, то приєднюється до цієї вершини нова вершина з ключем К.

8. Яка структура бінарного дерева, що таке вершина або корінь дерева,

що таке гілки дерева?

Видалення запису із заданим ключем здійснюється дуже просто, якщо:

1. Ця вершина є кінцевою (рис. 5, а).

2. Із вершини виходить лише одна гілка (рис. 5, б).

3.ІНДИВІДУАЛЬНЕ ЗАВДАННЯ

Сформувати бінарне дерево, елементами якого є цифри та знаки

арифметичної дії, наприклад, вираз 7+9-2*4. Виконати арифметичні

операції, обійшовши дерево, починаючи з крайнього лівого вузла.

Вивести сформоване дерево та результат обчислень.

4.ТЕКСТ ПРОГРАМИ

program lab14 (input,output);

TYPE

Der=^pointer;

Pointer=record

kl:integer;

zap:char;

pr,lv:der;

end;

VAR

vs,vl:der;

text:char;

kluch:integer;

BEGIN

writeln('Введіть в різні стрічки число та знак');

New(vs);

vs^.kl:=200;

vs^.zap:='*';

vs^.pr:=nil;

vs^.lv:=nil;

REPEAT

readln(kluch);

readln(text);

vl:=vs;

1:while kluch>vl^.kl do

begin

if vl^.pr=nil then

begin

new(vl^.pr);

vl:=vl^.pr;

vl^.kl:=kluch;

vl^.zap:=text;

vl^.pr:=nil;

vl^.lv:=nil;

end

else

vl:=vl^.pr;

end;

while kluch<vl^.kl do

begin

if vl^.lv=nil then

begin

new(vl^.lv);

vl:=vl^.lv;

vl^.kl:=kluch;

vl^.zap:=text;

vl^.pr:=nil;

vl^.lv:=nil;

end

else

vl:=vl^.lv;

end;

if kluch>vl^.kl then goto 1

UNTIL kluch =0;

vl:=vs;

write(vs^.lv^.lv^.zap);

write(vs^.lv^.pr^.zap);

write(vs^.lv^.zap);

write(vs^.pr^.lv^.zap);

write(vs^.pr^.pr^.zap);

write(vs^.pr^.zap);

write(vs^.zap);

END.

ВИСНОВОК

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