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

Списки

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

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

Операции
— добавление элемента в списке
— удаление элемента в списке
— поиск элемента в списке

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

Операции
— push добавление элемента
— pop удаление элемента
— pip отображение содержимого стека

— удалить элемент можно только после того, как были убраны все ранее добавленные элементы

Операции
— enqueue добавлять элементы в конец очереди
— dequeue удалять первый элемент

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

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

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

Свойства
— каждое дерево имеет корневой узел (вверху)
— корневой узел имеет ноль или более дочерних узлов
— каждый дочерний узел имеет ноль или более дочерних узлов, и так далее

двоичное дерево поиска
дополнительные свойства
— каждый узел имеет до двух дочерних узлов (потомков)
— каждый узел меньше своих потомков справа, а его потомки слева меньше его самого.

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

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

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

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

граф изображают в одном из двух видов

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

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

— алгоритмы обхода, специальные для просмотра рёбер и вершин в графах
особенности
с их помощью можно определить, насколько близко к корневому узлу находятся те или иные вершины графа

основные типы поиска
— breadth-first поиск в ширину
— depth-first search глубину