ЗВ'язані динамічні дані основні визначення



Скачати 45.47 Kb.
Дата конвертації11.05.2017
Розмір45.47 Kb.
ЛЕКЦІЯ 16

ЗВ'ЯЗАНІ ДИНАМІЧНІ ДАНІ




Основні визначення



Лінійні списки це дані динамічної структури, які є сукупністю лінійно зв'язаних однорідних елементів, і для яких дозволяється додавати елементи між будь-якими двома іншими, і видаляти будь-який елемент.
Кільцеві списки — це такі ж дані, як і лінійні списки, але що мають додатковий зв'язок між останнім і першим елементами списку.
Черга — окремий випадок лінійного однозв’язного списку, для якого дозволено дві дії: додавання елементу в кінець (хвіст) черги і видалення елементу з початку (голови) черги.
Стек — окремий випадок лінійного однозв’язного списку, для якого дозволено додавати або видаляти елементи тільки з одного кінця списку, який називається вершиною (головою) стека.
Дерева — це динамічні дані ієрархічної структури довільної конфігурації. Елементи дерева називаються вершинами (вузлами).
Пірамідою (впорядкованим деревом) називається дерево, в якому значення вершин (вузлів) завжди зростають або убувають при переході на наступний рівень.

Організація взаємозв'язків в зв'язаних динамічних даних

Зв'язані динамічні дані характеризуються високою гнучкістю створення структур даних різної конфігурації. Це досягається завдяки можливості виділяти і звільняти пам'ять під елементи у будь-який момент часу роботи програми і можливості встановити зв'язок між будь-якими двома елементами за допомогою покажчиків.

Для організації зв'язків між елементами динамічної структури даних потрібно, щоб кожен елемент містив не тільки інформаційні значення, але і як мінімум один покажчик. Звідси витікає, що як елементи таких структур необхідно використовувати записи, які можуть об'єднувати в єдине ціле різнорідні елементи.

У простому випадку елемент динамічної структури даних повинен складатися з двох нулів: інформаційного і вказівного.


Таку структуру даних можна задати таким чином
Type

TElement = ^Element;

Element = record

Inf : integer;

Link : TElement

End;
Правило послідовності описів в Borland Pascal вимагає, щоб кожен ідентифікатор був описаний, перш ніж він використовуватиметься для інших оголошень. Проте в приведеному прикладі, як би не розташовувалися описи типів покажчика Тelement і елементу Element, це правило виконано не буде. Тому, для опису типів елементів динамічних структур даних зроблено виключення.

"Тип покажчика на елемент динамічної структури даних може і повинен бути описаний перед описом типу цього елементу

Робота з чергою.

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

| на початок черги (візьмемо ідентифікатор NO );

| на кінець черги (візьмемо ідентифікатор KO ).

Крім того, для звільнення пам'яті елементів, що видаляються, потрібний додатковий тимчасовий покажчик (візьмемо ідентифікатор Р). Додатковий покажчик також часто використовується в інших ситуаціях для зручності роботи з чергою.
Створення черги
1. Початковий стан:

NO := nil;

KO := nil;
2. Виділення пам'яті під перший елемент черги:

New(P);
3. Занесення інформації в перший елемент черги:

P^. inf := 1;

P^. Link := nil;


4. Установка покажчиків NO і KO на створений перший елемент:

NO := P;


KO := P;
Додавання елементу черзі
1. Виділення пам'яті під новий елемент і занесення в нього інформації:

New(P);


P^. inf := 2;

P^. Link := nil;




  1. Установка зв'язку між останнім елементом черги і новим, а також переміщення покажчика кінця черги КО на новий елемент:

KO^.Link := p;

KO := P;
Видалення елементу черги
1. Витягання інформації з елементу, що видаляється, в змінну VAL і установка на нього допоміжного покажчика Р:
VAL := NO^.inf;

P:= NO;
2. Перестановка покажчика початку черги NO на наступний елемент, використовуючи значення поля Link, яке зберігається в першому елементі. Після цього звільняється пам'ять початкового елементу черги, використовуючи додатковий покажчик Р:


NO := P^.Link;

Dispose(P);




Робота із стеком
Для роботи із стеком, на відміну від черги, необхідно мати один основний покажчик на вершину стека (візьмемо ідентифікатор W) і один додатковий тимчасовий покажчик (візьмемо ідентифікатор Р), який використовується для виділення і звільнення пам'яті елементів стека.
Створення стека
1. Початковий стан:

W := nil;


2. Виділення пам'яті під перший елемент стека і внесення до нього інформації:

New(P);


P^. inf := 1;

P^. Link := nil;


3. Установка вершини стека Тор на створений елемент:

W := P;
Додавання елементу стека


1. Виділення пам'яті під новий елемент стека:

New(P);


2. Внесення значення в інформаційне поле нового елементу і установка зв'язку між ним і "старою" вершиною стека W:

P^.inf := Val; {Val =2}

P^.Link := W;
3. Переміщення вершини стека Тор на новий елемент:

W :=P;
Видалення елементу стека


1. Витягання інформації з інформаційного поля вершини стека W в змінну Val і установка на вершину стека допоміжного покажчика Р:

Val := W.inf;

P := W;
2. Переміщення покажчика вершини стека W на наступний елемент і звільнення пам'яті, займаною "старою" вершиною стека:

W := P^.Link;



Dispose(P);


База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка