Основні теоретичні відомості. Поняття динамічної структури даних

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

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

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

Можна виділити наступні характеристики динамічної структури даних (далі структури):

– для структури виділяється пам’ять в процесі виконання програми;

– кількість елементів структури не фіксується;

– розмір памяті, що займають елементи структури, може змінюватися в процесі виконання програми;

– в процесі виконання програми може змінюватися зв’язок між елементами.

Для роботи з динамічною структурою потрібно створити змінну яка має тип динамічної структури.

Лінійний односпрямований (однозв’язний) список. Список – це набір елементів, що ідуть один за одним та мають деякий загальний зміст для задачі, що вирішується. Динамічний список – список, елементи якого пов’язані покажчиками з сусідними елементами.

У лінійному списку у кожного даного, що його складає (елемента списку), є один передуючий і один наступний елемент (це справедливо для всіх елементів, окрім першого і останнього).

Лінійний однозв’язний список – це динамічний список, кожний елемент якого складається з двох полів. Одне поле містить інформацію (або посилання на неї), інше поле містить посилання на наступний елемент списку. Елемент списку називають «ланкою» списку. Таким чином, список – це ланцюг пов’язаних між собою ланок від першого до останнього.

Приклад 1 (рядок символів ВЕТА представимо у вигляді списку):

 

 

Рисунок 1.1 – Рядок символів ВЕТА у вигляді списку

 

Остання ланка (рис. 1.1) не вказує на наступний елемент, тому поле посилання має значення NULL – порожній покажчик.

 

 

Рисунок 1.2 – Рядок символів ВЕТА у вигляді циклічного списку

 

Остання ланка вказує на перший елемент списку (рис. 1.2) – це циклічний список.

В односпрямованому списку можна рухатися тільки в одному напрямку – від першої ланки до останньої.

Щоб задати динамічний список треба описати його ланку. Так як ланка складається з полів різних типів, то описати її можна неоднорідним типом – структурою (або класом).

Щоб працювати зі списком як з єдиним об’єктом, треба використовувати змінну-покажчик, значення якої – це адреса першої ланки списку. Якщо список порожній, то вона повинна мати значення NULL.

Використовуючи покажчик, можна звертатися до елементів списку (для списку на рис. 1.1):

List... //покажчик на початкову ланку списку

List->next... //покажчик на першу ланку списку

List->next->next... //покажчик на другу ланку списку

List->elem... //звертання до інформаційного поля першого елемента списку

Для більш зручної роботи зі списком краще ввести покажчик, який вказує на поточний елемент списку.

Над списками можна виконувати наступні операції:

– пошук заданого елемента за його значенням або порядковим номером; операція завершується, коли елемент знайдено або переглянуто весь список (якщо елемента немає); результат операції повинен визначати, є елемент у списку або ні і, якщо є, то можливо його адресу або значення;

– занесення (вставка) до списку нового елемента перед чи після заданого елемента (в т.ч. перед першим елементом або після останнього); занесенню, як правило, передує пошук елемента, після і/або перед яким відбувається вставка; при занесенні елемента перед першим у список без початкової ланки змінюється заголовок списку; при занесенні після деякого елемента змінюється поле посилання у елемента, після якого відбувається вставка, тому надо визначати посилання на елемент, після якого здійснюється занесення;

– виключення (видалення) заданого елемента зі списку (в т.ч. видалення першого елемента або останнього); виключенню, як правило, передує пошук елемента, що виключається; результатом пошуку має бути посилання на елемент попередній для того, що виключається, так як при видаленні елемента зі списку змінюється поле посилання у попереднього елемента до того, що видаляється; при видаленні першого елемента зі списку без початкової ланки змінюється заголовок списку;

– визначення числа ланок списку;

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

Приклад 2. Список складається із вузлів (елементів), що пов’язанні між собою покажчиками. Тому опишемо допоміжний клас для подання одного вузла списку:

 

class Node

{

public:

char d; // дані

Node *next; // покажчик на наступний вузол

Node (char dat = 0) // конструктор

{ d = dat; next = 0; }

};

 

class List

{Node *pbeg, *pend; // покажчики на початок та кінець списку

public:

List() { pbeg = 0; pend = 0;} // конструктор

~List(); // деструктор

void add(char d); // додавання вузла в кінець списку

void print();// друк списку

};

 

Розглянемо реалізацію методів класу. Метод add виділяє пам'ять під новий об’єкт типу Node та приєднує його к списку, оновлюючи покажчик на його кінці:

 

void List::add(char d)

{ Node *pv = new Node(d); // виділення пам'яті під новий вузол

if(!pbeg) { pbeg = pend = pv; } // перший вузол

else //зв’язування нового вузла:

{ pend->next = pv;

pend = pv; } // оновлення покажчика на кінець списку

}

Метод друку списку поелементно переглядає список, переходячи по відповідним посиланням:

 

void List::print()

{ Node *pv = pbeg;

cout << endl << " list: ";

while(pv)

{ cout << pv->d << " ";

pv = pv->next;

}

cout << endl;

}

Деструктор списку звільняє пам'ять з-під усіх елементів списку:

 

List::~List()

{

if(pbeg)

{ Node *pv = pbeg;

while(pv)

{ pv = pv->next;

delete pbeg;

pbeg = pv;

}

}

}

Нижче наведений приклад програми, що використовує клас List. Програма формує список рядку 'BETA' та друкує його на екран.

 

void main()

{ List l;

l.add('B');

l.add('E');

l.add('T');

l.add('A');

l.print();

getch();

}