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

Бінарне дерево, простий приклад ветвящейся зв'язної структури даних.

Структура даних ( англ. data structure ) - Програмна одиниця, що дозволяє зберігати й обробляти безліч однотипних і / або логічно пов'язаних даних в обчислювальній техніці. Для додавання, пошуку, зміни та видалення даних структура даних надає деякий набір функцій, складових її інтерфейс.

Термін "структура даних" може мати кілька близьких, але тим не менше різних значення [1] :

  • Абстрактний тип даних;
  • Реалізація будь-якого абстрактного типу даних;
  • Примірник типу даних, наприклад, конкретний список;
  • У контексті функціонального програмування - унікальна одиниця ( англ. unique identity ), Зберігається при змінах. Про неї неформально говорять як про одну структуру даних, незважаючи на можливу наявність різних версій.

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

Різні види структур даних підходять для різних додатків; деякі з них мають вузьку спеціалізацію для певних завдань. Наприклад, B-дерева зазвичай підходять для створення баз даних, в той час як хеш-таблиці використовуються повсюдно для створення різного роду словників, наприклад, для відображення доменних імен в інтернет-адреси комп'ютерів.

При розробці програмного забезпечення складність реалізації і якість роботи програм істотно залежить від правильного вибору структур даних. Це розуміння дало початок формальним методам розробки та мов програмування, в яких саме структури даних, а не алгоритми, є наріжним архітектури програмного засобу. Велика частина таких мов володіє певним типом модульності, що дозволяє структурам даних безпечно переіспользоваться в різних додатках. Об'єктно-орієнтовані мови, такі як Java, C # і C + +, є прикладами такого підходу.

Багато класичні структури даних представлені в стандартних бібліотеках мов програмування або безпосередньо вбудовані в мови програмування. Наприклад, структура даних хеш-таблиця вбудована в мови програмування Lua, Perl, Python, Ruby, Tcl та ін Широко використовується стандартна бібліотека шаблонів (STL) мови C + +.

Фундаментальними будівельними блоками для більшої частини структур даних є масиви, записи ( struct в Сі і record в Паскалі), розмічені об'єднання ( union в Сі) і посилання. Наприклад, двусвязний список може бути побудований за допомогою записів та посилань, де кожен запис (вузол) буде зберігати дані та посилання на "лівий" і "правий" вузли.


Порівняння структур даних у функціональному та імперативний програмуванні

Проектувати структури даних для функціональних мов більш складно, ніж для імперативних, як мінімум з двох причин [1] :

  1. Майже всі структури даних інтенсивно використовують присвоювання, яке в чисто функціональному стилі не використовується;
  2. Функціональні структури даних є більш гнучкими, і тому там, де в імперативному програмуванні стара версія втрачається, просто замінюючись нової, у функціональному вона автоматично продовжує існувати. Іншими словами, в імперативному програмуванні (якщо не прийняти спеціальних заходів, що можуть серйозно ускладнити програму) структури даних є ефемерними ( англ. ephemeral ), А в функціональних програмах вони як правило постійні ( англ. persistent ).

Примітки

  1. 1 2 Okasaki, 1998, pp. 3-4

Література

  • Альфред В. Ахо, Джон Хопкрофт, Джеффрі Д. Ульман. Структури даних та алгоритми = Data Structures and Algorithms. - М .: Вільямс, 2000. - 384 с. - ISBN 0-201-00023-7
  • Майкл Мейн, Уолтер Савітч. Структури даних та інші об'єкти в C + + = Data Structures and Other Objects Using C + +. - 2-ге вид. - М .: Вільямс, 2002. - 832 с. - ISBN 0-201-70297-5
  • Chris Okasaki Purely Functional Data Structures. - Cambridge University Press, 1998. - 232 с. - ISBN 978-0521663502