Program LAB11_1;
{$APPTYPE CONSOLE}
uses Sysutils;
TYPE Tvector = array[1..1] of integer;
VAR vt: ^ Tvector; {Типізований вказівник}
pn: Pointer; { Нетипізований вказівник}
n, i, j: integer;
BEGIN
{Введення початкових даних}
writeln(‘Введіть розмір масиву n<=200’);
readln(n);
{Розрахунок розміру пам’яті для розміщення }
{n елементів масиву}
j:=n*sizeof(integer);
{Виділення динамічної пам’яті}
GetMem (pn, j);
vt:=pn;
writeln(‘Введіть елементи масиву ’);
for i:=1 to n do
read(vt^[i]);
{Виведення масиву по п’ять елементів у рядку}
for i:=1 to n do
if i mod 5 <> 0 then write(vt^[i]:6)
else writeln(vt^[i]:6);
{Звільнення динамічної пам’яті}
FreeMem(pn, j);
readln;
END.
Зв’язані динамічні дані – це структури із зв’язаних однорідних елементів. Елемент зв’язаної структури динамічних даних складається з двох частин: даних і вказівників (Рис 11.1).
Рис 11.1. Елемент зв’язаної структури динамічних даних
Дані можуть бути як простими, так і структурованими. Наприклад,
TYPE Tdan1 = integer;
Tdan2 = record
p: string[20];
rn: word;
pos: string[15];
end;
dan1 = record
x1: Tdan1;
v1:Tvk1;
end;
dan2 = record
x2: Tdan2;
v2:Tvk2;
end;
Tvk1 = ^dan1;
Tvk2 = ^dan2;
VAR p1: Tvk1;
P2: Tvk2;
BEGIN
. . . . . . . . . . . .
p1^.x1:=5;
p2^.x2.p:=’Шевченко’;
. . . . . . . . . . .
END.
У наведеному прикладі для типу Tdan1 елементами динамічних даних будуть цілі числа, а для Tdan2 – записи. Звернення до елементів динамічних даних здійснюється за допомогою складених імен.
До зв’язаних динамічних структур даних належать: списки, черги, стеки, дерева.
Список– це динамічна структура лінійно зв’язаних елементів даних. При роботі зі списками використовуються вказівники на початок (L) і кінець (K) списку. Списки бувають: однозв’язні, зі зв’язком з наступним (Рис 11.2) або попереднім (Рис 11.3) елементом; однозв’язні циклічні, зі зв’язком останнього елемента з першим (Рис 11.4); двозв’язні, зі зв’язками з наступним і попереднім елементами одночасно (Рис 11.5).
L
Рис 11.2. Однозв’язний список.
Зв’язок з наступним елементом.
L
Рис 11.3. Однозв’язний список.
Зв’язок з попереднім елементом.
L
Рис 11.4 Однозв’язний циклічний список.
L K
Рис 11.5 Двозв’язний список.
Над списками виконуються операції:
· створення;
· включення нового елемента перед або після 
-го елемента;
· включення нового елемента перед або після елемента з заданим значенням;
· вилучення елемента перед або після -го елемента;
· вилучення елемента перед або після елемента з заданим значенням;
· вилучення елемента з заданим значенням;
· упорядкування елементів списку;
· виведення елементів списку;
· та інші.
Черга– це частковий випадок однозв’язного списку, з якого елементи вилучаються спочатку і записуються в кінець. Черга працює за принципом першим прийшов – першим пішов. Для роботи з чергою необхідні операції:
· додати елемент;
· вибрати елемент;
· очистити чергу;
· перевірити, чи черга порожня.
Стек– це частковий випадок однозв’язного списку, в який елементи додаються і вибираються з одного кінця. Стек працює за принципом останнім прийшов – першим пішов. Для роботи зі стеком необхідні операції:
· додати елемент;
· вибрати елемент;
· очистити стек;
· перевірити, чи стек порожній.
Дерево – це динамічні дані ієрархічної структури, які відображують структурні відношення між елементами.
Елементи дерева називаються вершинами або вузлами, один з яких називається коренем. Дерева можуть мати довільну ієрархічну структуру. Оскільки від дерева довільної структури завжди можна перейти до бінарного дерева, то розглядатимемо бінарні дерева. У бінарному дереві з кожним вузлом зв’язані два інших вузли Рис. 11.6.
З деревами можна виконувати такі операції:
· створення;
· обхід і пошук елемента;
· пошук шляхів;
· визначення кількості входжень елемента у дерево;
· виведення елементів дерева;
· інші операції.
Рис.11.6 Бінарне дерево
Приклад.Розробити програму, яка створює бінарне дерево, елементи якого цілі числа. Виводить це дерево по рангах та обчислює суму елементів вузлів.
Для побудови дерева використаємо алгоритм пошуку елемента вузла за його номером і підключення до нього чергового вузла. Будемо рухатися починаючи від кореня дерева по лівих зв’язках, а праві, якщо вони є будемо записувати у стек. Якщо шлях по лівому зв’язку закінчується, то вибираємо правий зв’язок із стеку і знову йдемо по лівому зв’язку. Процедура завершується якщо вузол знайдено або, якщо при черговій спробі вибрати зв’язок із стеку виявляється що він порожній тоді це буде означати що вузла з таким номером у дереві немає.
Для виведення дерева по рангах використаємо чергу. Спочатку зв’язки кореня дерева поміщаємо у чергу, а потім
вибираючи зв’язки з черги виводимо чергову вершину, а її зв’язки поміщаємо у чергу. Процес завершується як тільки черга стає порожньою.
Для обчислення суми використаємо алгоритм обходу вершин дерева аналогічно як і при створенні дерева.
Створимо програмний модуль не пов’язаний з формою з ім.’ям ModDd11_1 і розмістимо в ньому такі процедури і функції:
· Procedure Vstek(var S:Tvst; Vkd:Tvd); – помістити елемент в стек;
· Procedure Izstek(var S:Tvst; var Vkd:Tvd); – вибрати елемент із стеку;
· Function Pustostek(var S:Tvst):Boolean; – перевірка чи стек порожній;
· Procedure Ochstek(var S:Tvst); – очистка стеку;
· Procedure Vchr(var pch,kch:Tvch; Vkd:Tvd; zv:integer); – помістити елемент в чергу;
· Procedure Izchr(var pch,kch:Tvch; var Vkd:Tvd; var zv:integer); – вибрати елемент із черги;
· Function Pustochr(var pch,kch:Tvch):Boolean; – перевірка чи черга порожня;
· Procedure Kopchr(var pch,kch,pch1,kch1:Tvch); – копіювання черги;
· Procedure Stvder(var T:Tvd; nd:integer; dd:Tel; zv:integer; var pr:integer); – створення дерева;
· Procedure Drukder(var T:Tvd; var Lst:TStringList); – виведення дерева;
· Function SumDR(var T:Tvd):Tel; – обчислення суми елементів дерева.
unit ModDd11_1;
interface
uses Classes, SysUtils;
Type
{Дерево}
Tel=integer;
Tvd=^Der;
Der=Record
Nv:integer;
Dv:Tel;
Vl:Tvd;
Vr:Tvd;
end;
{Стек}
Tvst=^St;
St=Record
Vd:Tvd;
Vst:Tvst;
end;
{Черга}
Tvch=^Ch;
Ch=Record
Vd:Tvd;
Zv:integer;
Vch:Tvch;
end;
Procedure Vstek(var S:Tvst; Vkd:Tvd);
Procedure Izstek(var S:Tvst; var Vkd:Tvd);
Function Pustostek(var S:Tvst):Boolean;
Procedure Ochstek(var S:Tvst);
Procedure Vchr(var pch,kch:Tvch; Vkd:Tvd; zv:integer);
Procedure Izchr(var pch,kch:Tvch; var Vkd:Tvd; var zv:integer);
Function Pustochr(var pch,kch:Tvch):Boolean;
Procedure Kopchr(var pch,kch,pch1,kch1:Tvch);
Procedure Stvder(var T:Tvd; nd:integer; dd:Tel; zv:integer;
var pr:integer);
Procedure Drukder(var T:Tvd; var Lst:TStringList);
Function SumDR(var T:Tvd):Tel;
implementation
Var T:Tvd=nil; {Вказівник на корінь дерева}
S:Tvst=nil; {Вказівник на вершину стеку}
pch:Tvch=nil; {Вказівник на початок черги}
kch:Tvch=nil; {Вказівник на кінець черги}
{Процедура включення в стек}
Procedure Vstek(var S:Tvst; Vkd:Tvd);
var q:Tvst;
begin
new(q); q^.vd:=vkd; q^.vst:=s; s:=q;
end;
{Процедура вибору із стеку}
Procedure Izstek(var S:Tvst; var Vkd:Tvd);
var q:Tvst;
begin
q:=s; Vkd:=q^.vd; s:=q^.vst; dispose(q);
end;
{Функція перевірки стеку}
Function Pustostek(var S:Tvst):Boolean;
begin
if s=nil then Result:=false else Result:=true;
end;
{Процедура очистки стеку}
Procedure Ochstek(var S:Tvst);
var q:Tvst;
begin
while s<>nil do
begin q:=s; s:=s^.vst; dispose(q); end;
end;
{Процедура установки в чергу}
Procedure Vchr(var pch,kch:Tvch; Vkd:Tvd; zv:integer);
var q:Tvch;
begin
new(q); q^.vd:=vkd; q^.zv:=zv; q^.vch:=nil;
if pch=nil then begin pch:=q;kch:=q; end
else begin kch^.vch:=q;kch:=q; end;
end;
{Процедура вибору із черги}
Procedure Izchr(var pch,kch:Tvch; var Vkd:Tvd; var zv:integer);
var q:Tvch;
begin
q:=pch; Vkd:=q^.vd; zv:=q^.zv; pch:=q^.vch; dispose(q);
end;
{Функція перевірки черги}
Function Pustochr(var pch, kch:Tvch):Boolean;
begin
if pch=nil then Result:=false else Result:=true;
end;
{Процедура копіювання черги}
Procedure Kopchr(var pch,kch,pch1,kch1:Tvch);
var p,q:Tvch;
begin
pch:=nil; kch:=nil; q:=pch1;
while q<>nil do
begin new(p); p^.Vd:=q^.vd; p^.Zv:=q^.zv; p^.Vch:=q^.vch;
if pch=nil then begin pch:=p;kch:=p;end else kch:=p;
pch1:=q^.vch;
dispose(q);
q:=pch1;
end;
end;
{Процедура створення бінарного дерева}
Procedure Stvder(var T:Tvd; nd:integer; dd:Tel; zv:integer; var pr:integer);
var p,q:Tvd;
S:Tvst;
F:Boolean;
begin
S:=nil; {Створення вузла дерева}
new(q); q^.Nv:=nd; q^.Dv:=dd; q^.Vl:=nil; q^.Vr:=nil;
if T=nil then begin T:=q; pr:=0;end {Корінь дерева}
else
{Пошук вузла до якого потрібно під’єднатися}
begin pr:=2; f:=true; p:=T;
while (p<>nil) and f do
begin
if p^.Nv=zv then begin {Включення вузла}
if p^.Vl=nil then {Лівий зв'язок}
begin pr:=0; f:=false; p^.vl:=q;end
else {Правий зв'язок}
begin if p^.Vr=nil then begin pr:=0; f:=false; p^.vr:=q;end
else begin f:=false; pr:=1;end; {Зв’язки зайняті}
end;
end
else begin {Перехід до наступного вузла}
if p^.Vl<>nil then {Йти вліво, праву вітку, якщо є, у стек}
begin if p^.Vr<>nil then Vstek(S, p^.Vr); p:=p^.Vl; end
else {Йти вправо якщо є зв'язок}
begin if p^.Vr<>nil then begin p:=p^.Vr; end
else {Зв'язків немає вибрати із стеку}
begin if Pustostek(S) then Izstek(S, p)
else p:=nil; {Стек порожній}
end;
end;
end;
end;
end;
if pr>0 then Dispose(q); {Елемент не включено}
if S<>nil then Ochstek(S); {Очистка стеку}
end;
{Процедура виведення бінарного дерева}
Procedure Drukder(var T:Tvd; var Lst:TStringList);
var nr,zv:integer;
Vd:Tvd;
c:string;
pch,kch:Tvch;
pch1,kch1:Tvch;
begin
pch:=nil; pch1:=nil;
if T=nil then Lst.Add('Дерево порожнє)
else begin nr:=0;
{Корінь в чергу}
Vchr(pch,kch, T, 0);
while Pustochr(pch,kch) do
begin
while Pustochr(pch,kch) do
begin Lst.Add(IntToStr(nr)+' - ранг'); c:='';
Izchr(pch, kch, Vd, zv);
c:=c+'('+IntToStr(Vd^.Nv)+','+IntToStr(Vd^.Dv)+', '+IntToStr(Zv)+'); ';
if Vd^.Vl<>nil then Vchr(pch1,kch1, Vd^.Vl, Vd^.Nv);
if Vd^.Vr<>nil then Vchr(pch1,kch1, Vd^.Vr, Vd^.Nv);
end;
Lst.Add(C);
nr:=nr+1;
Kopchr( pch,kch,pch1,kch1);
end;
end;
end;
{Функція обчислення суми вузлів бінарного дерева}
Function SumDR(var T:Tvd):Tel;
var p:Tvd;
begin
s:=nil; Result:=0; p:=T;
while (p<>nil) do
begin Result:=Result+p^.Dv;
{Перехід до наступної вершини}
if p^.Vl<>nil then {Є лівий зв'язок, правий у стек, йти вліво}
begin if p^.Vr<>nil then Vstek(S, p^.Vr); p:=p^.Vl; end
else begin if p^.Vr<>nil then p:=p^.Vr {Йти вправо}
else {Немае обох звязків, взяти із стеку}
if Pustostek(S) then Izstek(S, p)
else p:=nil; {Стек порожній кінець перегляду}
end;
end;
end;
end.
Для розв’язку задачі командою File|New Application створимо новий проект. Присвоїмо формі заголовок ДЕРЕВО (властивість Caption). Командою File|Save All запишемо програмний модуль у файл з іменем ULAB11_1.pas, а проект – PLAB11_1.dpr.
Розробимо форму для введення початкових даних і виведення результату Рис.11.7.
Рис.11.7 Форма Дерево
Розмістимо на цій формі три компоненти Edit для введення номеру вузла, даних та зв’язку і один компонент для виведення суми.
Для виведення дерева по рангах використаємо компонент Memo.
Пояснення до цих компонентів зробимо за допомогою компонента Label (властивість Caption).
Крім цього, розмістимо на формі чотири керуючі кнопки (компонент Button) з написами Включити, Вивести, Сума і Вихід. Тексти обробників для цих кнопок містяться у програмному модулі ULAB11_1.
Unit ULAB11_1;
. . . . . . . . . . . . . . .
implementation
uses ModDd;
{$R *.DFM}
{Обробник кнопки Включити}
procedure TForm1.Button1Click(Sender: TObject);
Var
nd:integer;
dd:Tel;
zv:integer;
pr:integer;
begin
nd:=StrToInt(Edit1.Text);
dd:=StrToInt(Edit2.Text);
zv:=StrToInt(Edit3.Text);
Stvder(T, nd, dd, zv, pr);
if pr=1 then Label6.Caption:='Зв''зки зайняті';
if pr=2 then Label6.Caption:='Вузол не знайдено';
if pr=0 then begin Label6.Caption:='Вузол включено';
Edit1.Text:=''; Edit2.Text:=''; Edit3.Text:='';
end;
end;
{Обробник кнопки Вихід}
procedure TForm1.Button3Click(Sender: TObject);
begin
Close;
end;
{Обробник кнопки Вивести}
procedure TForm1.Button2Click(Sender: TObject);
var Lst:TStringList;
begin
Lst:=TStringList.Create;
Drukder(T, Lst);
Memo2.Lines.Clear;
Memo2.Lines.AddStrings(Lst);
end;
{Обробник кнопки Сума}
procedure TForm1.Button4Click(Sender: TObject);
begin
Edit4.Text:=IntToStr(SumDR(T));
end;
end.
