Введение
Особый способ хранения и организации данных в компьютере. Информация о структуре данных в Википедии.
information on Wikipedia's data structure
In computer science, a data structure is a data organization, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data, i. e., it is an algebraic structure about data.
В информатике структура данных — это организация и формат хранения данных, обычно выбираемые для обеспечения эффективного доступа к ним. Более точно, структура данных представляет собой совокупность значений данных, отношений между ними и функций или операций, которые могут быть применены к этим данным, то есть это алгебраическая структура, относящаяся к данным.
information on Wikipedia's data structure
In computer science, a data structure is a data organization, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data, i. e., it is an algebraic structure about data.
Использование
Структуры данных служат основой для абстрактных типов данных (ADT). ADT определяет логическую форму типа данных, а структура данных реализует его физическую форму. Различные типы структур данных подходят для разных областей применения, при этом некоторые из них высокоспециализированы для конкретных задач. Например, реляционные базы данных обычно используют B-деревья для поиска данных, а реализации компиляторов – хэш-таблицы для поиска идентификаторов. Структуры данных предоставляют средства для эффективного управления большими объемами данных, что необходимо для таких приложений, как крупные базы данных и интернет-индексаторы. Как правило, эффективные структуры данных являются ключевым фактором при разработке эффективных алгоритмов. Некоторые формальные методы проектирования и языки программирования делают акцент на структурах данных, а не на алгоритмах, как на основном организующем принципе при разработке программного обеспечения. Структуры данных могут использоваться для организации хранения и извлечения информации, хранящейся как в оперативной, так и во внешней памяти.
Реализация
Структуры данных могут быть реализованы с использованием различных языков и методов программирования, но все они преследуют общую цель – эффективно организовывать и хранить данные. Структуры данных, как правило, основаны на способности компьютера извлекать и хранить данные в любом месте своей памяти, определяемом указателем – последовательностью битов, представляющей адрес памяти, который сам может храниться в памяти и обрабатываться программой. Таким образом, структуры данных, такие как массивы и записи, основаны на вычислении адресов элементов данных с помощью арифметических операций, в то время как связные структуры данных основаны на хранении адресов элементов данных внутри самой структуры. Такой подход к организации данных имеет глубокие последствия для эффективности и масштабируемости алгоритмов. Например, непрерывное выделение памяти в массивах обеспечивает быстрый доступ и изменение данных, что приводит к оптимизации производительности в сценариях последовательной обработки данных. Реализация структуры данных обычно требует написания набора процедур, которые создают и манипулируют экземплярами этой структуры. Эффективность структуры данных нельзя анализировать отдельно от этих операций. Это наблюдение обуславливает теоретическую концепцию абстрактного типа данных – структуры данных, которая определяется косвенно операциями, которые над ней могут выполняться, и математическими свойствами этих операций (включая их затраты по пространству и времени).
Примеры
Существует множество типов структур данных, как правило, построенных на более простых примитивных типах данных. Хорошо известные примеры: массив — это последовательность элементов в определенном порядке, как правило, все одного и того же типа (в зависимости от языка, отдельные элементы могут быть либо принудительно одного и того же типа, либо могут быть почти любого типа). Доступ к элементам осуществляется с помощью целочисленного индекса для указания требуемого элемента. Типичные реализации выделяют смежные ячейки памяти для элементов массивов (но это не всегда обязательно). Массивы могут быть фиксированной длины или изменяемого размера. Связный список (также просто список) — это линейная коллекция элементов данных любого типа, называемых узлами, где каждый узел содержит значение и указывает на следующий узел в списке. Основное преимущество связного списка над массивом заключается в том, что значения всегда можно эффективно вставлять и удалять без перемещения остальной части списка. Однако некоторые другие операции, такие как произвольный доступ к определенному элементу, выполняются в списках медленнее, чем в массивах. Запись (также называемая кортежем или структурой) — это агрегированная структура данных. Запись — это значение, которое содержит другие значения, как правило, в фиксированном количестве и последовательности и, как правило, индексируется по именам. Элементы записей обычно называются полями или членами. В контексте объектно-ориентированного программирования записи известны как простые старые структуры данных (plain old data structures), чтобы отличить их от объектов. Хеш-таблицы, также известные как хеш-карты, — это структуры данных, которые обеспечивают быстрый поиск значений по ключам. Они используют хеш-функцию для сопоставления ключей с индексами в массиве, что позволяет осуществлять доступ за постоянное время в среднем случае. Хеш-таблицы обычно используются в словарях, кэшах и индексации баз данных. Однако могут возникать коллизии хешей, которые могут повлиять на их производительность. Для обработки коллизий используются такие методы, как цепочки и открытая адресация. Графы — это коллекции узлов, соединенных ребрами, представляющие отношения между сущностями. Графы могут использоваться для моделирования социальных сетей, компьютерных сетей и транспортных сетей и т. д. Они состоят из вершин (узлов) и ребер (соединений между узлами). Графы могут быть ориентированными или неориентированными и могут содержать циклы или быть ациклическими. Алгоритмы обхода графа включают поиск в ширину и поиск в глубину. Стек и очередь — это абстрактные типы данных, которые могут быть реализованы с использованием массивов или связных списков. Стек имеет две основные операции: push (добавляет элемент на вершину стека) и pop (удаляет верхний элемент из стека), которые следуют принципу LIFO (Last In, First Out — последний пришел, первый ушел). Очереди имеют две основные операции: enqueue (добавляет элемент в конец очереди) и dequeue (удаляет элемент из начала очереди), которые следуют принципу FIFO (First In, First Out — первый пришел, первый ушел). Деревья представляют собой иерархическую организацию элементов. Дерево состоит из узлов, соединенных ребрами, при этом один узел является корнем, а все остальные узлы образуют поддеревья. Деревья широко используются в различных алгоритмах и сценариях хранения данных. Двоичные деревья (особенно кучи), деревья AVL и B-деревья — это некоторые популярные типы деревьев. Они обеспечивают эффективный и оптимальный поиск, сортировку и иерархическое представление данных. Префиксное дерево (trie) — это специализированная структура данных дерева, используемая для эффективного поиска строк. Префиксные деревья хранят символы строки в виде узлов, при этом каждое ребро представляет символ. Они особенно полезны в сценариях обработки текста, таких как автозаполнение, проверка орфографии и реализация словарей. Префиксные деревья обеспечивают быстрый поиск и операции на основе префиксов для строк.
An array is a number of elements in a specific order, typically all of the same type (depending on the language, individual elements may either all be forced to be the same type, or may be of almost any type). Elements are accessed using an integer index to specify which element is required. Typical implementations allocate contiguous memory words for the elements of arrays (but this is not always a necessity). Arrays may be fixed length or resizable. A linked list (also just called list) is a linear collection of data elements of any type, called nodes, where each node has itself a value, and points to the next node in the linked list. The principal advantage of a linked list over an array is that values can always be efficiently inserted and removed without relocating the rest of the list. Certain other operations, such as random access to a certain element, are however slower on lists than on arrays. A record (also called tuple or struct) is an aggregate data structure. A record is a value that contains other values, typically in fixed number and sequence and typically indexed by names. The elements of records are usually called fields or members. In the context of object oriented programming, records are known as plain old data structures to distinguish them from objects. Hash tables, also known as hash maps, are data structures that provide fast retrieval of values based on keys. They use a hashing function to map keys to indexes in an array, allowing for constant time access in the average case. Hash tables are commonly used in dictionaries, caches, and database indexing. However, hash collisions can occur, which can impact their performance. Techniques like chaining and open addressing are employed to handle collisions. Graphs are collections of nodes connected by edges, representing relationships between entities. Graphs can be used to model social networks, computer networks, and transportation networks, among other things. They consist of vertices (nodes) and edges (connections between nodes). Graphs can be directed or undirected, and they can have cycles or be acyclic. Graph traversal algorithms include breadth first search and depth first search. Stacks and queues are abstract data types that can be implemented using arrays or linked lists. A stack has two primary operations: push (adds an element to the top of the stack) and pop (removes the topmost element from the stack), that follow the Last In, First Out (LIFO) principle. Queues have two main operations: enqueue (adds an element to the rear of the queue) and dequeue (removes an element from the front of the queue) that follow the First In, First Out (FIFO) principle. Trees represent a hierarchical organization of elements. A tree consists of nodes connected by edges, with one node being the root and all other nodes forming subtrees. Trees are widely used in various algorithms and data storage scenarios. Binary trees (particularly heaps), AVL trees, and B trees are some popular types of trees. They enable efficient and optimal searching, sorting, and hierarchical representation of data. A trie, also known as a prefix tree, is a specialized tree data structure used for the efficient retrieval of strings. Tries store characters of a string as nodes, with each edge representing a character. They are particularly useful in text processing scenarios like autocomplete, spell checking, and dictionary implementations. Tries enable fast searching and prefix based operations on strings.
Языковая поддержка
Большинство языков ассемблера и некоторые языки низкого уровня, такие как BCPL (Basic Combined Programming Language), не имеют встроенной поддержки структур данных. С другой стороны, многие языки программирования высокого уровня и некоторые языки ассемблера более высокого уровня, такие как MASM, имеют специальный синтаксис или другие встроенные средства поддержки определенных структур данных, таких как записи и массивы. Например, языки C (прямой потомок BCPL) и Pascal поддерживают структуры и записи соответственно, в дополнение к векторам (одномерным массивам) и многомерным массивам. Большинство языков программирования предоставляют тот или иной библиотечный механизм, позволяющий повторно использовать реализации структур данных в различных программах. Современные языки обычно поставляются со стандартными библиотеками, реализующими наиболее распространенные структуры данных. Примерами служат библиотека стандартных шаблонов C++, Java Collections Framework и Microsoft .NET Framework. Современные языки также обычно поддерживают модульное программирование, разделяющее интерфейс библиотечного модуля и его реализацию. Некоторые предоставляют непрозрачные типы данных, позволяющие клиентам скрывать детали реализации. В объектно-ориентированных языках программирования, таких как C++, Java и Smalltalk, для этих целей обычно используются классы. Многие известные структуры данных имеют многопоточные версии, позволяющие нескольким вычислительным потокам одновременно обращаться к одному конкретному экземпляру структуры данных.