Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Для использования в других целях, см. Структура данных (значения) .
Не путать с типом данных .
Для получения информации о структуре данных Википедии см. Википедия: Администрирование § Структура данных и разработка .
Структура данных, известная как хеш-таблица .

В информатике , структура данных является организация данных, управление и формат хранения данных, позволяет эффективно доступа и модификации. [1] [2] [3] Точнее, структура данных - это набор значений данных, взаимосвязей между ними, а также функций или операций, которые могут быть применены к данным. [4]

Использование [ править ]

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

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

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

Реализация [ править ]

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

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

Примеры [ править ]

Основная статья: Список структур данных

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

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

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

Языковая поддержка [ править ]

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

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

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

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

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

  • Абстрактный тип данных
  • Параллельная структура данных
  • Модель данных
  • Динамизация
  • Связанная структура данных
  • Список структур данных
  • Постоянная структура данных
  • Обычная старая структура данных
  • Краткая структура данных

Ссылки [ править ]

  1. ^ Кормен, Томас Х .; Leiserson, Charles E .; Ривест, Рональд Л .; Стейн, Клиффорд (2009). Введение в алгоритмы, третье издание (3-е изд.). MIT Press. ISBN 978-0262033848.
  2. ↑ Black, Paul E. (15 декабря 2004 г.). «структура данных» . В Питерсе, Вреда; Блэк, Пол Э. (ред.). Словарь алгоритмов и структур данных [онлайн] . Национальный институт стандартов и технологий . Проверено 6 ноября 2018 .
  3. ^ «Структура данных» . Британская энциклопедия . 17 апреля 2017 . Проверено 6 ноября 2018 .
  4. ^ Вегнер, Питер; Рейли, Эдвин Д. (29 августа 2003 г.). Энциклопедия компьютерных наук . Чичестер, Великобритания: Джон Уайли и сыновья. С. 507–512. ISBN 978-0470864128.
  5. ^ «Абстрактные типы данных» . Технологический институт Вирджинии - структуры данных и алгоритмы CS3 .
  6. ^ Гэвин Пауэлл (2006). «Глава 8: Построение быстродействующих моделей баз данных» . Начало проектирования базы данных . Wrox Publishing . ISBN 978-0-7645-7490-0.
  7. ^ «1.5 Приложения хеш-таблицы» . Университет Реджайны - Лаборатория CS210: Хеш-таблица .
  8. ^ «Когда данные слишком велики, чтобы поместиться в основную память» . homes.sice.indiana.edu .
  9. ^ Дубей, RC (2014). Продвинутая биотехнология: для студентов бакалавриата и магистра биотехнологии и других биологических наук . Нью-Дели: С. Чанд. ISBN 978-81-219-4290-4. OCLC  883695533 .
  10. ^ Seymour, Липшуц (2014). Структуры данных (пересмотренное первое издание). Нью-Дели, Индия: McGraw Hill Education. ISBN 9781259029967. OCLC  927793728 .
  11. ↑ Уолтер Э. Браун (29 сентября 1999 г.). «Примечание по языку C ++: типы POD» . Национальная ускорительная лаборатория Ферми . Архивировано из оригинала на 2016-12-03 . Проверено 6 декабря +2016 .
  12. ^ "Руководство GNU C" . Фонд свободного программного обеспечения . Проверено 15 октября 2014 .
  13. ^ Ван Canneyt, Микаэль (сентябрь 2017). «Free Pascal: Справочное руководство» . Бесплатный Паскаль.
  14. ^ Марк Мойр и Нир Шавит. «Параллельные структуры данных» (PDF) . cs.tau.ac.il .

Библиография [ править ]

  • Питер Брасс, Advanced Data Structures , Cambridge University Press , 2008, ISBN 978-0521880374 
  • Дональд Кнут , Искусство программирования , т. 1. Addison-Wesley , 3-е издание, 1997 г., ISBN 978-0201896831 
  • Динеш Мехта и Сартадж Сахни , Справочник по структурам данных и приложениям , Chapman and Hall / CRC Press , 2004, ISBN 1584884355 
  • Никлаус Вирт , Алгоритмы и структуры данных , Прентис Холл , 1985, ISBN 978-0130220059 

Дальнейшее чтение [ править ]

  • Альфред Ахо , Джон Хопкрофт и Джеффри Уллман , Структуры данных и алгоритмы , Аддисон-Уэсли, 1983, ISBN 0-201-00023-7 
  • GH Gonnet и R. Baeza-Yates , Handbook of Algorithms and Data Structures - in Pascal and C , second edition, Addison-Wesley, 1991, ISBN 0-201-41607-7 
  • Эллис Хоровиц и Сартадж Сахни, Основы структур данных в Паскале , Computer Science Press , 1984, ISBN 0-914894-94-3 

Внешние ссылки [ править ]

  • Описания из Словаря алгоритмов и структур данных
  • Курс структур данных
  • Исследование структур данных с точки зрения .NET
  • Шаффер К. Структуры данных и анализ алгоритмов