Самые популярные структуры данных

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

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


Обычно используемые структуры данных
Давайте сначала перечислим наиболее часто используемые структуры данных, а затем рассмотрим их одну за другой:

• Arrays — массивы
• Stacks — стеки
• Queues — очереди
• Linked Lists — связанные списки
• Trees — деревья
• Graphs — графы
• Tries (они, по сути, деревья, но все же хорошо называть их отдельно). — очередности
• Hash Tables — хэш таблицы

Arrays — Массивы
Массив — это самая простая и наиболее широко используемая структура данных. Другие структуры данных, такие как стеки и очереди, являются производными от массивов.
Вот изображение простого массива размера 4, содержащего элементы (1, 2, 3 и 4).



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

Ниже приведены два типа массивов:

• Одномерные массивы (как показано выше) One-dimensional arrays
• Многомерные массивы (массивы внутри массивов) Multi-dimensional arrays

Основные операции над массивами
Вставить (Insert) — вставляет элемент по указанному индексу
Получить (Get) — возвращает элемент по указанному индексу
Удалить (Delete) — удаляет элемент по указанному индексу
Размер (Size) — получить общее количество элементов в массиве

Для самостоятельного изучения:
1. Найти второй минимальный элемент массива.
2. Первые неповторяющиеся целые числа в массиве.
3. Объединить два отсортированных массива.
4. Переставить положительные и отрицательные значения в массиве.

Stacks (Стеки)
Мы все знакомы со знаменитой опцией Undo (Отмена), которая присутствует практически в каждом приложении. Когда-нибудь задумывались, как это работает? Суть механизма в том, что вы сохраняете предыдущие состояния вашей работы (которые ограничены определенным числом) в памяти в таком порядке, что последнее действие появляется первым. Это не может быть сделано только с помощью массивов. Вот где стек и пригодится!

Реальным примером стека может быть стопка книг, расположенных в вертикальном порядке. Чтобы получить книгу, которая находится где-то посередине, вам нужно удалить все книги, помещенные поверх нее. Вот как работает метод LIFO (Last In First Out).
Вот изображение стека, содержащего три элемента данных (1, 2 и 3), где 3 вверху и будет удалено первым:



Основные операции со стеками:
Протолкнуть (Push) — вставляет элемент сверху других.
Вытащить (Pop) — возвращает верхний элемент после удаления из стека.
Пустой? (IsEmpty) — возвращает истина (true), если стек пуст.
Верхний (Top) — возвращает верхний элемент без удаления из стека.

Для самостоятельного изучения:
1. Оцените постфиксное выражение, используя стек.
2. Сортировка значений в стеке.
3. Проверьте сбалансированные скобки в выражении.

Queues (Очереди)
Подобно стеку, очередь — это еще одна линейная структура данных, в которой элементы хранятся последовательно. Единственное существенное различие между стеком и очередью состоит в том, что вместо использования метода LIFO в Queue реализован метод FIFO, который является сокращением от First in First Out.
Прекрасный реальный пример очереди: ряд людей, ожидающих у билетной кассы. Если приходит новый человек, он присоединяется к линии с конца, а не с начала — и человек, стоящий впереди, первым получит билет и, следовательно, покинет линию.
Вот изображение очереди, содержащей четыре элемента данных (1, 2, 3 и 4), где 1 находится вверху и будет удалено первым:



Основные операции с очередью:
Вочередить (Enqueue) — вставляет элемент в конец очереди.
Выочередить (Dequeue) — удаляет элемент из начала очереди.
Пустой? (IsEmpty) — возвращает истина (true), если очередь пуста.
Верхний (Top) — возвращает первый элемент очереди.

Для самостоятельного изучения:
1. Реализация стека с использованием очереди.
2. Обратные первые k элементы очереди.
3. Генерация двоичных чисел от 1 до n с использованием очереди.

Связанный список (Linked List)
Связанный список — это еще одна важная линейная структура данных, которая на первый взгляд может выглядеть аналогично массивам, но отличается распределением памяти, внутренней структурой и тем, как выполняются основные операции вставки и удаления.

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

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

Вот визуальное представление внутренней структуры связанного списка:



Ниже приведены типы связанных списков:

• Односвязный список (однонаправленный)
• Двусвязный список (двунаправленный)

Основные операции над связанным списком
ВставитьВКонец (InsertAtEnd) — вставляет элемент в конец связанного списка.
ВставитьВНачало (InsertAtHead) — вставляет элемент в начало связанного списка.
Удалить (Delete) — удаляет данный элемент из связанного списка.
УдалитьВНачале (DeleteAtHead) — удаляет первый элемент связанного списка.
Search (Поиск) — возвращает найденный элемент из связанного списка.
Пустой? (IsEmpty) — возвращает истина (true), если связанный список пуст.

Для самостоятельного изучения:
1. Перевернуть связанный список (Обратить, реверсировать, отобразить задом наперёд).
2. Определить цикл в связанном списке.
3. Вернуть N-й узел с конца в связанном списке.
4. Удалить дубликаты из связанного списка.

