Структура данных
В информатике структура данных — это организация данных и формат хранения, который обычно выбирается для эффективного доступа к данным. [1] [2] [3] Точнее, структура данных — это совокупность значений данных, связей между ними, а также функций или операций , которые можно применять к данным. [4] е. это алгебраическая структура данных т . .
Использование [ править ]
Структуры данных служат основой для абстрактных типов данных (ADT). ADT определяет логическую форму типа данных. Структура данных реализует физическую форму типа данных . [5]
Различные типы структур данных подходят для разных типов приложений, а некоторые узкоспециализированы для конкретных задач. Например, реляционные базы данных обычно используют индексы B-дерева для поиска данных. [6] в то время как компилятора реализации обычно используют хеш-таблицы для поиска идентификаторов . [7]
Структуры данных предоставляют средства для эффективного управления большими объемами данных для таких целей, как большие базы данных и службы индексирования в Интернете. Обычно эффективные структуры данных являются ключом к разработке эффективных алгоритмов . Некоторые формальные методы проектирования и языки программирования подчеркивают, что структуры данных, а не алгоритмы, являются ключевым организующим фактором при разработке программного обеспечения. Структуры данных могут использоваться для организации хранения и извлечения информации, хранящейся как в основной , так и во вторичной памяти . [8]
Реализация [ править ]
Структуры данных могут быть реализованы с использованием различных языков программирования и методов, но все они имеют общую цель — эффективную организацию и хранение данных. [9] Структуры данных обычно основаны на способности компьютера извлекать и сохранять данные в любом месте своей памяти, указанном указателем — битовой строкой , представляющей адрес памяти , которая сама может храниться в памяти и управляться программой. Таким образом, структуры данных массива и записи основаны на вычислении адресов элементов данных с помощью арифметических операций , тогда как связанные структуры данных основаны на хранении адресов элементов данных внутри самой структуры. Такой подход к структурированию данных имеет глубокие последствия для эффективности и масштабируемости алгоритмов. Например, непрерывное выделение памяти в массивах облегчает операции быстрого доступа и изменения, что приводит к оптимизации производительности в сценариях последовательной обработки данных. [10]
Реализация структуры данных обычно требует написания набора процедур , которые создают экземпляры этой структуры и управляют ими. Эффективность структуры данных нельзя анализировать отдельно от этих операций. Это наблюдение мотивирует теоретическую концепцию абстрактного типа данных , структуры данных, которая определяется косвенно операциями, которые могут быть выполнены над ней, и математическими свойствами этих операций (включая их пространственную и временную стоимость). [11]
Примеры [ править ]
Существует множество типов структур данных, обычно построенных на основе более простых примитивных типов данных . Хорошо известны примеры: [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]
См. также [ править ]
Ссылки [ править ]
- ^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2009). Введение в алгоритмы, третье издание (3-е изд.). Массачусетский технологический институт Пресс. ISBN 978-0262033848 .
- ^ Блэк, Пол Э. (15 декабря 2004 г.). "структура данных" . В Питерсе, Вреда; Блэк, Пол Э. (ред.). Словарь алгоритмов и структур данных [онлайн] . Национальный институт стандартов и технологий . Проверено 6 ноября 2018 г.
- ^ "Структура данных" . Британская энциклопедия . 17 апреля 2017 года . Проверено 6 ноября 2018 г.
- ^ Вегнер, Питер; Рейли, Эдвин Д. (29 августа 2003 г.). Энциклопедия информатики . Чичестер, Великобритания: Джон Уайли и сыновья. стр. 507–512. ISBN 978-0470864128 .
- ^ «Абстрактные типы данных» . Технологический институт Вирджинии — Структуры данных и алгоритмы CS3 . Архивировано из оригинала 10 февраля 2023 г. Проверено 15 февраля 2023 г.
- ^ Гэвин Пауэлл (2006). «Глава 8: Построение быстропроизводительных моделей баз данных» . Начало проектирования базы данных . Издательство Wrox . ISBN 978-0-7645-7490-0 . Архивировано из оригинала 18 августа 2007 г.
{{cite book}}: CS1 maint: неподходящий URL ( ссылка ) - ^ «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, ISBN 978-0-444-82537-7 , получено 12 ноября 2023 г.
- ^ Дубей, RC (2014). Передовая биотехнология: для студентов бакалавриата и магистратуры, изучающих биотехнологию и другие биологические науки . Нью-Дели: С. Чанд. ISBN 978-81-219-4290-4 . OCLC 883695533 .
- ^ Сеймур, Липшуц (2014). Структуры данных (пересмотренное первое издание). Нью-Дели, Индия: Образование Макгроу Хилл. ISBN 9781259029967 . OCLC 927793728 .
- ^ Уолтер Э. Браун (29 сентября 1999 г.). «Примечание по языку C++: типы POD» . Национальная ускорительная лаборатория имени Ферми . Архивировано из оригинала 3 декабря 2016 г. Проверено 6 декабря 2016 г.
- ^ «Руководство GNU C» . Фонд свободного программного обеспечения . Проверено 15 октября 2014 г.
- ^ Ван Каннейт, Майкл (сентябрь 2017 г.). «Free Pascal: Справочное руководство» . Бесплатный Паскаль.
- ^ Марк Мойр и Нир Шавит. «Параллельные структуры данных» (PDF) . cs.tau.ac.il. Архивировано из оригинала (PDF) 1 апреля 2011 г.
Библиография [ править ]
- Питер Брасс, Расширенные структуры данных , издательство Кембриджского университета , 2008 г., ISBN 978-0521880374
- Дональд Кнут , Искусство компьютерного программирования , т. 1. Аддисон-Уэсли , 3-е издание, 1997 г., ISBN 978-0201896831
- Динеш Мехта и Сартадж Сахни , Справочник по структурам данных и приложениям , Чепмен и Холл / CRC Press , 2004, ISBN 1584884355
- Никлаус Вирт , Алгоритмы и структуры данных , Прентис Холл , 1985, ISBN 978-0130220059
Дальнейшее чтение [ править ]
- Альфред Ахо , Джон Хопкрофт и Джеффри Уллман , Структуры данных и алгоритмы , Аддисон-Уэсли, 1983, ISBN 0-201-00023-7
- Г.Х. Гонне и Р. Баеза-Йейтс , Справочник по алгоритмам и структурам данных - на языке Паскаль и C , второе издание, Addison-Wesley, 1991, ISBN 0-201-41607-7
- Эллис Горовиц и Сартадж Сахни, Основы структур данных в Паскале , Computer Science Press , 1984, ISBN 0-914894-94-3
