Структура данных - Data structure

Структура данных, известная как хеш-таблица .

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

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

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

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

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

Реализация

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

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

Примеры

Python 3. Стандартный тип hierarchy.png

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

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

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

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

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

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

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

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

Смотрите также

использованная литература

Библиография

дальнейшее чтение

внешние ссылки