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

Основные структуры данных

Массив

Самый простой тип структуры данных - линейный массив. Также известен как одномерный массив. В массиве хранится несколько значений одного типа (Integer, Floats, String и т.д.). Доступ к элементам внутри массива осуществляется очень быстро. Массив обычно имеет фиксированный размер. После того как размер массива определен в самом начале, может оказаться невозможным увеличить размер массива без создания нового массива большего размера и копирования всех значений в новый массив. В информатике структура данных массива или просто массив - это структура данных, состоящая из набора элементов (значений или переменных), каждый из которых идентифицируется по крайней мере одним индексом массива или ключом. Массив хранится таким образом, что положение каждого элемента может быть вычислено из кортежа его индексов по математической формуле.

Например, массив из 10 целочисленных переменных с индексами от 0 до 9 может храниться в виде 10 слов по адресам памяти 2000, 2004, 2008, 2036, так что элемент с индексом i имеет адрес 2000 + 4 × i.

Поскольку математическая концепция матрицы может быть представлена в виде двумерной сетки, двумерные массивы также иногда называют матрицами. В некоторых случаях для обозначения массива в вычислительной технике используется термин "вектор", хотя более правильным математическим эквивалентом являются кортежи, а не векторы. Массивы часто используются для реализации таблиц, особенно таблиц поиска; слово таблица иногда используется как синоним массива.

Массивы являются одними из самых старых и важных структур данных и используются практически в каждой программе. Они также могут быть использованы для реализации многих других структур данных, таких как списки и строки. Они эффективно используют логику адресации компьютеров. В большинстве современных компьютеров и многих внешних запоминающих устройствах память представляет собой одномерный массив слов, индексами которых являются их адреса. Процессоры, особенно векторные, часто оптимизированы для работы с массивами.

Массивы полезны тем, что индексы элементов могут быть вычислены во время выполнения. Кроме всего прочего, эта возможность позволяет в одном итерационном операторе обрабатывать произвольное количество элементов массива. По этой причине элементы структуры данных массива должны иметь одинаковый размер и использовать одинаковое представление данных. Набор допустимых кортежей индексов и адреса элементов (а значит, и формула адресации элементов) обычно, но не всегда, фиксированы, пока массив используется.

Термин массив часто используется для обозначения типа данных массива, типа данных, предоставляемого большинством языков программирования высокого уровня, который состоит из коллекции значений или переменных, которые могут быть выбраны по одному или нескольким индексам, вычисляемым во время выполнения программы. Типы массивов часто реализуются структурами массивов; однако в некоторых языках они могут быть реализованы хэш-таблицами, связанными списками, деревьями поиска или другими структурами данных.

Связанный список

Связанная структура данных - это набор информации/данных, связанных между собой ссылками. Данные часто называют узлами. Ссылки часто называют ссылками или указателями. В дальнейшем для обозначения этих понятий будут использоваться слова узел и указатель.

В связанных структурах данных указатели только разыменовываются или сравниваются на равенство. Таким образом, связанные структуры данных отличаются от массивов, которые требуют сложения и вычитания указателей.

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

Стек

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

Базовая реализация стека также называется структурой "Last In First Out", однако существуют различные варианты реализации стека.

Существует три основных операции, которые можно выполнять над стеками. К ним относятся:

• вставка ("проталкивание") элемента в стопку
• удаление ("выталкивание") элемента из стека
• отображение содержимого верхнего элемента стека ("подглядывание")

Очередь

Очередь - это абстрактный тип данных или линейная структура данных, в которой первый элемент вставляется с одного конца ("хвост"), а удаление существующего элемента происходит с другого конца ("голова"). Очередь - это структура типа "первый вошел - первый вышел". "First In First Out" означает, что элементы, поставленные в очередь первыми, выходят первыми, а элементы, поставленные последними, выходят последними. Примером очереди может служить очередь из ожидающих людей. Первый человек в очереди идет первым, а последний - последним.

Процесс добавления элемента в очередь называется "включением", а процесс удаления элемента из очереди - "выключением".

График

Граф - это абстрактный тип данных, предназначенный для реализации концепций графов и гиперграфов из математики.

Графовая структура данных состоит из конечного (и, возможно, изменяемого) набора упорядоченных пар, называемых ребрами или дугами, определенных объектов, называемых узлами или вершинами. Как и в математике, считается, что ребро (x,y) указывает или идет от x к y. Узлы могут быть частью структуры графа, а могут быть внешними объектами, представленными целочисленными индексами или ссылками. Структура данных графа может также связывать с каждым ребром некоторое значение ребра, например, символическую метку или числовой атрибут.

Дерево

Дерево - одна из самых мощных продвинутых структур данных. Оно часто встречается в таких передовых дисциплинах, как искусственный интеллект (ИИ) и дизайн. Удивительно, но дерево важно в гораздо более простом применении - ведении эффективного индекса.

При использовании дерева высока вероятность использования индекса. Самый простой тип индекса - это отсортированный список ключевых полей. Дерево обычно имеет определенную структуру. В случае двоичного дерева можно использовать двоичный поиск для нахождения любого элемента без необходимости просматривать каждый элемент.

Тип данных "дерево" является разновидностью графа, что означает, что многие алгоритмы, предназначенные для обхода графа, работают и с деревом, однако алгоритмы могут быть очень похожими и должны иметь выделенный начальный узел, то есть узел, на который не ссылаются другие узлы.

Проблема с простым упорядоченным списком возникает, когда вы начинаете добавлять новые элементы и должны поддерживать сортировку списка - это может быть сделано достаточно эффективно, но требует некоторых модификаций. Кроме того, линейный индекс нелегко использовать совместно, поскольку весь индекс должен быть "заблокирован", когда один пользователь редактирует его, в то время как одна "ветвь" дерева может быть заблокирована, оставляя другие ветви доступными для редактирования другими пользователями (поскольку они не могут быть затронуты).

Хеш-таблица

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

Каждый узел указывает на другой узел.