Класифікація структур даних.

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

Досить важлива ознака структури даних – її змінність – зміна кількості елементів і/або зв’язків між елементами структури.За ознакою змінності розрізняють структури статичні, напівстатичні, динамічні.

Ще одна важлива ознака структури даних – характер впорядкованості її елементів. За цією ознакою структури можна поділити на лінійні й нелінійні структури.

Базові операції над структурами даних.

Над будь-якими структурами даних можуть виконуватися чотири загальні операції: створення, знищення, вибір (доступ), поновлення.

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

Дані арифметичного типу.

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

Результати логічного типу отримуються при порівнянні даних будь-яких типів. Величини логічного типу можуть приймати тільки значення true і false. Внутрішня форма представлення значення false – 0 (нуль). Будь-яке інше значення інтерпретується як true.

Значенням символьного типу є символи з деякої наперед визначеної множини.

Ще одна група операцій над арифметичними типами – операції порівняння: „рівно”, „не рівно”, „більше”, „менше” і т.п.

Дані перерахованого типу.

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

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

Властивості статичних структур даних.

Статичні структури відносяться до класу структур, які представляють собою структуровану множину примітивних, базових структур. Оскільки статичні структури відрізняються відсутністю змінності, пам’ять для них виділяється автоматично – як правило, на етапі компіляції, або при виконанні – в момент активізації того програмного блоку, в якому вони описані.

Масив як структура даних

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

Розріджені масиви.

Розріджений масив – це масив, більшість елементів якого ОДНАКОВІ, так що зберігати в пам’яті достатньо лише невелику кількість значень, які вирізняються від «фонового» значення інших елементів.

Розрізняють два типи розріджених масивів:масиви, в яких розташування елементів із значеннями, відмінними від фонового, можуть бути описані математично;масиви з випадковим розташуванням елементів.

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

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

Множина як структура даних.

Множина – така структура, яка є набором даних одного і того ж типу, що не повторюються (кожен елемент множини є унікальним). Порядок слідування елементів множини на має принципового значення.

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

1. Об’єднання множин.

2. Перетин множин.

3. Різниця множин. Результатом є множина, яка містить елементи першої множини, які не входять в другу множину.

4. Симетрична різниця. Результатом є множина, яка містить елементи, які входять до складу однієї або другої множини (але не обох).

5. Перевірка на входження елемента в множину.

 

Структурний тип даних.

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

Самою найважливішою операцією для структури є операція доступу до вибраного поля структури – операція кваліфікації.

 

Об’єднання як структура даних.

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

Бітовий тип даних.

Бітові поля – це особливий вид полів структури. Вони використовуються для компактного розміщення даних, наприклад, прапорців типу „так/ні”. Мінімально адресована комірка пам’яті – 1 байт, а для зберігання прапорця достатньо одного біта. Бітові поля описуються за допомогою структурного типу.

Над бітовими типами можливі три групи специфічних операцій: операції алгебри логіки, операції зсуву, операції порівняння.

 

Таблиця як структура даних.

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

Особливості напівстатичних структур даних.

Напівстатичні структури даних характеризуються такими ознаками:

· вони мають змінну довжину і нескладні процедури її зміни;

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

Стек як структура даних.

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

Основні операції над стеком – включення нового елемента (push – заштовхувати) і виключення елемента зі стеку (pop – вискакувати).

Черга як структура даних.

Черга (queue) - динамічна структура даних, що працює за принципом «перший прийшов — перший пішов» (FIFO — first in, first out). У черги є голова (head) та хвіст (tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові. Така черга повністю аналогічна звичній «базарній» черзі, в якій хто перший встав в неї, той першим буде обслуженим.

• enqueue — "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення (queue overflow).

• dequeue — "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповнення" (queue underflow).

Дек як структура даних.

Дек – особливий вид черги. Дек (deq – double ended queue, тобто черга з двома кінцями) – це такий послідовний список, в якому як включення, так і виключення елементів, може здійснюватися з будь-якого з двох кінців списку. Так само можна сформулювати поняття деку, як стек, в якому включення і виключення елементів може здійснюватися з обох кінців. Дек як двобічна черга— абстрактна структура даних, елементи якої можуть додаватись як на початок, так і в кінець.

Лінійні списки.

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