Структура даних – програмна одиниця, що дозволяє зберігати і обробляти масу однотипних або ж логічно зв’язаних даних в обчислювальних пристроях. Якщо потрібно додати, знайти, змінити або видалити відомості, структура надасть певний пакет опцій, що становить її інтерфейс.
Що включає в себе поняття структури даних?
Цей термін може мати кілька близьких, але все ж відмінних значень. Це:
- абстрактний тип;
- реалізація абстрактного виду інформації;
- примірник типу даних, наприклад, певний список.
Якщо говорити про структуру даних в контексті функціонального програмування, то це особлива одиниця, що зберігається при змінах. Про неї неформально можна сказати як про єдиної структурі, незважаючи на те, що можуть бути різні версії.
Що формує структуру?
Структура даних формується з допомогою типів інформації, посилань та операцій над ними в певній мові програмування. Варто сказати, що різні види структур, підходять для здійснення різних програм, деякі, наприклад, мають зовсім вузькою спеціалізацією і підходять тільки для виробництва встановлених завдань.
Якщо взяти B-дерева, то вони зазвичай підходять для формування баз даних і тільки для них. У цей ж годину хеш-таблички застосовуються ще повсюдно на практиці для створення різних словників, наприклад, для демонстрації доменних назв в інтернет-адресах ПК, а не тільки для формування баз.
Під час розробки того чи іншого програмного забезпечення складність реалізації і якість функціональності програм безпосередньо залежать від правильного застосування структур даних. Таке розуміння речей дало поштовх до розробки формальних методик розробки та мов програмування, де структури, а не алгоритми ставляться на лідируючі позиції в архітектурі програми.
Варто відзначити, що багато мов програмування мають встановленим типом модульності, що дозволяє структурам з даними безпечно використовувати в різних додатках. Яскравими прикладами є мови Java, C#, C++. Зараз класична структура використовуваних даних представлена в стандартних бібліотеках мов програмування або безпосередньо вона вбудована вже сама мова. Наприклад, це структура хеш-таблиці вбудована в Lua, Python, Perl, Ruby, Tcl і інші. Широко застосовується стандартна бібліотека шаблонів в C++.
Порівнюємо структуру у функціональному та імперативний програмуванні
Варто відразу обмовиться, що проектувати структури для функціональних мов складніше, ніж для імперативних, як мінімум, на це є дві причини:
Що включає в себе структура?
Часто дані, з якими працюють програми, що зберігаються у вбудованих в застосовуваному мовою програмування масивах, константі або змінної довжини. Масив – це найпростіша структура з відомостями, однак для вирішення деяких завдань потрібна більша ефективність деяких операцій, тому застосовуються інші структури (складніше).
Найпростіший масив підходить для частого звернення до встановлених компонентів за індексами і їх зміни, а видалення елементів із середини функціонує за принципом O(N)O(N). Якщо вам потрібно видалити елементи, щоб вирішити певні завдання, то доведеться скористатися іншою структурою. Наприклад, бінарне дерево (std::set) дозволяє робити це за O(logN)O(logN), однак воно не підтримує роботу з індексами, виконується виключно почерговий обхід елементів і їх пошук за значенням. Таким чином, можна сказати, що структура відрізняється операціями, що вона здатна виконувати, а також швидкістю їх виконання. Для прикладу варто розглянути найпростіші структури, що не дають вигоди в ефективності, але мають точно встановлений набір підтримуваних операцій.
Стек
Це один з типів структур даних, представлений у вигляді обмеженого найпростішого масиву. Класичний стек підтримує всього лише три опції:
- Внести елемент в стек (Складність: O(1)O(1)).
- Вилучення елемента зі стека (Складність: O(1)O(1)).
- Перевірка, порожній чи стек чи ні (Складність: O(1)O(1)).
Щоб пояснити принцип роботи стека, можна застосувати на практиці аналогію з банкою печива. Уявіть, що на дні посудини лежить кілька печенюшек. Наверх ви можете покласти ще пару шматочків або ж ви можете, навпаки, взяти одну печеньку зверху. Інші печеньки будуть закриті верхніми, і ви про них нічого не будете знати. Ось так справи йдуть і зі стеком. Для опису поняття застосовується абревіатура LIFO (Last In, First Out), яка підкреслює, що компонент, який потрапив всередину стека останнім, буде першим і вилучено з нього.
Чергу
Це ще один тип структури даних, що підтримує той же набір опцій, що і стек, однак у нього протилежна семантика. Для опису черзі застосовується абревіатура FIFO (First In, First Out), бо спочатку витягується елемент, що був доданий раніше за всіх. Назва структури говорить за себе – принцип роботи повністю збігається з чергами, що можна побачити в магазині, супермаркеті.
Січ
Це ще один вид структури даних, який ще називають чергою з двома кінцями. Опція підтримує наступний набір операцій:
- Внести елемент на початок (Складність: O(1)O(1)).
- Витягти компонент з початку (Складність: O(1)O(1)).
- Внесення елемента в кінець (Складність: O(1)O(1)).
- Вилучення елемента з кінця (Складність: O(1)O(1)).
- Перевірка, порожній чи дек (Складність: O(1)O(1)).
Списки
Дана структура даних визначає послідовність лінійно зв’язаних компонентів, для яких можна операції додавання компонентів в будь-яке місце списку і його видалення. Лінійний список задається покажчиком на початок списку. Типові операції над списками: обхід, пошук конкретного компонента, вставка елемента, видалення компонента, об’єднання двох списків у єдине ціле, розбивка списку на пару і так далі. Варто обмовитися, що в лінійному списку, крім першого, є попередній компонент для кожного елемента, не включаючи останній. Це означає, що компоненти списку знаходяться в упорядкованому стані. Так, обробка такого списку не завжди зручна, адже немає можливості просування в протилежну сторону — від кінця списку до початку. Однак у лінійному списку можна поетапно пройтися по всім складовим.
Ще існують кільцеві списки. Це така ж структура, що і лінійний список, проте вона має додаткову зв’язок між першим і останнім компонентами. Іншими словами, наступним за останнім елементом є перший компонент.
У цьому списку елементи рівноправні. Виділення першого і останнього – це умовність.
Дерева
Це сукупність компонентів, що називаються вузлами, в якому є головний (один) компонент у вигляді кореня, а всі інші розбиті на безліч роз’єднаних елементів. Кожна множина є деревом, а корінь кожного дерева – нащадком кореня дерева. Іншими словами, всі компоненти з’єднані між собою відносинами предок–нащадок. Як результат можна спостерігати ієрархічну структуру вузлів. Якщо вузли не мають нащадка, то вони називаються листям. Над деревом визначені такі операції: додавання компонента і його видалення, обхід, пошук компонента. Особливу роль в інформатиці грають бінарні дерева. Що це таке? Це приватний випадок дерева, де кожен вузол може мати не більше пари нащадків, що є корінням лівого і правого піддерева. Якщо додатково для вузлів дерева виконується ще умову, що всі значення компонентів лівого піддерева менше значень кореня, а значення компонентів правого піддерева більше кореня, то таке дерево називається деревом бінарного пошуку, і воно призначається для швидкого знаходження елементів. Як же працює алгоритм пошуку в такому випадку? Шукане значення порівнюється зі значенням кореня, і в залежності від результату пошук або завершується, або триває, але виключно в лівому або правому поддереве. Загальна кількість операцій порівняння не стане перевершувати висоту дерева (це найбільше число компонентів на шляху від кореня до одного з листя).
Графи
Графи – це сукупність компонентів, що називаються вершинами разом з комплексом відносин між даними вершинами, які називаються ребрами. Графічна інтерпретація даної структури представлена у вигляді безлічі точок, що відповідають за вершини, а деякі пари з’єднані лініями або стрілками, що відповідає ребрах. Останній випадок говорить про те, що граф потрібно називати орієнтованим.
Графами можна описувати об’єкти який завгодно структури, вони є головним засобом для опису складних структур і функціонування всіх систем.
Детальніше про абстрактну структуру
Для побудови алгоритму потрібно провести формалізацію даних або, іншими словами, необхідно привести дані до певної інформаційної моделі, що вже досліджена і написана. Як тільки модель буде знайдена, то можна стверджувати, що встановлена абстрактна структура.
Це основна структура даних, що демонструє ознаки, якості об’єкта, взаємозв’язок між компонентами об’єкта та операції, що можливо здійснити над ним. Основне завдання – пошук і відображення форм подання відомостей, комфортних для комп’ютерної коригування. Варто обмовитися відразу, що інформатика як точна наука діє з формальними об’єктами.
Аналіз структур даних здійснюється наступними об’єктами:
- Цілі і речові числа.
- Логічні значення.
- Символи.
Для обробки на комп’ютері всіх елементів існують відповідні алгоритми і структури даних. Типові об’єкти можна об’єднати в складні структури. Можна додати операції над ними, правила до певних компонентів цієї структури.
Структура організації даних включає в себе:
- Вектори.
- Динамічні структури.
- Таблиці.
- Багатовимірні масиви.
- Графи.
Якщо всі елементи вибрані вдало, то це буде запорукою формування ефективних алгоритмів та структур даних. Якщо застосовувати на практиці аналогію структур і реальних об’єктів, то можна ефективно вирішувати завдання.
Варто зауважити, що всі структури організації даних існують і окремо в програмуванні. Над ними багато працювали ще в восемнадцатых і девятнадцатых століттях, коли ще і в помині не було обчислювальної машини.
Можливо розробляти алгоритм в поняттях абстрактної структури, однак для реалізації алгоритму на певній мові програмування потрібно відшукати методику для її подання в типи даних, оператори, що підтримуються конкретною мовою програмування. Для створення структур, таких як вектор, табличка, рядок, послідовність, у багатьох мовах програмування є класичні типи даних: одновимірний або двовимірний масив, рядок, файл.
Які є методичні рекомендації по роботі зі структурами?
Ми розібралися з характеристиками структур даних, тепер варто приділити більше уваги розуміння поняття структури. При вирішенні абсолютно будь-якого завдання необхідно працювати з якимись даними, щоб здійснити операції над інформацією. У кожного завдання є свій набір операцій, проте деякий набір застосовується на практиці найчастіше для вирішення різноманітних завдань. У такому випадку корисно придумати певний спосіб організації інформації, що дозволить виконувати ці операції як можна ефективніше. Як тільки такий спосіб з’явився, можна вважати, що у вас з’явився «чорний ящик», в якому будуть зберігатися дані певного роду і який стане виконувати ті чи інші операції з даними. Це дозволить відволіктися від деталей і повністю сконцентруватися на характерних особливостях завдання. Даний «чорний ящик» може бути реалізований будь-яким чином, при цьому необхідно прагнути до якомога більш продуктивної реалізації.
Кому це потрібно знати?
Ознайомитись з інформацією варто починаючим програмістам, які бажають відшукати своє місце в цій сфері, але не знають, куди податися. Це основи в кожній мові програмування, тому буде не зайвим дізнатися відразу ж про структури даних, а після працювати з ними на конкретних прикладах і з певною мовою. Не слід забувати, що кожну структуру можливо охарактеризувати логічними і фізичними уявленнями, а також сукупністю операцій над цими уявленнями.
Не забувайте: якщо ви говорите про ту чи іншій структурі, то майте на увазі її логічне представлення, адже фізичне представлення повністю приховано від «зовнішнього спостерігача».
Крім того, майте на увазі, що логічне уявлення абсолютно не залежить від мови програмування і від обчислювальної машини, а фізична, навпаки, залежить від трансляторів і обчислювальної техніки. Приміром, двовимірний масив в “Фортране” і “Паскаль” можна представити ідентичним чином, а фізичне представлення в одній і тій же обчислювальній машині на цих мовах буде відрізнятися.
Не поспішайте починати вчити конкретні структури, краще всього зрозуміти їх класифікацію, ознайомитися з усіма в теорії і бажано на практиці. Варто пам’ятати, що мінливість – це важливий ознака структури, і він вказує на статичну, динамічну або ж полустатическое положення. Вивчайте основи, перш ніж приступити до більш глобальних речей, це допоможе вам у подальшому розвитку.
