РОЗДІЛ 14. ДИНАМІЧНІ СТРУКТУРИ ДАНИХ

Будь-яка програма призначена для обробки даних, від способу організації яких залежать алгоритми роботи, тому вибір структур даних повинен робитись перед створенням алгоритмів. Найчастіше в програмах використовуються масиви, структури і їх поєднання, наприклад, масиви структур, полями яких є масиви та структури.

Пам'ять під дані виділяється або на етапі компіляції (в цьому випадку необхідний об'єм має бути відомий до початку виконання програми, тобто заданий у вигляді константи), або під час виконання програми за допомогою операції new. У обох випадках виділяється безперервна ділянка пам'яті.

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

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

Елемент будь-якої динамічної структури даних є структурою (struct), що містить принаймні два поля: для зберігання даних і для вказівки. Полів даних та вказівок може бути декілька. Опис простого елементу виглядає таким чином:

struct Node

{

Data d; // тип даних Data має бути визначений раніше

Node *р;

};

Розглянемо реалізацію основних операцій з динамічними структурами даних (стек, черга, лінійний список) [10, с.114].

Стек

Стек реалізує принцип обслуговування LIFO (last in – first out, останнім прийшов, – першим пішов). Стек можна представити як стопку книг, які складаються одна на одну. Так першою буде взята остання книга в стопці.

Нижче приведена програма, яка формує стек з п'яти цілих чисел (1, 2, 3, 4, 5) і виводить його на екран. Функція поміщення елементу в стек називається push, а вибірки – pop. Вказівка для роботи із стеком (top) завжди посилається на його вершину.

#include <iostream>

using namespace std;