ЛЕКЦІЯ 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;
-
Установка зв'язку між останнім елементом черги і новим, а також переміщення покажчика кінця черги КО на новий елемент:
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); |