Вопрос, который нельзя не задать — Структуры данных
Данный ответ это просто текст. Не нужно понимать, не нужно бояться. Нужно запомнить. Ты справишься^_^
Структура данных — это контейнер, который хранит данные в определенном макете. Этот «макет» позволяет структуре данных быть эффективной в некоторых операциях и неэффективной в других.
Массивы: Массив — это простейшая и наиболее распространенная структура данных. Другие структуры данных, например, стеки и очереди, производны от массивов. Каждому элементу данных присваивается положительное числовое значение, именуемое индексом и соответствующее положению этого элемента в массиве. В большинстве языков программирования элементы в массиве нумеруются с 0. Существуют массивы двух типов: Одномерные (такие, как показанный выше) и Многомерные (массивы, в которые вложены другие массивы).
Простейшие операции с массивами:
Insert — вставляем элемент на позицию с заданным индексом
Get — возвращаем элемент, занимающий позицию с заданным индексом
Delete — удаляем элемент с заданным индексом
Size — Получаем общее количество элементов в массиве
Стеки: Стек можно сравнить с высокой стопкой книг. Если вам нужна какая-то книга, лежащая около центра стопки, вам сначала придется снять все книги, лежащие выше. Именно так работает принцип LIFO (Последним пришел — первым вышел).
Простейшие операции со стеком:
Push — Вставляет элемент в стек сверху
Pop — Возвращает верхний элемент после того, как удалит его из стека
isEmpty — Возвращает true, если стек пуст
Top — Возвращает верхний элемент, не удаляя его из стека
Очереди: Очередь, как и стек — это структура данных, элементы в которой хранятся в последовательном порядке. Единственное существенное отличие между стеком и очередью заключается в том, что в очереди вместо LIFO действует принцип FIFO (Первым пришел — первым вышел).
Простейшие операции с очередью:
Enqueue() — Добавляет элемент в конец очереди
Dequeue() — Удаляет элемент из начала очереди
isEmpty() — Возвращает true, если очередь пуста
Top() — Возвращает первый элемент в очереди
Связанные списки: Связанный список — массив где каждый элемент является отдельным объектом и состоит из двух элементов — данных и ссылки на следующий узел.Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.
Однонаправленные, каждый узел хранит адрес или ссылку на следующий узел в списке и последний узел имеет следующий адрес или ссылку как NULL.
1->2->3->4->NULL
Двунаправленные, две ссылки, связанные с каждым узлом, одним из опорных пунктов на следующий узел и один к предыдущему узлу.
NULL<-1<->2<->3->NULL
Круговые, все узлы соединяются, образуя круг. В конце нет NULL. Циклический связанный список может быть одно-или двукратным циклическим связанным списком.
1->2->3->1
Основные операции:
InsertAtEnd — Вставка заданного элемента в конец списка
InsertAtHead — Вставка элемента в начало списка
Delete — удаляет заданный элемент из списка
DeleteAtHead — удаляет первый элемент списка
Search — возвращает заданный элемент из списка
isEmpty — возвращает True, если связанный список пуст
Графы: Граф — это множество узлов, соединенных друг с другом в виде сети. Узлы также называются вершинами. Пара (x,y) называется ребром, это означает, что вершина x соединена с вершиной y. Ребро может иметь вес/стоимость — показатель, характеризующий, насколько затратен переход от вершины x к вершине y. Бывают Ориентированными, ребра являются направленными, т.е. существует только одно доступное направление между двумя связными вершинами и Неориентированные, к каждому из ребер можно осуществлять переход в обоих направлениях.
В языках программирования графы могут быть представлены двумя способами:
Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.
Список смежности — способов представления графа в виде коллекции списков вершин. Каждой вершине графа соответствует список, состоящий из “соседей” этой вершины.
Распространенные алгоритмы обхода графа:
Поиск в ширину — пусть мы начали обход в ширину из какой-то вершины V. В следующий момент времени мы будем просматривать соседей вершины V (соседом вершины V назовем вершины, имеющий общее ребро с V). И так до тех пор, пока все вершины в графе не будут просмотрены.
Поиск в глубину — Идея заключается в том, что мы двигаемся от начальной вершины (точки, места) в определенном направлении (по определенному пути) до тех пор, пока не достигнем конца пути или пункта назначения (искомой вершины). Если мы достигли конца пути, но он не является пунктом назначения, то мы возвращаемся назад (к точке разветвления или расхождения путей) и идем по другому маршруту.
Деревья: Дерево — это иерархическая структура данных, состоящая из вершин (узлов) и ребер, которые их соединяют. Деревья подобны графам, однако, ключевое отличие дерева от графа таково: в дереве не бывает циклов.
Типы деревьев:
Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны NULL) называются листьями.
Бинарное дерево поиска — это бинарное дерево, обладающее дополнительными свойствами: значение левого потомка меньше значения родителя, а значение правого потомка больше значения родителя для каждого узла дерева.
Сбалансированное бинарное дерево поиска — это бинарное дерево поиска с логарифмической высотой. В сбалансированном бинарном дереве поиска операции поиска, вставки и удаления выполняются за логарифмическое время (так как путь к любому листу от корня не более логарифма).
АВЛ-дерево — сбалансированное по высоте бинарное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
Красно-черное дерево — бинарное дерево поиска, в котором каждый узел имеет атрибут цвета. При этом:
- Узел может быть либо красным, либо черным и имеет двух потомков;
- Корень — как правило чёрный. Это правило слабо влияет на работоспособность модели, так как цвет корня всегда можно изменить с красного на чёрный;
- Все листья — черные и не содержат данных.
- Оба потомка каждого красного узла — черные.
- Любой простой путь от узла-предка до листового узла-потомка содержит одинаковое число черных узлов.
N-арное дерево — Если дерево является корневым деревом, в котором каждый узел имеет не более N дочерних элементов, оно называется N-арным деревом.
Дерево 2–3–4 (также называемое деревом 2–4) — это самобалансирующаяся структура данных, которая обычно используется для реализации словарей. Числа означают дерево, в котором каждый узел с дочерними элементами (внутренний узел) имеет два, три, или четыре дочерних узла:
2-узел имеет один элемент данных, а если внутренний имеет два дочерних узла;
3-узел имеет два элемента данных, а если внутренний имеет три дочерних узла;
4-узел имеет три элемента данных, а если внутренний имеет четыре дочерних узла;
Префиксные деревья — Префиксным деревом называется корневое дерево, в котором каждая связь помечена некоторой буквой и каждому узлу соответствует слово, получаемое чтением пометок при прохождении в него из корня.
Корневое дерево — это дерево со счетным числом узлов, в котором определенный узел отличается от других и называется корневым узлом.
Хэш таблицы: Хэширование — это процесс, используемый для уникальной идентификации объектов и хранения каждого объекта в заранее рассчитанном уникальном индексе (ключе). Объект хранится в виде пары «ключ-значение», а коллекция таких элементов называется «словарем». Каждый объект можно найти с помощью этого ключа. По сути это массив, в котором ключ представлен в виде хеш-функции.
Бонус: Алгоритм Флойда-Уоршелла
Предназначен для решения задачи поиска всех кратчайших путей на графе. Для заданного ориентированного взвешенного графа алгоритм находит кратчайшие расстояния между всеми парами вершин за время O(n³). Алгоритм применим к графам с произвольными, в том числе с отрицательными, весами. Таким образом, он является более общим в сравнении с алгоритмом Дейкстры, который не работает с отрицательными весами ребер. Также алгоритм распознает наличие отрицательных циклов.
Имеем граф G=(V,E), в котором каждая вершина пронумерована от 1 до |V|. Сформируем матрицу смежности D. Эта матрица имеет размер |V|∗|V| и каждому ее элементу Dij присвоен вес ребра, соединяющего вершину i с вершиной j. Заметим, что в силу ориентированности графа G матрица D может быть несимметрична.
По мере выполнения алгоритма данная матрица будет перезаписываться: в каждую из ее ячеек вносится значение, определяющее оптимальную длину пути из вершины i в вершину j.
Полагаем диагональные элементы Dii равными нулю, а недиагональные элементы, соответствующие не инцидентным вершинам (не имеющим общего ребра), положим равными бесконечности или числу, заведомо большему возможного расстояния между ребрами.
Ключевая часть алгоритма состоит из трех циклов:
Для k от 1 до |V| выполнять
Для i от 1 до |V| выполнять
Для j от 1 до |V| выполнять
Если D[i,k]+D[k,j]<D[i,j], то D[i,j]:=D[i,k]+D[k,j]
Все сведения взяты из источников:
