Структура даних

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

Бінарне дерево, одна з найпростіших деревоподібних структур даних

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

Відома формула «Програма = Алгоритми + Структури даних» дуже точно виражає необхідність відповідального ставлення до такого підбору. Тому іноді навіть не обраний алгоритм для обробки масиву даних визначає вибір тієї чи іншої структури даних для їх збереження, а навпаки.

Підтримка базових структур даних, які використовуються в програмуванні, включена в комплекти стандартних бібліотек найбільш розповсюджених мов програмування, таких як Standard Template Library (STL) для C++, Java API, Microsoft.NET тощо.

Приклади

Існує велика кількість різноманітних структур даних, що зазвичай будуються з примітивних типів даних[1]:

масив (список) — деяка кількість елементів, упорядкованих певним чином, зазвичай ці елементи належать до одного й того ж типу. Доступ до елементів відбувається завдяки цілочисельному індексу необхідного елементу (хоча самі елементи можуть бути майже будь-якого типу). Масиви можуть бути фіксованої довжини або ж такими, розмір яких можна змінити.
зв'язаний список — це лінійна колекція елементів даних будь-якого типу, які називаються вузлами, де кожен вузол містить дані, і вказівник на наступний вузол у зв'язаному списку. Принциповою перевагою зв'язного списку над масивом є те, що елементи завжди можна ефективно додавати й видаляти без перерозподілу всього списку. Звісно, інші операції, такі як довільний доступ до конкретного елементу, є повільнішими в таких списках, ніж у масивах.
асоціативний масив (словник, map) — більш гнучка варіація масиву, можна вільно додавати та видаляти пари «ім'я-значення». Геш-таблиця є найбільш звичною реалізацією асоціативного масиву.
запис (структура) — агрегована структура даних. Запис — це значення, що містить інші значення. Зазвичай це фіксоване число та послідовність, які індексуються поіменно. Елементи запису зазвичай називають полями або членами
об'єднання — структура даних, що зазначає, які із дозволених примітивних типів можуть зберігатись у її екземплярах. На відміну від запису, який можна визначити таким чином, щоб він зберігав і ціле число, і число з рухомою комою, у об'єднанні можна зберігати лише один певний тип. Для зберігання об'єднання виділяється стільки пам'яті скільки необхідно для найбільшого типу даних.

Література

Алгоритми і структури даних: навч. посіб. / Т. О. Коротєєва ; М-во освіти і науки України, Нац. ун-т «Львів. політехніка». — Львів: Вид-во Львів. політехніки, 2014. — 280 с. : іл. — Бібліогр.: с. 276 (16 назв). — ISBN 978-617-607-660-5
Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019). Частина 3: Структури даних. Вступ до алгоритмів (вид. 3). К.І.С. с. 164–243. ISBN 978-617-684-239-2.
Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973.
Алгоритми + структури даних = програми. М.: Мир, 1985; (рос.)

Див. також

Seymour, Lipschutz (2014). Data structures (вид. Revised first). New Delhi, India: McGraw Hill Education. ISBN 9781259029967. OCLC 927793728.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Seymour, Lipschutz (2014). Data structures (вид. Revised first). New Delhi, India: McGraw Hill Education. ISBN 9781259029967. OCLC 927793728.