Исчерпывающий видеокурс: структуры данных C#
Рассматриваем 10 самых важных и часто встречающихся структур данных. Подробный разбор как теоретической базы, так и практическая реализация на языке программирования C#.
Связный список (linked lists)
На этом уроке вы изучите одну из самых простых и известных динамических структур данных – связный список (linked list).
Стек (stack)
На втором занятии изучение структуры данных под названием стек (stack), которая организовывает доступ к элементам по принципу "последним пришел – первым вышел" (LIFO)
Двусвязный и кольцевой список (linked list)
Автор рассказывает о двусвязном и кольцевом списках. Как и односвязный, двусвязный список предоставляет строго последовательный доступ, но при этом также появляется возможность перемещаться и в обе стороны. А вот в кольцевом замыкающий элемент всегда будет содержать указатель на первый. Подробнее со схемами и практической частью в третьем уроке.
Очередь, Дек (Queue, Deque)
Рассмотрим очередь (queue). Эта структура данных работает по принципу FIFO (First In – First Out) – первым пришел, первым вышел. А также изучим ее разновидность – двустороннюю очередь – дек (deque).
Множество (Set)
На этом занятии мы рассмотрим множество (set). Оно является реализацией одноименного математического объекта. Структуры данных типа множество позволяют хранить ограниченное число значений определённого типа без определённого порядка. Повторение значений, как правило, недопустимо.
Хеш таблица (Hash Table)
Хеш таблица (Hash Table) – это специальная структура данных, которая позволяет хранить информацию в виде пар ключ-значение. Наиболее близко к ней понятие ассоциативного массива. Основное преимущество хеш таблицы – выполнение операций вставки, поиска и удаления за O(1).
Словарь C# (Map или Dictionary)
Это специальная структура данных, которая позволяет хранить информацию в виде пар ключ-значение. Наиболее близко к нему понятие ассоциативного массива и хеш-таблицы. Основное преимущество словаря – выполнение операций вставки, поиска и удаления за O(1). Но в отличие от хеш-таблицы, здесь используется другой способ разрешения коллизий.
Бинарное дерево (binary search tree, BST)
Бинарное дерево, или, как его еще называют, двоичное дерево (binary search tree, BST), – это иерархическая нелинейная структура данных. Каждая вершина имеет не более двух поддеревьев.
Префиксное дерево или бор (trie)
Префиксное дерево, также известное как бор, луч, нагруженное дерево или trie – это структура данных на основе корневого дерева, каждое ребро которого помечено каким-то символом так, что для любого узла все ребра, соединяющие это узел с его сыновьями, помечены разными символами. Таким образом, прокладывая путь от основания до одной из вершин, можно составить слово или целое предложение.
Графы (graph) и алгоритмы обхода
Граф представляет собой набор узлов, соединенных друг с другом в виде сети. Узлы также называются вершинами. Пара (x, y) называется ребром, которое указывает, что вершина x соединена с вершиной y. Ребро может содержать вес/стоимость, показывая, сколько затрат требуется, чтобы пройти от x до y.
Графы делятся на два основных типа: ориентированные и неориентированные. У неориентированных графов рёбра между узлами не имеют какого-либо направления, тогда как у рёбер в ориентированных графах оно есть. Чаще всего граф изображают в каком-либо из двух видов: это может быть список смежности или матрица смежности. Рассмотрим основные алгоритмы обхода графа: обход графа в ширину и обход графа в глубину.