stringtranslate.com

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

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

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

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

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

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

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

Выполнение

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

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

Примеры

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

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

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

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

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

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

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

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

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

Ссылки

  1. ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2009). Введение в алгоритмы, третье издание (3-е изд.). Массачусетский технологический институт Пресс. ISBN 978-0262033848.
  2. ^ Black, Paul E. (15 декабря 2004 г.). "структура данных". В Pieterse, Vreda; Black, Paul E. (ред.). Словарь алгоритмов и структур данных [онлайн] . Национальный институт стандартов и технологий . Получено 2018-11-06 .
  3. ^ "Структура данных". Encyclopaedia Britannica . 17 апреля 2017 г. Получено 06.11.2018 .
  4. ^ Вегнер, Питер; Рейлли, Эдвин Д. (2003-08-29). Энциклопедия компьютерных наук. Чичестер, Великобритания: John Wiley and Sons. стр. 507–512. ISBN 978-0470864128.
  5. ^ "Абстрактные типы данных". Virginia Tech - CS3 Data Structures & Algorithms . Архивировано из оригинала 2023-02-10 . Получено 2023-02-15 .
  6. ^ Гэвин Пауэлл (2006). "Глава 8: Создание быстродействующих моделей баз данных". Начало проектирования баз данных . Wrox Publishing . ISBN 978-0-7645-7490-0. Архивировано из оригинала 2007-08-18.{{cite book}}: CS1 maint: unfit URL (link)
  7. ^ "1.5 Applications of a Hash Table". University of Regina - CS210 Lab: Hash Table . Архивировано из оригинала 2021-04-27 . Получено 2018-06-14 .
  8. ^ «Когда данные слишком велики, чтобы поместиться в основную память». Университет Индианы в Блумингтоне — Структуры данных (C343/A594) . 2014. Архивировано из оригинала 10.04.2018.
  9. ^ Вайшнави, Гунджал; Шраддха, Гаване; Йогешвари, Джоши (2021-06-21). «Обзорная статья по мелкозернистому распознаванию выражений лица с использованием машинного обучения» (PDF) . Международный журнал компьютерных приложений . 183 (11): 47–49. doi :10.5120/ijca2021921427.
  10. ^ Нивергельт, Юрг; Видмайер, Питер (2000-01-01), Сак, Дж. -Р.; Уррутия, Дж. (ред.), «Глава 17 - Пространственные структуры данных: концепции и выбор дизайна», Справочник по вычислительной геометрии , Амстердам: Северная Голландия, стр. 725–764, ISBN 978-0-444-82537-7, получено 2023-11-12
  11. ^ Дубей, RC (2014). Продвинутая биотехнология: Для студентов бакалавриата и магистратуры по биотехнологии и другим биологическим наукам . Нью-Дели: S Chand. ISBN 978-81-219-4290-4. OCLC  883695533.
  12. ^ Сеймур, Липшуц (2014). Структуры данных (пересмотренное первое издание). Нью-Дели, Индия: McGraw Hill Education. ISBN 9781259029967. OCLC  927793728.
  13. ^ Уолтер Э. Браун (29 сентября 1999 г.). «Заметка по языку C++: типы POD». Национальная ускорительная лаборатория имени Ферми . Архивировано из оригинала 2016-12-03 . Получено 6 декабря 2016 г.
  14. ^ "Руководство GNU C". Free Software Foundation . Получено 2014-10-15 .
  15. ^ Ван Каннейт, Майкл (сентябрь 2017 г.). «Free Pascal: Справочное руководство». Бесплатный Паскаль.
  16. ^ Марк Мойр и Нир Шавит. "Конкурентные структуры данных" (PDF) . cs.tau.ac.il . Архивировано из оригинала (PDF) 2011-04-01.

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

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

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