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

Материал из Википедии — свободной энциклопедии

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

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

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

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

Поскольку структуры данных настолько критичны для профессиональных программ, многие из них поддержаны в стандартных библиотеках современных языках программирования и окружения, таких как STL языка C++, Java API и Платформа .NET.

Фундаментальными строительными блоками для большей части структур данных являются массивы, записи, размеченные объединения и ссылки. Например, зануляемая ссылка (ссылка которая может принимать значение null) является комбинацией ссылок и размеченных объединений, а простейшая связная структура данных, которая называется связанным списком, может быть построена из записей и зануляемых ссылок.

[править] Смотри также

• Список структур данных — каталог структур данных общего назначения
• Структуры данных постоянного хранения
• Неструктурированные данные