Зв’язані динамічні дані

Це структури даних із зв’язаних однорідних елементів. Елемент зв’язаної структури динамічних даних складається з двох частин даних і вказівників (Рис 1).

Дані   Вказівники  

Рис 1. Елемент зв’язаної структури динамічних даних

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

Type Tel1 = integer;

Tvk1 = ^dan1;

dan1 = record

x1: Tel1;

v1:Tvk1;

end;

Tel2 = record

pib= record p,i,b:string[15];end;

rn: word;

pos: string[10];

end;

Tvk2 = ^dan1;

dan2 = record

x2: Tel2;

v2:Tvk2;

end;

Var p1: Tvk1;

P2: Tvk2;

begin

............

p1^.x1:=5;

p2^.x2.pib.p:=’Шевченко’;

...........

end.

У наведеному прикладі для елементів зв’язаних динамічних даних dan1 даними будуть цілі числа, а для dan2 – записи. Звернення до елементів динамічних даних здійснюється за допомогою складених імен.

До зв’язаних динамічних структур даних належать: списки, черги, стеки, дерева.

Список – це динамічна структура лінійно зв’язаних елементів даних. При роботі зі списками використовуються вказівники на початок (L) і кінець (K) списку. Списки бувають: однозв’язні, зі зв’язком з наступним (Рис 11.4) або попереднім (Рис 11.5) елементом; однозв’язні циклічні, зі зв’язком останнього елемента з першим (Рис 11.6); двозв’язні, зі зв’язками з наступним і попереднім елементами одночасно (Рис 11.7).

    NIL

...

L

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

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

  NIL    

L

...

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

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

L

...

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

    NIL  

...

  NIL    

L K

Рис 11.7 Двозв’язний список.

Над списками можуть виконуватися такі операції:

· створення;

· включення нового елемента перед або після -го елемента;

· включення нового елемента перед або після елемента з заданим значенням;

· вилучення елемента перед або після -го елемента;

· вилучення елемента перед або після елемента з заданим значенням;

· вилучення елемента з заданим значенням;

· упорядкування елементів списку;

· виведення елементів списку;

· та інші.

Приклад 1. Наступна програма демонструє добавляння елемента на початок списку.

type

elem=^zapis;

zapis=record

name:string;

next:elem;

end;

var

a1,a:elem;

procedure TForm1.Button1Click(Sender: TObject);

begin

new(a1);

a1^.name:=Edit1.Text;

a1^.next:=nil;

Memo1.Lines.Add(a1^.name);

end;

procedure TForm1.Button2Click(Sender: TObject);

begin

Memo1.Lines.Add('Формування стеку:');

new(a);

a^.name:=Edit1.Text;

a^.next:=a1;

Memo1.Lines.Add(a^.name);

a:=a^.next;

Memo1.Lines.Add(a^.name);

end;

Результат роботи програми:

Иванов

Формування стеку:

Петров

Иванов

Дата добавления: 2015-10-26