Структуры данных, алгоритмы Flashcards
(23 cards)
Статический и динамический массивы
Статический массив - структура данных, размер который заранее определен и не может быть изменен (byte[]).
Динамический массив - массив, размер которого может изменяться во время выполнения программы (List<T>), память выделяется динамически, когда ранее выделенная память уже израсходована (в C# основан на статическом массиве, который пересоздается с большим размером и данные копируются в него).</T>
Двумерный массив
Двумерный массив - матрица из строк и столбцов (изображение - это двумерный массив пикселей):
- каждый элемент имеет два индекса: [номер строки][номер столбца]
Связные списки
Связные списки:
1) Односвязный список - это структура данных, состоящая из элементов, связанных между собой последовательно посредством указателей, каждый элемент имеет указатель на следующий элемент, а последний элемент списка указывает на NULL.
2) Двусвязный список - список, каждый элемент которого имеет указатель на предыдущий и следующий элемент (в C# LinkedList<T>).</T>
3) Кольцевой односвязный список (циклический) - это структура данных, в которой последний элемент ссылается на первый, образуя замкнутый круг.
Стек (Stack)
Стек - это структура данных, работающая по принципу LIFO (Last In, First Out), что означает: Последний добавленный элемент извлекается первым (C# Stack<T>):
- Push (добавляет элемент на вершину стека)
- Pop (извлекает и возвращает первый сверху элемент стека)
- Peek (извлекает и возвращает первый сверху элемент стека без его удаления)</T>
Реализации стека:
1) через массив ()
2) через односвязный список
Применение стека:
- Обратный порядок обработки данных (например, отмена действий “Ctrl + Z”).
- Управление рекурсией (вызовы функций хранятся в стеке).
- Парсинг выражений (например, вычисление математических выражений).
Очереди (Queues)
Очередь - это структура данных, работающая по принципу FIFO (First in, First Out - первый зашёл — первый вышел).
C# класс Queue<T> - реализует универсальную очередь в виде циклического массива:
- Enqueue (добавляет элемент в конец)
- Dequeue (удаляет самый старый элемент из начала)
- Peek (возвращает первый в очереди элемент без его удаления)</T>
Реализация очереди:
1) через массив (циклический)
2) через двусвязный список
3) на 2 стеках
Двусторонняя очередь
Двусторонняя очередь - поддерживает добавление и удаление с обоих концов за O(1).
Реализация:
1) на двусвязном списке
Очередь с приоритетом
Очередь с приоритетом - очередь, где элементы извлекаются по приоритету
Хеш-таблица
Хеш-таблица - структура данных (большой массив) для хранения пар ключ-значение и обеспечивает быстрый доступ (O(1)) к элементам.
- Хеш-функция - применяется к ключу и возвращает целочисленное хеш-значение (обычно большое число)
Сложность операций:
- Вставка O(1)
- Поиск O(1)
- Удаление O(1)
Деревья
Бинарное дерево - это структура данных, где каждый узел (node) может иметь не более двух потомков (детей).
Виды бинарных деревьев:
1) Сбалансированное дерево (разница высот левого и правого поддерева любого узла не превышает 1):
- гарантируют выполнение операций за O(log n) в худшем случае
2) Полное бинарное дерево (у каждого узла либо два потомка, либо ни одного)
3) Бинарное дерево поиска (Binary Search Tree, BST):
- Все ключи в левом поддереве меньше, чем ключ текущего узла
- Все ключи в правом поддереве больше, чем ключ текущего узла
- Каждое поддерево также является бинарным деревом поиска
- O(logN) - поиск, вставка, удаление в среднем (т.к. при каждом шаге поиска мы отбрасываем половину узлов)
AVL дерево
AVL дерево - самобалансирующееся бинарное дерево поиска, в котором разница в высотах поддеревьев для каждой вершины не может превышать 1. Это гарантирует, что дерево остаётся сбалансированным, а операции поиска, вставки и удаления выполняются за логарифмическое время (O(log n)).
Красно-черные деревья
Красно-черное дерево - самобалансирующееся бинарное дерево поиска (BST), в котором каждый узел имеет цвет (красный или черный) и соблюдаются специальные правила, которые помогают поддерживать баланс.
- Балансировка позволяет выполнять поиск, вставку и удаление за O(log n) даже в худшем случае, предотвращая превращение дерева в односвязный список.
Б-дерево (Btree)
Б-дерево - самобалансирующееся дерево, похоже на бинарное дерево, каждый узел может содержать несколько ключей и иметь больше двух потомков.
Б+-дерево (B+tree)
Б+-дерево (B+tree) - улучшенная версия B-дерева, которая используется в БД и файловых системах:
- Все данные хранятся только в листьях (внутренние узлы содержат только ключи-указатели)
- Листья связаны между собой - это позволяет эффективно искать диапазоны значений
- Более компактные внутренние узлы, поэтому меньше занимаемой памяти, быстрее работа
Графы
Графы - сеть, состоящая из узлов (вершин) и связей (рёбер) между ними:
- можно добраться до элемента разными маршрутами
Виды графов:
1) Ориентированные графы - граф, где рёбра имеют направление.
2) Взвешенные графы - граф, в котором каждое ребро (связь) имеет вес (стоимость).
Какие бывают типы структур данных?
Типы структур данных:
1) Линейные структуры данных (все элементы расположены последовательно, без иерархии): массивы, списки, стеки, очереди
2) Нелинейные структуры данных (элементы связаны не последовательно, а могут соединяться с двумя и более другими элементами в произвольном порядке): деревья, графы, хеш-таблицы
В чем заключается разница между массивом и связным списком?
1) Массив:
- последовательность ячеек памяти, которые расположены подряд
- Позволяет быстро получать элементы по индексу за O(1)
- Сложно добавлять или удалять элементы в середине, потому что приходится сдвигать остальные элементы
2) Связный список:
- Состоит из узлов, где каждый узел хранит значение и ссылку на следующий элемент
- Легко вставлять и удалять элементы, так как изменения касаются только соседних узлов
- Поиск элемента требует O(n) времени, так как приходится перебирать узлы один за другим
Что такое куча и где она используется?
Куча – это структура данных, представляющая собой частично упорядоченное дерево (но хранится в массиве (хитро рассчитываются индексы)), которое подчиняется определенным правилам.
Типы куч:
- max-куча – каждый родительский узел содержит значение, которое больше или равно значениям его потомков.
- min-куча – каждый родительский узел содержит значение, которое меньше или равно значениям его потомков.
Применение куч:
- Приоритетные очереди
- Сортировка кучей – эффективный метод сортировки данных с временной сложностью O(n log n).
- Алгоритм Дейкстры – используется в поиске кратчайших путей в графах.
Методы балансировки BST
Методы балансировки BST:
1) реализовать AVL-дерево (самобалансирующееся): O(log n) для всех операций
2) реализовать Красно-черное дерево: O(log n) для операций, но с меньшим числом поворотов по сравнению с AVL.
Мин-куча
Мин-куча – это бинарная куча, в которой родительский узел всегда меньше своих дочерних узлов.
Как реализовать хеш-таблицу с разрешением коллизий?
1) Цепное хеширование (Каждый элемент хеш-таблицы – это не один объект, а список элементов, которые имеют одинаковый хеш)
2) Открытая адресация
Представления графа
Представления графа:
1) В виде матрицы смежности (двумерный массив): строки и столбцы соответствуют вершинам, а элементы массива показывают, существует ли реберное соединение между двумя вершинами
2) Список смежности (список списков): каждый элемент основного списка представляет вершину графа, а вложенные списки содержат вершины, с которыми эта вершина непосредственно соединена
Поиск в глубину (DFS) и поиск в ширину (BFS) в графе
DFS – это алгоритм обхода графа, который сначала исследует одну ветвь как можно глубже, а затем возвращается назад (бэктрекинг) и переходит к следующей:
- можно реализовать рекурсивно или с помощью стека
BFS – это алгоритм обхода графа, который проходит все вершины на текущем уровне перед тем, как спуститься на следующий уровень:
- удобно реализовывать с помощью очереди
Выбор алгоритма:
- Если нужно найти путь в лабиринте или дереве, DFS подходит лучше.
- Если нужно найти кратчайший путь в невзвешенном графе, BFS работает лучше.
Сортировки
1) Пузырьковая сортировка: O(n²)
2) Сортировка слиянием - быстрая, но требует дополнительной памяти, т.к. нужны вспомогательные массивы: (O(n log n))
3) Быстрая сортировка (очень эффективна, но может работать медленно в худшем случае (если выбрать неудачный опорный элемент) со скоростью O(n²))
