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