Jump to content

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Массив представляет собой ряд элементов в определенном порядке, обычно все одного типа (в зависимости от языка отдельные элементы могут быть либо все элементы одного типа, либо могут быть практически любого типа). Доступ к элементам осуществляется с использованием целочисленного индекса, чтобы указать, какой элемент требуется. В типичных реализациях для элементов массивов выделяются смежные слова памяти (но это не всегда необходимо). Массивы могут иметь фиксированную длину или изменять размер.
  • ( Связанный список также называемый просто списком ) — это линейная коллекция элементов данных любого типа, называемых узлами, где каждый узел сам по себе имеет значение и указывает на следующий узел в связанном списке. Основное преимущество связанного списка перед массивом заключается в том, что значения всегда можно эффективно вставлять и удалять без перемещения остальной части списка. Однако некоторые другие операции, такие как произвольный доступ к определенному элементу, в списках выполняются медленнее, чем в массивах.
  • Запись совокупную (также называемая кортежем или структурой ) представляет собой структуру данных . Запись — это значение, которое содержит другие значения, обычно в фиксированном количестве и последовательности и обычно индексируемое по именам. Элементы записей обычно называются полями или членами . В контексте объектно-ориентированного программирования записи называются старыми простыми структурами данных, что отличает их от объектов. [13]
  • Хэш-таблицы , также известные как хэш-карты, представляют собой структуры данных, обеспечивающие быстрый поиск значений на основе ключей. Они используют хеш-функцию для сопоставления ключей с индексами в массиве, обеспечивая в среднем доступ к постоянному времени. Хэш-таблицы обычно используются в словарях, кэшах и индексации баз данных. Однако могут возникнуть хеш-коллизии, которые могут повлиять на их производительность. Для обработки коллизий используются такие методы, как цепочка и открытая адресация.
  • Графы — это наборы узлов, соединенных ребрами, представляющие отношения между сущностями. Графы можно использовать, среди прочего, для моделирования социальных сетей, компьютерных сетей и транспортных сетей. Они состоят из вершин (узлов) и ребер (соединений между узлами). Графы могут быть направленными или неориентированными, иметь циклы или быть ациклическими. Алгоритмы обхода графа включают поиск в ширину и поиск в глубину.
  • Стеки и очереди — это абстрактные типы данных, которые можно реализовать с помощью массивов или связанных списков. Стек имеет две основные операции: push (добавляет элемент на вершину стека) и pop (удаляет самый верхний элемент из стека), которые следуют принципу «Последний вошел — первый вышел» (LIFO). Очереди имеют две основные операции: постановку в очередь (добавление элемента в конец очереди) и удаление из очереди (удаление элемента из начала очереди), которые следуют принципу «первым вошел — первым вышел» (FIFO).
  • Деревья представляют собой иерархическую организацию элементов. Дерево состоит из узлов, соединенных ребрами, причем один узел является корнем, а все остальные узлы образуют поддеревья. Деревья широко используются в различных алгоритмах и сценариях хранения данных. Двоичные деревья (особенно кучи ), AVL-деревья и B-деревья — некоторые популярные типы деревьев. Они обеспечивают эффективный и оптимальный поиск, сортировку и иерархическое представление данных.
  • Дерево , также известное как префиксное дерево, представляет собой специализированную древовидную структуру данных , используемую для эффективного поиска строк. Пытается сохранить символы строки как узлы, где каждое ребро представляет символ. Они особенно полезны в сценариях обработки текста, таких как автозаполнение, проверка орфографии и реализация словаря. Попытки обеспечивают быстрый поиск и операции со строками на основе префиксов.

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

Большинство языков ассемблера и некоторые языки низкого уровня , такие как 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: неподходящий URL ( ссылка )
  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 . OCLC   883695533 .
  12. ^ Сеймур, Липшуц (2014). Структуры данных (пересмотренное первое издание). Нью-Дели, Индия: Образование Макгроу Хилл. ISBN  9781259029967 . OCLC   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 г.

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

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

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

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 0184651c8ca5b131f0aee185969d1fac__1718861220
URL1:https://arc.ask3.ru/arc/aa/01/ac/0184651c8ca5b131f0aee185969d1fac.html
Заголовок, (Title) документа по адресу, URL1:
Data structure - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)