Контрольні питання

1. Що таке об’єднання?

2. В чому відмінність об’єднань від структур?

3. Розкрийте сутність переліченого типу даних (enum).

4. Наведіть приклад роботи з переліченим типом даних enum.

5. Яким чином можна використовувати бітові поля?

6. Наведіть приклад використання бітових полів.

7. Розкрийте сутність та призначення виключних ситуацій.

8. Яким чином можна згенерувати власну помилку?

Розділ 14. Динамічні структури даних

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

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

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

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

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

struct Node

{

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

Node *р;

};

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

14.1. Стек

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

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

#include <iostream>

using namespace std;

struct Node

{

int d;

Node *p;

};

Node * first(int d);

void push(Node **top, int d);

int pop(Node **top);

void main()

{

Node* top = first(1);

for (int i = 2; i<6; i++) push(&top, i);

while (top)

cout << pop(&top) << " ";

}

// Початкове формування стеку

Node * first(int d)

{

Node *pv = new Node;

pv->d = d;

pv->p = 0;

return pv;

}

// Занесення в стек

void push(Node **top, int d)

{

Node *pv = new Node;

pv->d = d;

pv->p = *top;

*top = pv;

}

// Вибірка із стеку

int pop (Node **top)

{

int temp = (*top)->d;

Node *pv = *top;

*top = (*top)->p;

delete pv;

return temp;

}

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

5 4 3 2 1