Алгоритмы и структуры данных, Лекция №2

• Лекция посвящена обсуждению динамических массивов, амортизированного времени добавления, однонаправленных и направленных списков, стеков, очередей, дек и двоичных куч.  

• Также будут рассмотрены абстрактные типы данных и их реализации с использованием массивов и списков.  

• Структура данных - это конкретная реализация абстрактного типа данных.  

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

• Массивы - это наборы элементов определенного типа.  

• Массивы могут быть статическими или автоматическими переменными внутри функций или методов.  

• Статические массивы выделяются в глобальной памяти, а автоматические переменные создаются на стеке.  

• Массивы переменной длины выделяются с помощью оператора new или malloc.  

• Куча - это область памяти, которая выделяется виртуальном пространстве и связывается с оперативной памятью по мере необходимости.  

• Куча используется для выделения объектов небольшого размера, которые не могут быть размещены в стеке.  

• При разрушении объектов, куча автоматически освобождает память.  

• В видео рассказывается о том, как работают динамические массивы в C++.  

• Они выделяются в оперативной памяти и размещаются в виртуальном адресном пространстве.  

• При добавлении элементов в массив, если он достигнет своего предела, будет выделен новый буфер, который будет в два раза больше предыдущего.  

• В видео описывается структура, описывающая массив чисел, и функции, которые работают с этим массивом.  

• При достижении предела буфера, вызывается функция, которая увеличивает размер буфера и копирует старые элементы в новый.  

• После этого старый буфер освобождается, и новый буфер становится активным.  

• В видео обсуждается, можно ли в программе убрать квадратные скобки и использовать только оператор new для выделения памяти.  

• Оказывается, что это возможно, так как функция new знает, сколько памяти выделено, и освободит ее в любом случае.  

• Однако, если используется оператор delete, то вызывается деструктор только для первого элемента, а если используется оператор delete[] - вызываются деструкторы для всех элементов массива.  

• Амортизационный анализ учитывает время работы последовательности операций, а не время работы одной операции.  

• Время работы последовательности операций складывается из времени работы отдельных операций и их количества.  

• Амортизационная стоимость операции в массиве зависит от размера массива и константы.  

• При удвоении размера буфера амортизационная стоимость остается константой.  

• Структура данных содержит буфер, размер буфера и количество элементов в массиве.  

• Реализованы функции доступа к элементам, добавления нового элемента и функция гроу, которая вызывает функцию гет для возврата буфера от индекса.  

• Видео объясняет, что списки - это динамические структуры данных, состоящие из узлов, каждый из которых содержит данные и ссылки на следующий или предыдущий узел.  

• Порядок элементов списка может быть произвольным, но не обязательно последовательным в памяти.  

• Односвязные списки содержат указатель на предыдущий узел, а двусвязные - на предыдущий и следующий.  

• Двусвязные списки могут быть зациклены, но обычно это не требуется.  

• В связанном списке операция удаления элемента может быть более сложной, так как нет указателя на предыдущий элемент.  

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

• Видео обсуждает различные операции, которые могут быть выполнены над связанным списком, включая поиск, вставку, удаление и объединение.  

• Время работы для этих операций обсуждается, и подчеркивается, что в худшем случае время работы будет равно длине списка.  

• Обсуждается операция вставки элемента после текущего элемента в списке.  

• Указатель на текущий элемент и новый элемент создаются, и стрелки перенаправляются.  

• Если следующего элемента нет, указатель на текущий элемент автоматически перенаправляется на ноль.  

• Обсуждается операция удаления элемента из списка.  

• Указатель на элемент обновляется, и стрелки перенаправляются.  

• Две проверки выполняются: существует ли элемент и существует ли следующий элемент.  

• Если элемент существует, его адрес копируется в ячейку памяти.  

• Если элемента нет, указатель автоматически перенаправляется на ноль.  

• Объединяются два списка, используя указатели на начало и конец каждого списка.  