Graphs (Графы)
Графы — это набор узлов, которые связаны друг с другом в форме сети. Узлы также называются вершинами. Пара (x, y) называется ребром, что указывает на то, что вершина x связана с вершиной y. Ребро может содержать вес / стоимость, показывая, сколько затрат требуется для перехода от вершины x к y.



Типы графов:

• Undirected Graph
• Directed Graph

В языках программирования графы представлены двумя формами:

• Смежная (соседняя) матрица (Adjacency Matrix)
• Смежный (соседний) список Adjacency List

Ниже приведен пример смежного списка Adjacency List (ненаправленный граф).



Известные примеры перемещения алгоритмы по графам:

• Breadth First Search
• Depth First Search

Для самостоятельного изучения:
1. Реализация Breadth and Depth First поиска
2. Проверка если граф дерево или нет.
3. Подсчет количества ребер в графе.
4. Найти кратчайший путь между вершинами.

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

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

Вот изображение простого дерева и основные термины, используемые в древовидной структуре данных:



Имеются типы деревьев:

• N-ое дерево
• Сбалансированное дерево (Balanced Tree)
• Бинарное дерево (Binary Tree)
• Бинарное поисковое дерево (Binary Search Tree)
• AVL дерево
• Красно-черное дерево (Red Black Tree)
• 2–3 дерево

Из вышеперечисленного Бинарное дерево и Бинарное поисковое дерево являются наиболее часто используемыми деревьями.

Для самостоятельного изучения:
1. Найти высоту бинарного дерева.
2. Найти k-е максимальное значение в двоичном поисковом дереве.
3. Найти узлы на расстоянии «k» от корня.
4. Найти предков данного узла в двоичном дереве.

Практические примеры:

1. Facebook: Каждый пользователь представляет собой вершину, и два человека являются друзьями, когда имеется ребро между двумя вершинами. Так же и рекомендации в друзья — расчитываются на основаниитеории графов.

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

3. Транспортные сети: в них вершины это пересечения дорог и рёбра — это дорожные сегменты между их пересечениями.

4. Представление молекулярных структур где вершины это молекулы и рёбра — это связи между молекулами.

5. Дискретные сигнальные процессы в графах. (и тут еще хорошая статья ну и заодно вот эта)

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

7. Теория расширение кластера Майера функции летучести газа (Z) в термодинамике требует вычисления двух, трех, четырёх условий и так далее. Существует систематический способ сделать это комбинаторно с диаграммами, и это помогает узнать связность таких диаграмм. Знание теории графов может быть полезным, когда вы хотите суммировать подмножество этих диаграмм.

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

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

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

Для любителей С#, как я, линк с примерами кода построения графов на C# тут. Для самых продвинутых библиотека с реализацией графов на C++ тут. Для фанатов AI и Skynet топать сюда.

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

Вот иллюстрация того, как три слова «top», «thus», и «their» хранятся в Очередности:



Слова хранятся сверху вниз, где зеленые узлы “p”, “s” и “r” указывают на конец “top”, “thus”, и “their” соответственно.

Для самостоятельного изучения:
1. Подсчитать общее количество слов в Очередности.
2. Распечатать все слова, хранящиеся в Очередности.
3. Сортировка элементов массива с использованием Очередности.
4. Формируйте слова из словаря, используя Очередности.
5. Создайте словарь T9.

Практические примеры использования:
1. Выбор из словаря или завершение при наборе слова.
2. Поиск в контактах в телефоне или телефонном словаре.

Hash Table (Хеш-таблица)
Хеширование — это процесс, используемый для уникальной идентификации объектов и сохранения каждого объекта по некоторому предварительно рассчитанному уникальному индексу, называемому его «ключом». Таким образом, объект хранится в форме пары «ключ-значение», а коллекция таких элементов называется «словарь». Каждый объект может быть найден с помощью этого ключа.

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

Хеш-таблицы обычно реализуются с использованием массивов.

Производительность хеширования структуры данных зависит от этих трех факторов:

• Хэш-функция
• Размер хеш-таблицы
• Метод обработки столкновений

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



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

Ниже приведен пример кода использования хэш-таблицы в .Net

static void Main(string[] args)
        {
            Hashtable ht = new Hashtable
            {
                { "001", "Zara Ali" },
                { "002", "Abida Rehman" },
                { "003", "Joe Holzner" },
                { "004", "Mausam Benazir Nur" },
                { "005", "M. Amlan" },
                { "006", "M. Arif" },
                { "007", "Ritesh Saikia" }
            };

            if (ht.ContainsValue("Nuha Ali"))
            {
                Console.WriteLine("Эта персона уже в списке!");
            }
            else
            {
                ht.Add("008", "Nuha Ali");
            }

            // Получить коллекцию ключей.
            ICollection key = ht.Keys;

            foreach (string k in key)
            {
                Console.WriteLine(k + ": " + ht[k]);
            }
            Console.ReadKey();
        }

Практические примеры:

1. Игра «Жизнь». В ней хэш — это набор координат каждой живой клетки.

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

3. При имплементации структуры/алгоритма многонаправленного дерева (multiway tree) хэштаблицы могут использоваться для быстрого доступа к любому дочернему элементу внутреннего узла.

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

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