Структура данных англ data structure программная единица позволяющая хранить и обрабатывать машиной однотипные и или лог

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

(**Бинарное дерево**), простой пример ветвящейся связной структуры данных.

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

Okasaki, 1998, pp. 3—4.

Литература

(Альфред В. Ахо), (Джон Хопкрофт), (Джеффри Д. Ульман). Структуры данных и алгоритмы = Data Structures and Algorithms. — М.: , 2000. — 384 с. — .
Майкл Мейн, Уолтер Савитч. Структуры данных и другие объекты в C++ = Data Structures and Other Objects Using C++. — 2-е изд. — М.: , 2002. — 832 с. — .
Chris Okasaki. Purely Functional Data Structures. — Cambridge University Press, 1998. — 232 с. — .

Ссылки

Структуры данных и хеширование

[_d06009ee041a6024-1] Okasaki, 1998, pp. 3—4.