• Если списки односвязные, операция выполняется быстро.  

• Если списки двусвязные, необходимо пройти по списку до конца и обновить указатели.  

• Дополнительные указатели на поля расходуют память.  

• Нет возможности доступа к предыдущим элементам.  

• Быстрое выделение памяти, но расположение элементов в памяти разреженное.  

• Быстрая вставка и удаление элементов, но нет возможности быстрого поиска элемента.  

• Стек - это абстрактный тип данных и структура данных одновременно.  

• Содержит две операции: вставка (push) и извлечение (pop).  

• Вставка выполняется после последнего добавленного элемента, извлечение - последнего добавленного элемента.  

• В видео обсуждается реализация стека с использованием массива.  

• Вершина стека хранится в конце массива, а при добавлении или удалении элементов, вершина стека сдвигается.  

• При удалении элемента, его место не затирается, а вершина стека сдвигается обратно.  

• В видео также рассматривается реализация стека с использованием указателей.  

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

• В видео демонстрируется реализация стека с использованием динамического массива.  

• В этом случае, размер массива передается в конструктор стека, а при добавлении элемента вызывается функция языка для добавления элемента.  

• В видео обсуждаются проверки на пустоту и операции с вершиной стека.  

• Вершина стека может быть равна отрицательному числу, если стек пуст.  

• Если требуется хранить больше двух миллиардов элементов, то размер стека должен быть сохранен.  

• В видео объясняется, как реализовать очередь с использованием массива.  

• При добавлении элемента в очередь, указатель на начало очереди (хэт) и указатель на конец очереди (тейл) сдвигаются, чтобы освободить место для нового элемента.  

• При извлечении элемента, указатель на начало очереди возвращается к началу массива.  

• В видео обсуждается проблема определения, когда очередь заполнена.  

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

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

• В видео подробно объясняется, как реализовать операции добавления и извлечения элементов в очередь.  

• При добавлении элемента, он записывается в конец массива, а затем указатель на конец очереди (тейл) прибавляется к себе.  

• При извлечении элемента, его значение возвращается из указателя на начало очереди (хэт).  

• Обсуждение оптимизации кода, где операции по модулю быстрее, чем логические переходы.  

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

• Обсуждение реализации очереди с помощью односвязного списка.  

• Рассмотрение стрелок и указателей для добавления и удаления элементов.  

• Дек - очередь, которая переводится как "двойная очередь".  

• Операции вставки, начала и конца, удаления из начала и конца.  

• Реализация дек-очереди с помощью списка, массива динамического и двусвязного списка.  

• Двоичная куча - это дерево, в котором значение каждого узла больше или равно значению его потомков.  

• Глубина листьев от корня должна отличаться не более чем на один слой, а последний слой заполняется слева направо.  

• Элементы хранятся в массиве, что позволяет быстро получать значения в дочерних узлах и выполнять операции.  

• Операция сифтап (проталкивание) позволяет восстановить свойства кучи, если один из узлов был изменен.  

• Операция выполняется за логарифмическое время по количеству элементов в куче.  

• Глубина кучи зависит от количества элементов, а не от высоты дерева.  

• Видео начинается с объяснения операции сифт-даун, которая спускает элемент, который меньше своих дочерних элементов.  

• Эта операция также известна как хиппи файт.  

• Затем автор объясняет операцию деструктивные глаза, которая восстанавливает основную кучу, проталкивая элемент наверх или вниз.  

• Эта операция работает с элементом, который меняет свое положение, но не предполагает, что вся куча является правильной.  

• Автор приводит пример, когда элемент больше своих сыновей, и объясняет, что в этом случае вся куча будет правильной.  

• Если элемент меньше своих сыновей, то его нужно опустить, а другой элемент поднять.  

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

• Затем автор переходит к объяснению рекурсии, которая используется в этих операциях.  

• Рекурсия происходит не для левого и правого поддеревьев, а только для одного из них.  

• Это позволяет избежать увеличения рекурсии.