Меню
ГлавнаяExcel

Структурирование данных. Понятие базы и банка данных. Классификация баз данных. Виды моделей данных: иерархическая, сетевая, реляционная. Типы и структуры данных

Какие виды структур данных бывают?(можете указать название структуры в определенном языке программирования) Хочется узнать их предназначение, сильные и слабые стороны. Так же интересует классификация, верно ли в вики написано? Список структур данных Развернутый ответ пока каждой структуре не нужен, просто кратко, для примера рассказать в чем преимущество этой структуры перед остальными(например самое быстрое время доступа к элементу, способность динамически менять объем памяти и т.д.) Может на всё сразу не стоит отвечать, вдруг объем ответа будет значительным, хотя бы по одной из структур которую хорошо знаете можете отписаться, а я буду добавлять в основной пост информацию. Очень удобно будет иметь перед глазами такой список, сразу по нему сверился и выбрал нужное.

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

1.1 Список Может всё то же самое, что и массив, но позволяет добавлять элементы в любое место, удалять элементы из любого места и получать текущее количество элементов.

1.2 Ассоциативный массив

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

преимущества:

  • Важное свойство хеш-таблиц состоит в том, что, при некоторых разумных допущениях, все три операции (поиск, вставка, удаление элементов) в среднем выполняются за время O(1), время для наихудшего случая - O(n).

недостатки:

  • Итерация не в порядке возрастания ключей
  • Необходимость «перехеширования» при увеличении числа хранимых объектов (?)
  • нельзя реализовать быстро работающие дополнительные операции MIN, MAX и алгоритм обхода всех хранимых пар в порядке возрастания или убывания ключей (?)
  • не поддерживает упорядоченности, и не сохраняет порядок следования элементов (?)
  • возможность коллизий

общий вид описания структур:

Основное предназначение, описание

Поддерживаемые операции

Преимущества

Недостатки

Готовая реализация в языке программирования (название функции или класса)

условные обозначения

(?) - под сомнением, поправьте пожалуйста если вдруг неправильно написано или наоборот утвердите чтобы исключить неоднозначность.

редактирование продолжается..

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

