Теорія структур даних
Залежно від призначення програми, дані можуть мати різний рівень складності (організованості). Зокрема, вони можуть об’єднуватися у деякі структури, організовані тим чи іншим способом. Прикладами таких структур є масиви, файли даних тощо. Можна сказати, що структура даних є моделлю організації даних.
Структуру даних можна розглядати як єдине ціле, як значення деякого програмного об’єкта, що дозволяє достатньо просто і зручно оперувати як із структурою уцілому, так і з окремими її елементами. При цьому окремий елемент даних, наприклад, число, можна розглядати як частковий, тривіальний випадок структури даних.
Кожна структура даних характеризується своїм логічним і фізичним представленням. Логічна структура даних - це модель відповідної структури (схема представлення її даних); фізична структура даних - це схема розміщення або зберігання структури в пам'яті комп'ютера. Фізична структура даних, зазвичай, не відповідає логічній. Наприклад, логічна структура двовимірного масиву - це прямокутна матриця, кожен елемент якої характеризується індексами відповідного рядка і стовпця; фізична структура того ж двовимірного масиву - це послідовність елементів пам'яті, кожен з яких містить один елемент масиву. Окрім того, фізичне представлення структури даних може істотно різнитися в різних програмних системах. Часто говорячи про ту або іншу структуру даних, мають на увазі саме її логічну структуру.
З урахуванням практичних задач представлення і використання даних універсальна мова повинна мати в своєму розпорядженні декілька методів структуризації даних. Вони можуть бути еквівалентні в математичному сенсі і розрізнятися лише операціями побудови їх значень і вибору компонент цих значень (доступу до них). Такими методами структуризації є методи, що дозволяють будувати наступні структури: масив, запис і множину. Відповідні структури в теорії структур даних називають фундаментальними. Вони є структурними конструкціями, які досить легко реалізуються на сучасних комп’ютерах. Змінні фундаментальної структури можуть міняти лише своє значення, зберігаючи при цьому форму - взаємне розташування і взаємозв'язок елементів структури. Такі структури займають в пам'яті комп’ютера постійний об’єм, тому їх називають ще статичними структурами.
Оскільки за визначенням статичні структури відрізняються відсутністю мінливості, пам'ять для них виділяється автоматично - як правило, на етапі компіляції або при виконанні - у момент активізації того програмного блоку, в якому вони описані. Ряд мов програмування (Pl/1, Algol-60) допускають розміщення статичних структур в пам'яті на етапі виконання на явну вимогу програміста, але і в цьому випадку об'єм виділеної пам'яті залишається незмінним до знищення структури. Виділення пам'яті на етапі компіляції є настільки зручною властивістю статичних структур, що у ряді задач програмісти використовують їх навіть для представлення об'єктів, що характеризуються мінливістю. Наприклад, коли розмір масиву невідомий заздалегідь, для нього резервується максимально можливий розмір.
Фундаментальні структури є компонентами, з яких складаються так звані ускладнені структури – структури, які можуть змінювати під час виконання програми не лише значення, але і форму. Тому такі структури ще називають динамічими. До них відносяться списки, дерева. Для реалізації таких структур потрібно застосовувати більш складні прийоми.
Послідовний файл (або просто послідовність) є в цій класифікації проміжним. Його довжина може змінюватися, але, оскільки така структура даних грає важливу роль практично у всіх обчислювальних системах, то її часто відносять до фундаментальних структур.
Таким чином, всю сукупність структур даних можна розділити на дві великі групи: статичні структури і динамічні структури. Дані статичної структури можуть бути простими (скалярними) і складеними, які формуються із простих структур за яким-небудь законом. Дані динамічної структури теж формуються за яким -небудь законом, але кількість елементів, їх взаєморозташування і взаємозв'язки можуть динамічно змінюватися під час виконання програми згідно із законом формування. Загальна класифікація структур даних наведена на рис. 1.
Типи компонент структур також можуть бути складеними, тому можна будувати цілі ієрархії структур. Однак слід пам’ятати, що кінцеві компоненти структури мають бути простими.
Часто з структурою даних пов'язується специфічний перелік операцій, які можуть бути виконані над даними, організованими в таку структуру. Наприклад, у мові Pascal для типу «множина» визначені такі специфічні операції, як об’єднання множин, їх переріз тощо.
Рис. 1. Класифікація структур даних.
Таким чином, при розробці програм необхідним кроком є визначення множини даних, які описують конкретну задачу, і організація цих даних. Вибір структури даних залежить від двох обставин. По-перше, структура повинна відображати фактичні зв'язки даних в реальному світі. З іншого боку, структура має бути досить простою, щоб дані можна було б якимось чином обробити.
Правильний підбір структур даних залежно від виконуваних операцій, розміру потрібної для їх розміщення пам'яті, частоти використання структури при виконанні програми є надзвичайно важливим для ефективного функціонування програм. Добре побудовані структури даних дозволяють оптимізувати використання машинного часу та пам'яті комп'ютера для виконання найбільш критичних операцій, зменшують час і вартість програмної розробки.
Разом з тим, рішення про структуризацію даних не можна приймати без знання алгоритмів, що застосовуються до цих даних, і навпаки, структура і вибір алгоритмів істотним чином залежать від структури даних. Побудова програм і структур даних нерозривно пов'язані між собою, що відображає формула Вірта:
АЛГОРИТМИ + СТРУКТУРИ ДАНИХ = ПРОГРАМИ
Тобто, програма є в кінцевому рахунку формулюванням алгоритму, що грунтується на конкретних структурах даних. В процесі конструювання програми представлення даних поступово уточнюється слідом за уточненням алгоритму, все більш відповідаючи обмеженням, що накладаються конкретною системою програмування.