Лекция: Приклад. Моделювання масиву зі змінною верхньою межею.

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. Елемент зв’язаної структури динамічних даних

Дані можуть бути як простими, так і структурованими. Наприклад,

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).

Рис 11.2. Однозв’язний список.

Зв’язок з наступним елементом.

Рис 11.3. Однозв’язний список.

Зв’язок з попереднім елементом.

Рис 11.4 Однозв’язний циклічний список.

Рис 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;

{Процедура створення бінарного дерева}

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;

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;

{Функція обчислення суми вузлів бінарного дерева}

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.

Для розв’язку задачі командою 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;