Классификация структур данных

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

  • Линейные
    • Массив
    • Список
    • Связанный список
    • Очередь
    • Хэш-таблица
  • Иерархические
    • Двоичные деревья
    • N-арные деревья
    • Иерархический список
  • Сетевые
    • Простой граф
    • Ориентированный граф
  • Табличные
    • Таблица реляционной базы данных
    • Двумерный массив
  • Другие

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

    Линейные структуры данных

    Элемент линейной структуры данных характеризуется порядковым номером или индексом в линейной последовательности элементов.

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

    Линейный массив.
    Адрес(элемент(index)) = размер_ячейки * index.

    Список – это динамическая линейная структура данных, в которой каждый элемент ссылается либо только на предыдущий – однонаправленный линейный список , либо на предыдущий и следующий за ним – двунаправленный линейный список . Достоинство этой структуры данных, помимо возможности изменять размер, - это простота реализации. Также, благодаря наличию ссылок, каждый элемент в списке, в отличие от массива, может занимать разный объем памяти. Адрес первого элемента в линейном списке однозначно определяется адресом самого списка.

    Связанный список – это вариант обычного линейного списка, оптимизированный для операций добавления и удаления элементов. Оптимизация заключается в том, что элементы связанного списка не обязаны в памяти располагаться друг за другом. Порядок элементов определяется ссылкой на первый элемент (не обязан быть в самом начале выделенной для списка памяти) и последовательностью ссылок на остальные элементы списка.


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

    Стек – это динамическая линейная структура данных, для которой определены всего две операции изменения набора элементов: добавление элемента в конец и удаление последнего элемента. Еще говорят, что стек реализует принцип LIFO (Last in, First Out) – последним пришел и первым ушел. Например, в ходе выполнения программного кода, вычислительная машина при необходимости вызвать процедуру или функцию сначала заносит указатель на место ее вызова в стек, чтобы при завершении выполнения ее кода корректно вернуться к следующей после точки вызова инструкции. Такая структура данных называется стеком вызовов подпрограмм.

    Стек.

    Очередь – очень похожая не стек, динамическая структура данных, с той лишь разницей, что она реализует принцип FIFO (First in, First out) – первым пришел и первым ушел. За примерами в реальной жизни, как понятно из названия, далеко ходить не надо. В программировании с помощью очередей, например, обрабатывают события пользовательского интерфейса, обращения клиентов к и прочие информационные запросы.

    Очередь.

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

    Иерархические структуры данных

    Элемент в иерархической структуре данных характеризуется ссылкой на вышестоящий в иерархии элемент (или ссылками на нижестоящие элементы) и (необязательно) порядковым номером в линейной последовательности своего уровня (иерархические списки).

    Деревья – динамическая иерархическая структура данных, представленная единственным корневым узлом и его потомками. Максимальное количество потомков каждого узла и определяет размерность дерева . Отдельно выделяют двоичные или бинарные деревья , поскольку они используются в алгоритмах сортировки и поиска: каждый узел двоичного дерева поиска соответствует элементу из некоторого отсортированного набора, все его “левые” потомки – меньшим элементам, а все его “правые” потомки – большим элементам. Каждый узел в дереве однозначно идентифицируется последовательностью неповторяющихся узлов от корня и до него – путем. Длина пути и является уровнем узла в иерархии дерева. Для двоичных или бинарных деревьев выделяют следующие виды рекурсивного обхода всех его элементов (в фигурных скобках указан порядок посещения элементов каждого узла, начиная с корня):

    • прямой или префиксный
      {узел, левое поддерево, правое поддерево};

    • обратный или постфиксный
      {левое поддерево, правое поддерево, узел};

    • симметричный или инфиксный
      {левое поддерево, узел, правое поддерево};

    Чтобы вывести элементы в порядке их возрастания, дерево поиска следует обойти в симметричном порядке. Чтобы элементы оказались в обратном порядке, в процессе обхода необходимо поменять порядок посещения поддеревьев.


    Двоичное (бинарное) дерево.

    Иерархический список – симбиоз линейного списка и дерева. Каждый элемент списка может быть также началом списка следующего подуровня иерархии. Пример иерархического списка – структура интернет форумов: последовательность сообщений образует линейный список, в то время как сообщения, являющиеся ответами на другие сообщения, порождают новые потоки обсуждения.


    Иерархический список.

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

    Элемент в сетевой структуре данных характеризуется набором связей с другими - соседними элементами. В таких структурах данных ни начальный, ни корневой элементы явно не выделены.

    Граф – динамическая сетевая структура данных, представленная набором вершин и ребер – связей между вершинами. Каждая вершина может быть связана с любым числом других вершин или с самой собой. Здесь уже нет никакой четкой иерархии. Если рассматривать узлы дерева, как вершины графа, а связи между узлами дерева разных уровней иерархии, как ребра графа, то само дерево можно считать графом, не содержащим циклов или ациклическим графом. Если для каждого ребра графа определено направление, то это ориентированный граф. Помимо направления каждое ребро графа может иметь свой вес. С помощью графа, например, моделируются транспортные сети и решаются задачи на оптимизацию транспортных потоков. Загруженность или, наоборот, пропускная способность транспортных магистралей задается весом соответствующих ребер.


    Граф.
    Ориентированный граф.

    Элемент в табличной структуре данных характеризуется двумерным индексом: индексом строки и индексом столбца, на пересечении которых он находится. Примерами табличных структур данных являются и таблицы .


    Оценка сложности алгоритмов

    Под оценкой сложности алгоритмов подразумевают не интеллектуальные усилия, которые затратили авторы при их разработке, а зависимость количества элементарных операций, выполняемых вычислительной машиной от объема обрабатываемой информации. Например, как будет зависеть число сравнений двух чисел от длины исходной последовательности в процессе работы алгоритма сортировки. Я намеренно немного сузил определение, поскольку в дальнейшем речь будет идти только о количестве элементарных операций. На самом деле сложность алгоритма определяется не только количеством операций, но и объемом привлеченных для решения задачи вычислительных ресурсов, и в первую очередь, оперативной памяти. Чем проще алгоритм, тем он, скорее всего, дольше работает. Сложные и быстрые алгоритмы зачастую используют вспомогательные структуры данных, и, как следствие, расходуют дополнительную память. Закон сохранения энергии или “за все надо платить”. Один из примеров “предельной оптимизации” был рассмотрен ранее – это хэш-таблица. Я лично не знаю, как устроена хэш-таблица и как выглядят хэш-функции (догадываюсь, что не просто), но зато время поиска элементов по ключу практически не зависит от размера таблицы. Далее немного теории.

    Оценку сложности алгоритмов проводят с использованием аппарата математического асимптотического анализа и выведения асимптотической оценки сложности.

    Асимптотическая оценка сложности обозначается греческой буквой Θ (тета).

    f(n) = Θ(g(n)), если существуют c1, c2>0 и n0 такие, что c1*g(n)n0.

    Функция g(n) является асимптотически точной оценкой сложности алгоритма - функции f(n), приведенное неравенство называется асимптотическим равенством, а само обозначение Θ символизирует множество функций, которые растут “так же быстро”, как и функция g(n) – т.е. с точностью до умножения на константу. Как следует из приведенного неравенства, оценка Θ являет собой одновременно и верхнюю и нижнюю оценки сложности. Не всегда есть возможность получить оценку в таком виде, поэтому верхнюю и нижнюю оценки иногда определяют отдельно.

    Верхняя оценка сложности обозначается греческой буквой Ο (омикрон), и является множеством функций, которые растут не быстрее, чем g(n).

    f(n)= Ο(g(n)), если существует c>0 и n0 такие, что 0n0.

    Нижняя оценка сложности обозначается греческой буквой Ω (омега), и является множеством функций, которые растут не медленнее, чем g(n).

    f(n)= Ω(g(n)), если существует c>0 и n0 такие, что 0n0.

    Как следствие: асимптотическая оценка существует только в том случае, если совпадают нижняя и верхняя оценки сложности алгоритма. В практике анализа алгоритмов чаще всего под оценкой сложности понимают верхнюю оценку сложности. Это вполне логично, поскольку наиболее важна оценка времени, за которое алгоритм гарантировано закончит работу, а не время, в пределах которого он точно не завершится.

    Работа с линейными структурами данных

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

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

    Абстрактная структура данных описывает признаки и свойства объекта, взаимосвязь между элементами объекта, а также возможные операции над данным объектом или классом объектов.

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

    · целые числа;

    · вещественные числа;

    · символы;

    · логические значения.

    Для компьютерной обработки этих объектов в языках программирования существуют соответствующие типы данных (см. “Типы данных ”). Базовые объекты можно объединять в более сложные структуры, добавляя операции уже над структурой в целом и правила доступа к отдельным элементам этой абстрактной структуры данных.

    К таким абстрактным структурам данных относятся:

    · векторы (конечные массивы);

    · таблицы (матрицы), а в общем случае - многомерные массивы;

    · динамические структуры:

    Последовательности символов, чисел;

    Очереди;

    Деревья;

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

    Заметим, что перечисленные структуры существуют независимо от их реализации при программировании. С этими структурами данных работали и в XVIII, и в XIX веках, когда еще не придумали вычислительную машину. Мы можем разрабатывать алгоритм в терминах абстрактной структуры данных, но для реализации алгоритма в конкретном языке программирования необходимо найти способ ее представления в терминах типов данных и операторов , поддерживаемых данным языком программирования (см. “Операторы языка программирования ”). Для компьютерного представления абстрактных структур используются структуры данных ,которые представляют собой набор переменных, возможно различных типов данных, объединенных определенным образом. Для конструирования таких структур, как вектор, таблица, строка, последовательность, в большинстве языков программирования присутствуют стандартные типы данных : одномерный массив, двухмерный массив, строка, файл (реже список) соответственно. Организацию остальных структур данных, в первую очередь динамических структур , размер которых меняется во время выполнения программы, программисту приходится осуществлять самостоятельно, используя базовые типы данных. Рассмотрим такие структуры подробнее.

    Списки

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

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

    Пример 1. Порядок следования записей фамилий читателей в компьютере библиотекаря определяет отношение “предыдущий–следующий”. Как правило, сами записи имеют дополнительное свойство - они упорядочены по алфавиту. Над этим списком реализованы операции добавления нового читателя и, при необходимости, удаления старого. Если к тому же ведутся записи выданных каждому читателю книг, то каждую такую запись удобно представлять опять же с помощью списка выданных книг.

    Кольцевые списки - такая же структура, как и линейный список, но имеющая дополнительную связь между последним и первым элементом, то есть следующим за последним элементом является первый элемент.

    В кольцевом списке в отличие от линейного все элементы равноправны (поскольку для каждого элемента определены и предыдущий, и следующий элементы). Выделение “первого” и “последнего” элементов в кольцевом списке весьма условно, так как собственно структура списка не имеет явно выделенных элементов !

    Пример 2. Во многих играх дети используют считалочки, чтобы выбрать ведущего, разделиться на команды и т.п. Как правило, считалочки длинные, и дети (сами того не зная) организуют кольцевой список. Отношение “предыдущий–следующий” определяется тем, в какую сторону ведущий считает. Типичная операция в такой структуре - удаление элемента из списка с сохранением его кольцевой структуры.

    Линейные списки, в которых операции вставки, удаления и доступа к значениями элементов выполняются только с крайними элементами (первым или последним), получили специальные названия.

    Стек - частный случай линейного односвязного списка, для которого определены две операции: добавление элемента в вершину стека (перед первым элементом) и удаление элемента из вершины стека (удаление первого элемента).

    Пример 3. Рассмотрим задачу определения сбалансированности скобок различных видов в арифметическом выражении. Например, требуется проанализировать, сбалансированы ли скобки в выражении, содержащем круглые и квадратные скобки: ? Для решения этой задачи будем использовать динамическую структуру данных стек . Приведем алгоритм решения этой задачи по шагам. Будем использовать следующие обозначения:

    i - номер анализируемого символа;

    n - количество символов в выражении.

    1. i = 0.

    2. i = i + 1.

    3. Если i n , то переход на п. (4), иначе если стек пуст, то выдаем сообщение “скобки сбалансированы”, в противном случае выдаем сообщение “скобки не сбалансированы ”. Конец алгоритма.

    4. Если i -й символ отличен от символов скобок, то переход на п. (2).

    5. Если i -й символ равен “(” или “[”, то помещаем его в стек, переход на п. (2).

    6. Если i -й символ равен “)”, то проверяем вершину стека: если в вершине стека находится “(”, то извлекаем ее из стека; переход на п. (2), иначе выдаем сообщение “скобки не сбалансированы ”. Конец алгоритма.

    7. Если i -й символ равен “]”, то проверяем вершину стека: если в вершине стека находится “[”, то извлекаем ее из стека; переход на п. (2), иначе выдаем сообщение “скобки не сбалансированы ”. Конец алгоритма.

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

    Понятие очереди действительно очень близко к бытовому термину “очередь”. Очередь покупателей в магазине хорошо описывается в терминах этой структуры данных.

    Деревья

    Дерево - это совокупность элементов, называемых узлами , в которой выделен один элемент (корень ), а остальные элементы разбиты на непересекающиеся множества (поддеревья), каждое из которых является деревом, при этом корень каждого поддерева является потомком корня дерева, т.е. все элементы связаны между собой отношением (предок–потомок). В результате образуется иерархическая структура узлов. Узлы, которые не имеют ни одного потомка, называются листьями . Над деревом определены следующие операции: добавление элемента в дерево, удаление элемента из дерева, обход дерева, поиск элемента в дереве.

    Пример 4. Дерево является наиболее удобной структурой данных для представления генеалогического дерева, с помощью которого можно решать задачи определения степени родства между двумя людьми.

    Используются деревья и для определения выигрышной стратегии в играх (см. статью “Игры. Выигрышные стратегии ”), и для построения различных информационных моделей (см. “Информационные модели ”).

    Особенно важную роль в информатике играют так называемые бинарные деревья .

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

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

    Графы

    Граф - это множество элементов, называемых вершинами графа вместе с набором отношений между этими вершинами, называемых ребрами графа. Графической интерпретацией этой структуры данных является множество точек, соответствующих вершинам, некоторые пары из которых соединены линиями или стрелками, которые соответствуют ребрам. В последнем случае граф называется ориентированным (см. также статьи “Графические модели ” и “Табличные модели ”).

    В силу того, что с помощью графов можно описывать объекты произвольной структуры, графы являются основным средством для описания структур сложных объектов и функционирования систем. Например, для описания вычислительной сети, транспортной системы, иерархической структуры (дерево является одной из разновидностей графа). Блок-схемы алгоритмов (см. “Способы записи алгоритмов ”) также представляют собой графы.

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

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

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

    Абстрактную структуру данных - граф - в программе можно представить несколькими способами, т.е. используя разные типы данных. Например, граф можно описывать с помощью списка ребер, задавая каждое ребро парой вершин и, при необходимости, весом. Наибольшее распространение получило табличное хранение графа (см. “Табличные модели ”), называемое также матрицей смежности , т.е. двухмерного массива, скажем, A , где для невзвешенного графа (или 1), если ребро между вершинами i и j существует, и (или 0) в противном случае. Для взвешенного графа A [i ][j ] равно весу соответствующего ребра, а отсутствие ребра в ряде задач удобно обозначать бесконечностью. Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали (i = j ). C помощью матрицы смежности легко проверить, существует ли в графе ребро, соединяющее вершину i с вершиной j . Основной же ее недостаток заключается в том, что матрица смежности требует, чтобы объем памяти был достаточен для хранения N 2 значений для графа, содержащего N вершин, даже если ребер в графе существенно меньше, чем N 2 .

    При объяснении понятия структуры данных можно воспользоваться следующей иллюстрацией.

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

    Государственный образовательный стандарт предусматривает изучение различных структур данных как в базовом курсе основной школы, так и в старших классах. В курсе программирования основной школы в Примерной программе упоминаются в качестве обрабатываемых объектов цепочки символов (строки), числа, списки, деревья, графы. Однако в практических работах из данных сложной структуры упоминается только массив (см. статью “Операции с массивами ”). В основной школе остальные структуры, видимо, имеет смысл изучать в первую очередь при построении графических и других моделей (см. раздел IV энциклопедии).

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

    Бинарное дерево также легко представить в памяти компьютера с помощью одномерного массива, при этом в первом элементе массива будет храниться корень дерева, а потомки узла дерева, хранящегося в i -м элементе массива, будут располагаться в 2i -м и (2i + 1)-м элементах соответственно. Если потомок у узла отсутствует, то соответствующий элемент будет равен, например, 0. Рекурсивная процедура обхода дерева t и печати его элементов в этом случае будет выглядеть так:

    procedure order(i:integer);

    if t[i] <> 0 then

    О реализации списков и массивов с помощью динамических переменных можно прочитать, например, в классической книге Н.Вирта “Алгоритмы и структуры данных”.

    В программу для профильной школы включены и алгоритмы на графах. В частности, упоминается поиск кратчайшего пути в графе. Для невзвешенного графа решать эту задачу можно, например, с использованием алгоритма “поиска в ширину”, когда сначала помечаются вершины графа, соединенные ребром с исходной вершиной, затем все вершины, соединенные с помеченными, и т.д. Для взвешенного графа чаще всего используют алгоритм Дийкстры (см., например, статью Е.В. Андреевой “Олимпиады по информатике. Пути к вершине”, “Информатика” № 8/2002). Знание таких алгоритмов необходимо для успешного решения олимпиадных задач по информатике. Так, на IV федеральном окружном этапе Всероссийской олимпиады по информатике 2007 г. предлагалась задача “Окопы и траншеи”, решение которой как раз и сводилось к поиску кратчайшего пути во взвешенном графе.

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

    Что включает в себя понятие структуры данных?

    Этот термин может иметь несколько близких, но все же отличительных значений. Это:

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

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

    Что формирует структуру?

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

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

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

    Стоит отметить, что многие языки программирования обладают установленным типом модульности, что позволяет структурам с данными безопасно использоваться в различных приложениях. Яркими примерами являются языки Java, C# и C++. Сейчас классическая структура используемых данных представлена в стандартных библиотеках языков программирования или непосредственно она встроена уже в сам язык. К примеру, хэш-таблицы встроена в Lua, Python, Perl, Ruby, Tcl и другие. Широко применяется стандартная библиотека шаблонов в C++.

    Сравниваем структуру в функциональном и императивном программировании

    Стоит сразу оговорится, что проектировать структуры для функциональных языков сложнее, чем для императивных, как минимум на это есть две причины:

    1. Фактически все структуры часто применяют на практике присваивание, которое в чисто функциональном стиле не используется.
    2. Функциональные структуры - это гибкие системы. В императивном программировании старые версии просто заменяются на новые, а в функциональном все работает, как работало. Иными словами, в императивном программировании структуры являются эфемерными, а в функциональном они постоянные.

    Что включает в себя структура?

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

    Простейший массив подходит для частого обращения к установленным компонентам по индексам и их изменению, а удаление элементов из средины функционирует за принципом O(N)O(N). Если вам требуется удалить элементы, чтобы разрешить определенные задачи, то придется воспользоваться иной структурой. К примеру, бинарное дерево (std::set) позволяет делать это по O(logN)O(log⁡N), однако оно не поддерживает работу с индексами, выполняется исключительно поочередный обход элементов и их поиск по значению. Таким образом, можно сказать, что структура отличается операциями, что она способна выполнять, а также скоростью их проделывания. Для примера стоит рассмотреть простейшие структуры, что не дают выгоды в эффективности, но имеют точно установленный набор поддерживаемых операций.

    Стек

    Это один из типов структур данных, представленный в виде ограниченного простейшего массива. Классический стек поддерживает всего лишь три опции:

    • Внести элемент в стек (Сложность: O(1)O(1)).
    • Извлечение элемента из стека (Сложность: O(1)O(1)).
    • Проверка, пустой ли стек или нет (Сложность: O(1)O(1)).

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

    Очередь

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

    Дек

    Это еще один вид структуры данных, который еще называют очередью с двумя концами. Опция поддерживает следующий набор операций:

    • Внести элемент в начало (Сложность: O(1)O(1)).
    • Извлечь компонент из начала (Сложность: O(1)O(1)).
    • Внесение элемента в конец (Сложность: O(1)O(1)).
    • Извлечение элемента из конца (Сложность: O(1)O(1)).
    • Проверка, пустой ли дек (Сложность: O(1)O(1)).

    Списки

    Данная структура данных определяет последовательность линейно связанных компонентов, для которых разрешены операции добавления компонентов в любое место списка и его удаление. Линейный список задается указателем на начало списка. Типичные операции над списками: обход, поиск конкретного компонента, вставка элемента, удаление компонента, объединение двух списков в единое целое, разбивка списка на пару и так далее. Стоит оговориться, что в линейном списке, помимо первого, имеется предыдущий компонент для каждого элемента, не включая последний. Это означает, что компоненты списка находятся в упорядоченном состоянии. Да, обработка такого списка не всегда удобна, ведь нет возможности продвижения в противоположную сторону — от конца списка к началу. Однако в линейном списке можно поэтапно пройтись по всем составляющим.

    Еще существуют кольцевые списки. Это такая же структура, что и линейный список, однако она имеет дополнительную связь между первым и последним компонентами. Другими словами, следующим за последним элементом является первый компонент.

    В этом списке элементы равноправны. Выделение первого и последнего - это условность.

    Деревья

    Это совокупность компонентов, что именуются узлами, в котором есть главный (один) компонент в виде корня, а все остальные разбиты на множество непересекающихся элементов. Каждое множество является деревом, а корень каждого древа - потомком корня дерева. Другими словами, все компоненты соединены между собой отношениями предок-потомок. Как результат можно наблюдать иерархическую структуру узлов. Если узлы не имеют потомка, то они называются листьями. Над деревом определены такие операции, как: добавление компонента и его удаление, обход, поиск компонента. Особую роль в информатике играют бинарные деревья. Что это такое? Это частный случай дерева, где каждый узел может иметь не больше пары потомков, являющихся корнями левого и правого поддерева. Если дополнительно для узлов дерева выполняется еще условие, что все значения компонентов левого поддерева меньше значений корня, а значения компонентов правого поддерева больше корня, то такое дерево именуется деревом бинарного поиска, и предназначается оно для быстрого нахождения элементов. Как же работает алгоритм поиска в таком случае? Искомое значение сравнивается со значением корня, и в зависимости от результата поиск либо завершается, либо продолжается, но исключительно в левом или правом поддереве. Общее число операций сравнения не станет превосходить высоту дерева (это наибольшее число компонентов на пути от корня до одного из листьев).

    Графы

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

    Графами можно описывать объекты какой угодно структуры, они являются главным средством для описания сложных структур и функционирования всех систем.

    Детальней об абстрактной структуре

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

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

    Анализ структур данных производится следующими объектами:

    • Целые и вещественные числа.
    • Логические значения.
    • Символы.

    Для обработки на компьютере всех элементов существуют соответствующие алгоритмы и структуры данных. Типичные объекты можно объединить в сложные структуры. Можно добавить операции над ними, правила к определенным компонентам этой структуры.

    Структура организации данных включает в себя:

    Если все элементы выбраны удачно, то это будет залогом формирования эффективных алгоритмов и структур данных. Если применять на практике аналогию структур и реальных объектов, то можно эффективно разрешать существующие задачи.

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

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

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

    Кому это необходимо знать?

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

    Не забывайте: если говорите о той или иной структуре, то имейте в виду ее логическое представление, ведь физическое представление полностью сокрыто от «внешнего наблюдателя».

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

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

    • Перевод

    Екатерина Малахова, редактор-фрилансер, специально для блога Нетологии адаптировала статью Beau Carnes об основных типах структур данных.

    «Плохие программисты думают о коде. Хорошие программисты думают о структурах данных и их взаимосвязях», - Линус Торвальдс, создатель Linux.

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

    В этой статье я покажу вам 10 самых распространенных структур данных. Для каждой из них приведены видео и примеры их реализации на JavaScript. Чтобы вы смогли попрактиковаться, я также добавил несколько упражнений из бета-версии новой учебной программы freeCodeCamp.

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

    Связные списки

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

    Так устроен связный список

    Связный список состоит из группы узлов, которые вместе образуют последовательность. Каждый узел содержит две вещи: фактические данные, которые в нем хранятся (это могут быть данные любого типа) и указатель (или ссылку) на следующий узел в последовательности. Также существуют двусвязные списки: в них у каждого узла есть указатель и на следующий, и на предыдущий элемент в списке.

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

    Временная сложность связного списка ╔═══════════╦═════════════════╦═══════════════╗ ║ Алгоритм ║Среднее значение ║ Худший случай ║ ╠═══════════╬═════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(1) ║ ║ Delete ║ O(1) ║ O(1) ║ ╚═══════════╩═════════════════╩═══════════════╝

    Упражнения от freeCodeCamp

    Стеки

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

    Стек организован по принципу LIFO (Last In First Out, «последним пришёл - первым вышел») . Это значит, что последний элемент, который вы добавили в стек, первым выйдет из него.


    Так устроен стек

    В стеках можно выполнять три операции: добавление элемента (push), удаление элемента (pop) и отображение содержимого стека (pip).

    Временная сложность стека ╔═══════════╦═════════════════╦═══════════════╗ ║ Алгоритм ║Среднее значение ║ Худший случай ║ ╠═══════════╬═════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(1) ║ ║ Delete ║ O(1) ║ O(1) ║ ╚═══════════╩═════════════════╩═══════════════╝

    Упражнения от freeCodeCamp

    Очереди

    Эту структуру можно представить как очередь в продуктовом магазине. Первым обслуживают того, кто пришёл в самом начале - всё как в жизни.


    Так устроена очередь

    Очередь устроена по принципу FIFO (First In First Out, «первый пришёл - первый вышел»). Это значит, что удалить элемент можно только после того, как были убраны все ранее добавленные элементы.

    Очередь позволяет выполнять две основных операции: добавлять элементы в конец очереди (enqueue ) и удалять первый элемент (dequeue ).

    Временная сложность очереди ╔═══════════╦═════════════════╦═══════════════╗ ║ Алгоритм ║Среднее значение ║ Худший случай ║ ╠═══════════╬═════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(1) ║ ║ Delete ║ O(1) ║ O(1) ║ ╚═══════════╩═════════════════╩═══════════════╝

    Упражнения от freeCodeCamp

    Множества



    Так выглядит множество

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

    • Объединение комбинирует все элементы из двух разных множеств, превращая их в одно (без дубликатов).
    • Пересечение анализирует два множества и  создает еще одно из тех элементов, которые присутствуют в обоих изначальных множествах.
    • Разность выводит список элементов, которые есть в одном множестве, но отсутствуют в другом.
    • Подмножество выдает булево значение, которое показывает, включает ли одно множество все элементы другого множества.
    Пример реализации на JavaScript

    Упражнения от freeCodeCamp

    Map

    Map - это структура, которая хранит данные в парах ключ/значение, где каждый ключ уникален. Иногда её также называют ассоциативным массивом или словарём. Map часто используют для быстрого поиска данных. Она позволяет делать следующие вещи:
    • добавлять пары в коллекцию;
    • удалять пары из коллекции;
    • изменять существующей пары;
    • искать значение, связанное с определенным ключом.

    Так устроена структура map

    Упражнения от freeCodeCamp

    Хэш-таблицы

    Так работают хэш-таблица и хэш-функция

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

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

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

    Временная сложность хэш-таблицы ╔═══════════╦═════════════════╦═══════════════╗ ║ Алгоритм ║Среднее значение ║ Худший случай ║ ╠═══════════╬═════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(1) ║ O(n) ║ ║ Insert ║ O(1) ║ O(n) ║ ║ Delete ║ O(1) ║ O(n) ║ ╚═══════════╩═════════════════╩═══════════════╝

    Упражнения от freeCodeCamp

    Двоичное дерево поиска


    Двоичное дерево поиска

    Дерево - это структура данных, состоящая из узлов. Ей присущи следующие свойства:

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

    Временная сложность двоичного дерева поиска ╔═══════════╦═════════════════╦══════════════╗ ║ Алгоритм ║Среднее значение ║Худший случай ║ ╠═══════════╬═════════════════╬══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(log n) ║ O(n) ║ ║ Insert ║ O(log n) ║ O(n) ║ ║ Delete ║ O(log n) ║ O(n) ║ ╚═══════════╩═════════════════╩══════════════╝


    Упражнения от freeCodeCamp

    Префиксное дерево

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

    Так устроено префиксное дерево

    Каждый узел в языковом префиксном дереве содержит одну букву слова. Чтобы составить слово, нужно следовать по ветвям дерева, проходя по одной букве за раз. Дерево начинает ветвиться, когда порядок букв отличается от других имеющихся в нем слов или когда слово заканчивается. Каждый узел содержит букву (данные) и булево значение, которое указывает, является ли он последним в слове.

    Посмотрите на иллюстрацию и попробуйте составить слова. Всегда начинайте с корневого узла вверху и спускайтесь вниз. Это дерево содержит следующие слова: ball, bat, doll, do, dork, dorm, send, sense.

    Упражнения от freeCodeCamp

    Двоичная куча

    Двоичная куча - ещё одна древовидная структура данных. В ней у каждого узла не более двух потомков. Также она является совершенным деревом: это значит, что в ней полностью заняты данными все уровни, а последний заполнен слева направо.


    Так устроены минимальная и максимальная кучи

    Двоичная куча может быть минимальной или максимальной. В максимальной куче ключ любого узла всегда больше ключей его потомков или равен им. В минимальной куче всё устроено наоборот: ключ любого узла меньше ключей его потомков или равен им.

    Порядок уровней в двоичной куче важен, в отличие от порядка узлов на одном и том же уровне. На иллюстрации видно, что в минимальной куче на третьем уровне значения идут не по порядку: 10, 6 и 12.


    Временная сложность двоичной кучи ╔═══════════╦══════════════════╦═══════════════╗ ║ Алгоритм ║ Среднее значение ║ Худший случай ║ ╠═══════════╬══════════════════╬═══════════════╣ ║ Space ║ O(n) ║ O(n) ║ ║ Search ║ O(n) ║ O(n) ║ ║ Insert ║ O(1) ║ O(log n) ║ ║ Delete ║ O(log n) ║ O(log n) ║ ║ Peek ║ O(1) ║ O(1) ║ ╚═══════════╩══════════════════╩═══════════════╝

    Упражнения от freeCodeCamp

    Граф

    Графы - это совокупности узлов (вершин) и связей между ними (рёбер). Также их называют сетями.

    Графы делятся на два основных типа: ориентированные и неориентированные. У неориентированных графов рёбра между узлами не имеют какого-либо направления, тогда как у рёбер в ориентированных графах оно есть.

    Чаще всего граф изображают в каком-либо из двух видов: это может быть список смежности или матрица смежности.


    Граф в виде матрицы смежности

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

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

    Существуют специальные алгоритмы для просмотра рёбер и вершин в графах - так называемые алгоритмы обхода. К их основным типам относят поиск в ширину (breadth-first search ) и в глубину (depth-first search ). Как вариант, с их помощью можно определить, насколько близко к корневому узлу находятся те или иные вершины графа. В видео ниже показано, как на JavaScript выполнить поиск в ширину.