 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Динамічні структури даних
Вказівники є ефективним засобом побудови динамічних структур даних. Статичні структури – це масиви, множини, записи і їх розміри залишаються незмінними протягом виконання програми. Розміри динамічних структур можуть змінюватися під час виконання програми. Різновидами ДС є списки, дерева і графи.
Кожен компонент динамічної структури представляє собою запис, яка вміщує 2 поля: вказівник і поле для розміщення даних. За допомогою вказівників компоненти зв’язується в єдину структуру, тобто вказівник повинен вказувати на запис того ж типу, що і запис яка вміщує вказівник.
Наприклад:
Type
CompPtr = ^Component;
Component = Record;
Data: DataType;{ поле даних типа DataType}
Next: CompPrt; { Вказівник на слідуючий компонент}
End;
| Data |
| Next |
Компонент найпростішої структури даних.
Однозв’язні списки - це послідовно зв’язані записи типа Component за допомогою вказівників Next.
Останній компонент списку = NIL(кінець списку).
| Data |
| Next |
| Data | Data | Data |
| Next | Next | Nil |
Однозв’язний список.
Наприклад:
Вставимо елемент С між елементами списку A і B.
A.Next:= @C;
C.Next:= @B;
Видалимо елемент С між елементами списку A і B.
A.Next:= @B;
Dispose (@C);
Використовуючи для зберігання послідовності елементів не масив, а список, можна прискорити операції вставки або видалення елементів, але одержати доступ до елементу по його номеру простіше в масиві, ніж у списку.
В програмуванні використовують 2 різновиди послідовностей: стек і черга.
Стеком називається послідовність, вставка нових елементів в яку або видалення існуючих з якої проводиться з одного і того ж кінця, який називається вершиною стека (нагадує дитячу пірамідку).
Основними видами операцій зі стеками є вставка елементів в його вершину та видалення таких із неї.
Для реалізації стека застосуємо запис Stack, яка має таку ж структуру, як Component.
Опишемо стек за допомогою запису Stack:
Type
StackPrt = ^Stack;
Stack =Record;
Data: Integer;{ поле даних типа Integer}
Next: StackPrt; { Вказівник на слідуючий компонент}
End;
Додамо елемент до стеку:
Procedure Push(var top:StackPrt; value:Integer);
Var x: StackPrt;
Begin
New(x);{ створити новий елемент }
x^.Data:=value;{ Ініціалізувати дані нового елементу }
x^.Next:= top;{ Додати елемент до стеку }
top:=x;{ Зробити вершиною стека новий елемент }
end;
Видалимо елемент із стеку:
Procedure Pop(var top:StackPrt; var variable:Integer);
Var x: StackPrt;
Begin
If top<> nil then { якщо стек не пустий }
Begin
Variable:=top^.Data;{ видалити дані із вершини стека }
x:= top;{ створити копію адреси вершини }
top:=top^.Next;{ вказівник на вершину перемістити на другий елемент }
Dispose(x);{ звільнити память, яку займала попередня вершина }
End;
End;
Черга – це така послідовність, при якій вставка нових елементів проводиться з одного кінця, який називається головою черги, а видалення існуючих – з іншого кінця, який називається хвостом черги.
Найчастіше черга організується у вигляді двозв’язного списку.
Type
QueuePtr = ^Queue;
Queue=Record;
Data: Integer;{ поле даних типа Integer}
Prev,Next: QueuePrt; { Вказівник на попередній і слідуючий компонент}
End;
Голова Хвіст
Поиск по сайту: