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

Термин «структура данных» может иметь несколько близких, но тем не менее различных значений :

• Абстрактный тип данных ;
• Реализация какого-либо абстрактного типа данных;
• Экземпляр типа данных, например, конкретный список ;
• В контексте функционального программирования — уникальная единица ( англ. unique identity ), сохраняющаяся при изменениях. О ней неформально говорят как об одной структуре данных, несмотря на возможное наличие различных версий.

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

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

При разработке программного обеспечения сложность реализации и качество работы программ существенно зависят от правильного выбора структур данных. Это понимание дало начало формальным методам разработки и языкам программирования, в которых именно структуры данных, а не алгоритмы, ставятся во главу архитектуры программного средства. Большая часть таких языков обладает определённым типом модульности , позволяющим структурам данных безопасно переиспользоваться в различных приложениях. Объектно-ориентированные языки , такие как Java , C# и C++ , являются примерами такого подхода.

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

Фундаментальными строительными блоками для большей части структур данных являются массивы , записи ( struct в Си и record в Паскале ), размеченные объединения ( union в Си) и ссылки . Например, двусвязный список может быть построен с помощью записей и ссылок, где каждая запись (узел) будет хранить данные и ссылки на «левый» и «правый» узлы.

Сравнение структур данных в функциональном и императивном программировании

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

1. Почти все структуры данных интенсивно используют присваивание , которое в чисто функциональном стиле не используется;
2. Функциональные структуры данных являются более гибкими, и поэтому там, где в императивном программировании старая версия теряется, просто заменяясь новой, в функциональном она автоматически продолжает существовать. Другими словами, в императивном программировании (если не принять особых мер, которые могут серьёзно усложнить программу) структуры данных являются эфемерными ( англ. ephemeral ), а в функциональных программах они как правило постоянные ( англ. persistent ).

См. также

• Онтология (информатика)

Примечания

Литература

• Альфред В. Ахо, Джон Хопкрофт , Джеффри Д. Ульман. Структуры данных и алгоритмы = 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 .

Ссылки