stringtranslate.com

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

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

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

Применение

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

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

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

Выполнение

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

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

Примеры

Стандартная иерархия типов языка программирования Python 3 .

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

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

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

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

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

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

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

Рекомендации

  1. ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2009). Введение в алгоритмы, третье издание (3-е изд.). Массачусетский технологический институт Пресс. ISBN 978-0262033848.
  2. ↑ Блэк, Пол Э. (15 декабря 2004 г.). "структура данных". В Питерсе, Вреда; Блэк, Пол Э. (ред.). Словарь алгоритмов и структур данных [онлайн] . Национальный институт стандартов и технологий . Проверено 6 ноября 2018 г.
  3. ^ «Структура данных». Британская энциклопедия . 17 апреля 2017 года . Проверено 6 ноября 2018 г.
  4. ^ Вегнер, Питер; Рейли, Эдвин Д. (29 августа 2003 г.). Энциклопедия информатики. Чичестер, Великобритания: Джон Уайли и сыновья. стр. 507–512. ISBN 978-0470864128.
  5. ^ «Абстрактные типы данных». Технологический институт Вирджинии — Структуры данных и алгоритмы CS3 . Архивировано из оригинала 10 февраля 2023 г. Проверено 15 февраля 2023 г.
  6. ^ Гэвин Пауэлл (2006). «Глава 8: Построение быстропроизводительных моделей баз данных». Начало проектирования базы данных . Издательство Wrox . ISBN 978-0-7645-7490-0. Архивировано из оригинала 18 августа 2007 г.{{cite book}}: CS1 maint: unfit URL (link)
  7. ^ «1.5 Применение хеш-таблицы». Университет Реджайны — Лаборатория CS210: Хэш-таблица . Архивировано из оригинала 27 апреля 2021 г. Проверено 14 июня 2018 г.
  8. ^ «Когда данные слишком велики, чтобы поместиться в основную память» . Университет Индианы, Блумингтон – Структуры данных (C343/A594) . 2014. Архивировано из оригинала 10 апреля 2018 г.
  9. ^ Вайшнави, Гунджал; Шраддха, Гаване; Йогешвари, Джоши (21 июня 2021 г.). «Обзорный доклад по детальному распознаванию выражений лица с использованием машинного обучения» (PDF) . Международный журнал компьютерных приложений . 183 (11): 47–49. дои : 10.5120/ijca2021921427.
  10. ^ Нивергельт, Юрг; Видмайер, Питер (1 января 2000 г.), Сак, Дж.-Р.; Уррутиа, Дж. (ред.), «Глава 17. Пространственные структуры данных: концепции и варианты проектирования», Справочник по вычислительной геометрии , Амстердам: Северная Голландия, стр. 725–764, ISBN 978-0-444-82537-7, получено 12 ноября 2023 г.
  11. ^ Дубей, RC (2014). Передовая биотехнология: для студентов бакалавриата и магистратуры, изучающих биотехнологию и другие биологические науки . Нью-Дели: С. Чанд. ISBN 978-81-219-4290-4. ОСЛК  883695533.
  12. ^ Сеймур, Липшуц (2014). Структуры данных (пересмотренное первое издание). Нью-Дели, Индия: Образование Макгроу Хилл. ISBN 9781259029967. ОКЛК  927793728.
  13. ↑ Уолтер Э. Браун (29 сентября 1999 г.). «Примечание по языку C++: типы POD». Национальная ускорительная лаборатория имени Ферми . Архивировано из оригинала 3 декабря 2016 г. Проверено 6 декабря 2016 г.
  14. ^ «Руководство GNU C». Фонд свободного программного обеспечения . Проверено 15 октября 2014 г.
  15. ^ Ван Каннейт, Майкл (сентябрь 2017 г.). «Free Pascal: Справочное руководство». Бесплатный Паскаль.
  16. ^ Марк Мойр и Нир Шавит. «Параллельные структуры данных» (PDF) . cs.tau.ac.il. _ Архивировано из оригинала (PDF) 1 апреля 2011 г.

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

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

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