МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра САПР ДИНАМІЧНІ ОБ’ЄКТИ СКЛАДНОЇ СТРУКТУРИ. ТАБЛИЦІ, БІНАРНІ ДЕРЕВА ЗВІТ до лабораторної роботи № 14 з курсу: “Алгоритмізація та програмування” 1. МЕТА РОБОТИ Мета роботи – ознайомитись із особливостями побудови та застосування динамічних об’єктів складної структури: таблиць і бінарних дерев; з операціями, які виконуються над елементами цих об’єктів. Набути практичних навичок програмування з використанням динамічних об’єктів складної структури зокрема бінарних дерева. 2. ЛАБОРАТОРНЕ ЗАВДАННЯ Програма №1, Варіант №7 Відобразити за допомогою дерева оператор умови: IF <умова> THEN <оператор> ELSE <оператор>; Вивести на друк проміжний результат та результат після видалення гілки ELSE. Блок-схема: / Код програми: program if_tree; uses crt; type tree = ^point; point = record key:string; left:tree; right:tree; entry:string end; function find_tree(kl:string; var tr, rez:tree):boolean; var p, q:tree; b:boolean; begin b:=false; p:=tr; if tr<>nil then repeat q:=p; if p^.key = kl then b:= true else begin q:=p; if kl<p^.key then p:=p^.left else p:=p^.right; end until b or (p=nil); find_tree:=b; rez:=q; end; procedure ins_tree(kl:string; var tr:tree; ent:string); var r, s:tree; begin if not find_tree(kl, tr, r) then begin new(s); s^.key:=kl; s^.entry:=ent; s^.left:=nil; s^.right:=nil; if tr = nil then tr:=s else if kl<r^.key then r^.left:=s else r^.right:=s end end; procedure del_tree(var tr:tree; kl:string); var q:tree; procedure del(var r:tree); begin if r^.right = nil then begin q^.key:=r^.key; q^.entry:=r^.entry; q:=r; r:=r^.left; end else del(r^.right); end; begin if tr = nil then writeln('Нема елемента з таким ключем') else if kl < tr^.key then del_tree(tr^.left, kl) else if kl > tr^.key then del_tree(tr^.right, kl) else begin q:=tr; if q^.right = nil then tr:=tr^.left else if q^.left = nil then tr:=tr^.right else del(q^.left); end end; const k1 = 'if'; k2 = 'then'; k3 = 'else'; var d:tree; s1, s2, s3:string; begin d:=nil; writeln('Введiть умову IF'); readln(s1); writeln('Введiть оператор пiсля THEN'); readln(s2); writeln('Введiть оператор пiсля ELSE'); readln(s3); ins_tree(k1, d, s1); ins_tree(k2, d, s2); ins_tree(k3, d, s3); writeln('Отримане дерево'); writeln(' ',d^.key); writeln(' ',d^.entry); writeln(' ', '/', ' ', '\'); writeln(' ', d^.left^.key, ' ', d^.right^.key); writeln(' ', d^.left^.entry, ' ', d^.right^.entry); del_tree(d, k3); writeln('Нове дерево'); writeln(' ',d^.key); writeln(' ',d^.entry); writeln(' ', '\'); writeln(' ', d^.right^.key); writeln(' ', d^.right^.entry); end. Результати обчислень: / 3. ВИСНОВОК В ході виконання цієї лабораторної роботи я ознайомився із особливостями побудови та застосування динамічних об’єктів складної структури: таблиць і бінарних дерев; з операціями, які виконуються над елементами цих об’єктів, набув практичних навичок програмування з використанням динамічних об’єктів складної структури зокрема бінарних дерева.