Міністерство освіти і науки України Національний університет «Львівська Політехніка» Кафедра Інформаційних систем та мереж Лабораторна робота №5 на тему Робота з динамічними структурами. Мета роботи: набуття практичних навичок опрацювання таких динамічних структур як зв’язні списки і дерева. Постановка завдання Розробити програми які виконують операції вказані в індивідуальному завданні. Програму для роботи з двонаправленими зв’язними списками. Кожен елемент списку містить посилання на наступний і попередній елемент в списку. Програма повинна забезпечувати ввід і побудову списку. Програму для роботи для роботи з деревами. Кожен елемент дерева містить посилання на батьківський елемент і посилання на елементи-нащадки (необмежена кількість). Програма повинна забезпечувати ввід і побудову дерева. Кожен елемент списку містить інформаційне поле(атрибут) деякого простого типу: символ, стрічка, число. Всі операції над динамічними структурами повинні супроводжуватись відповідним виводом на екран. В контрольних прикладах забезпечити опрацювання структур з 10-20 елементами. Індивідуальні завдання: 8 Доповнення списку з обох кінців. Видалення елемента з дерева за вказаним значенням інформаційного атрибуту.   Текст програми 1: program L5_1; uses Crt; const max=10; type TStack = ^TItem; TItem = record data: integer; next,prev: TStack; end; var c: integer; ch: char; left: boolean; st,tmp,a1: TStack; procedure Add2R(v: integer); Begin New(tmp); tmp^.data:=v; tmp^.next:=nil; st^.next:=tmp; Inc(c); end; procedure Add2L(v: integer); Begin New(tmp); tmp^.data:=v; tmp^.next:=a1^.next; tmp^.prev:=a1; a1^.next:=tmp; Inc(c); end; procedure WriteArr; Begin WriteLn(''); If left then Write('->[') else Write(' ['); st:=a1^.next; while st^.next<>nil do Begin Write(st^.data); st:=st^.next; If st^.next<>nil then Write(','); end; If left then WriteLn('] ') else WriteLn(']<-'); WriteLn; If c>0 then WriteLn(' ',c,' elements in list') else WriteLn(' List is empty'); WriteLn; WriteLn(' [Left]\[Right] - change direction'); WriteLn(' [+] - add random element'); WriteLn(' [Esc] - exit'); end; Begin Randomize; New(a1); New(st); st^.data:=random(100); st^.prev:=a1; st^.next:=nil; a1^.next:=st; c:=1; left:=true; repeat ClrScr; WriteArr; ch:=ReadKey; case ch of #75: left:=true; #77: left:=false; '+': If left then Add2L(random(100)) else Add2R(random(100)); end; until ch=#27; end. Результати виконання програми:


Текст програми 2: program L5_2; uses Crt; type Tree = ^S; S = record data: integer; left, right: tree; end; var del,cnt,c,i: integer; t: Tree; procedure AddElem(n: integer; var tr: Tree); procedure Add(var trr:Tree); begin if trr=nil then begin new(trr); trr^.data:=n; trr^.left:=nil; trr^.right:=nil; end else if trr^.data>n then Add(trr^.left) else if trr^.data<n then Add(trr^.right); end; begin Add(tr); end; procedure WriteTree; procedure WriteItem(p: Tree); Begin if p<>nil then begin if p^.left<>nil then write('L: ') else write('R: '); WriteLn(p^.data); WriteItem(p^.left); WriteItem(p^.right); Inc(c); end; end; Begin c:=0; WriteItem(t); WriteLn(c,' elements in the tree'); WriteLn('Enter item data to delete it(-1 to exit):'); end; procedure Delete(e: integer; var tr: Tree); procedure Go(var tr: Tree); var left,right: Tree; begin if tr<>nil then begin Go(tr^.left); Go(tr^.right); if tr^.data=e then begin left:=tr^.left; right:=tr^.right; dispose(tr); tr:=nil; if left=nil then tr:=right else if right=nil then tr:=left else begin tr:=left; while left^.right<>nil do left:=left^.right; left^.right:=right; end; end; end; end; begin Go(tr); end; {--------=[MaiN]=--------} Begin Randomize; ClrScr; WriteLn('How many elements do you want to add to the tree?'); ReadLn(cnt); For i:=1 to cnt do AddElem(random(100),t); repeat ClrScr; WriteTree; ReadLn(del); If del<>-1 then Delete(del,t) else Exit; until false; end. Результати виконання програми:



Висновки: При виконанні даної роботи я набув практичних навичок опрацювання таких динамічних структур як зв’язні списки і дерева.