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

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

Использование

Структуры данных служат основой для абстрактных типов данных (ADT, abstract data types). ADT определяет логическую форму типа данных. Структура данных реализует физическую форму типа данных.

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

Структуры данных предоставляют средства для эффективного управления большими объемами данных для таких применений, как большие базы данных и службы индексирования в Интернете. Как правило, эффективные структуры данных являются ключом к разработке эффективных алгоритмов. Некоторые формальные методы проектирования и языки программирования подчеркивают структуры данных, а не алгоритмы, как ключевой организующий фактор в разработке программного обеспечения. Структуры данных могут быть использованы для организации хранения и поиска информации, хранящейся как в основной памяти, так и во вторичной памяти.

Реализация

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

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

Примеры структур данных

Существует множество типов структур данных, в основном построенных на более простых примитивных типах данных:

• Массив - это количество элементов в определенном порядке, как правило, одного и того же типа (в зависимости от языка отдельные элементы могут быть либо одного типа, либо почти любого типа). Доступ к элементам осуществляется с помощью целочисленного индекса, чтобы указать, какой элемент требуется. Типичные реализации выделяют смежные слова памяти для элементов массивов (но это не всегда необходимо). Массивы могут быть фиксированной длины или изменяемого размера.
• Связанный список (также называемый просто списком) представляет собой линейную коллекцию элементов данных любого типа, называемых узлами, где каждый узел имеет свое значение и указывает на следующий узел в связанном списке. Основное преимущество связанного списка над массивом состоит в том, что значения всегда можно эффективно вставлять и удалять без перемещения остальной части списка. Однако некоторые другие операции, такие как произвольный доступ к определенному элементу, в списках выполняются медленнее, чем в массивах.
• Запись (также называемая кортежем (tuple) или структурой) представляет собой совокупную структуру данных. Запись - это значение, которое содержит другие значения, обычно в фиксированном количестве и последовательности и обычно индексируется по именам. Элементы записей обычно называются полями или членами.
• Объединение (union) - это структура данных, которая определяет, какой из ряда разрешенных типов примитивов может быть сохранен в его экземплярах, например, float или длинное целое число. Сравните с записью, которая может быть определена как содержащая число с плавающей точкой и целое число; тогда как в объединении существует только одно значение за раз. Достаточно места выделено, чтобы содержать самый широкий тип данных.
• Помеченное объединение (tagged union) (также называемое вариантом, записью варианта, распознаваемым объединением или непересекающимся объединением) содержит дополнительное поле, указывающее его текущий тип, для повышения безопасности типов.
• Объект - это структура данных, которая содержит поля данных, как это делает запись, а также различные методы, которые работают с содержимым данных. Объект - это экземпляр класса из таксономии в памяти. В контексте объектно-ориентированного программирования записи известны как простые старые структуры данных, чтобы отличать их от объектов.

Кроме того, графы и двоичные деревья являются другими часто используемыми структурами данных.

Языковая поддержка

Большинство языков ассемблера и некоторые языки низкого уровня, такие как BCPL (Basic Combined Programming Language), не имеют встроенной поддержки структур данных. С другой стороны, многие языки программирования высокого уровня и некоторые языки ассемблера более высокого уровня, такие как MASM, имеют специальный синтаксис или другую встроенную поддержку определенных структур данных, таких как записи и массивы. Например, язык C (прямой потомок BCPL) и язык Pascal поддерживают структуры и записи соответственно в дополнение к векторам (одномерные массивы) и многомерным массивам.

Большинство языков программирования имеют своего рода библиотечный механизм, который позволяет реализациям структуры данных повторно использоваться различными программами. Современные языки обычно поставляются со стандартными библиотеками, которые реализуют наиболее распространенные структуры данных. Примерами являются библиотека стандартных шаблонов C++, Java Collections Framework и Microsoft .NET Framework.

Современные языки также обычно поддерживают модульное программирование, разделение интерфейса библиотечного модуля и его реализации. Некоторые предоставляют непрозрачные типы данных, которые позволяют клиентам скрывать детали реализации. Объектно-ориентированные языки программирования, такие как C++, Java и Smalltalk, обычно используют классы для этой цели.

Многие известные структуры данных имеют параллельные версии, которые позволяют нескольким вычислительным потокам одновременно обращаться к одному конкретному экземпляру структуры данных.