Введение
В основе каждой программы или части программного обеспечения лежат две сущности: данные и алгоритмы. Структуры данных — это то, как мы можем хранить и извлекать данные, они представляют собой знания, которые должны быть организованы в памяти. Неважно, какую проблему мы решаем, так или иначе нам приходится с ними сталкиваться: изучение структур данных необходимо!
Здесь мы увидим четыре самые основные структуры данных.
Начнем!
Множество
Массив — это самая фундаментальная, самая простая и наиболее широко используемая структура данных. Массив — это способ хранения коллекции элементов, доступ к которым осуществляется напрямую с помощью индекса. Чтобы быть более точным: это набор элементов одного типа фиксированного размера, хранящихся в смежных ячейках памяти.
Важно помнить, что индекс массива всегда начинается с 0 и заканчивается на: length -1 :
array[0] // Первый элемент
array[lenght — 1] // Последний элемент.
Сохранение элементов одного типа (одного размера в памяти) рядом друг с другом позволяет компьютеру вычислять положение индекса в памяти, просто добавляя смещение к базовому адресу. Это ключевое преимущество массива: он обеспечивает быстрый поиск O(1).
С другой стороны, добавление и удаление элемента из массива происходит медленно, поскольку вы не можете изменить размер массива после его создания. Это правда, что большинство языков программирования позволяют вам определять динамические массивы: это гибкие массивы, выделяемые во время выполнения программы (например, std::vector для c++). Лучше всего использовать их, но помните, что изменение размера массива требует от компьютера создания нового массива и копирования всех элементов за O(n).
Цели
Сократите количество переменных, используя массивы
Используйте индексы для быстрого доступа к элементу (случайный метод доступа)
Последовательный проход по массиву (цикл)
Вычисляйте статистику с нашими данными.
У нас будет краткий обзор использования массива с примерами кода для выполнения операций обхода, поиска и обновления. Мы также быстро увидим, как найти максимальное значение и вычислить общие выгоды от ряда потерь и прибылей.
Как пользоваться
Вот некоторый код, использующий как необработанный массив, так и динамический массив (рекомендуется). В то время как мы выбрали C++ в качестве языка программирования для иллюстрации кода, другие языки используют ту же логику и чаще всего тот же синтаксис.
Инициализация
Доступ/обновление
Обход/обновление (цикл)
Вот и все: у вас есть все, чтобы начать играть с массивами и векторами, чтобы построить какой-то процесс. Мы закончим тремя простыми реальными случаями, которые часто используются. Допустим, мы игрок в покер, который отмечает результаты своих выигрышей или проигрышей день за днем в течение года.
Максимальное усиление
Время последнего проигрыша
Общий выигрыш
Связанный список
Связанный список — это другая наиболее фундаментальная структура данных: как массив, это также способ хранения набора элементов. Однако вместо того, чтобы хранить данные в фиксированной непрерывной памяти, связанный список представляет собой набор узлов, которые связаны ссылками и могут быть найдены в любом месте пространства памяти.
У каждого данных в памяти есть адрес, вы всегда можете получить адрес из переменной данных и получить доступ к значению данных по его адресу. Идея проста: у нас есть доступ к первому узлу, который содержит: его данные и адрес следующего узла. Нулевой указатель (nullptr) указывает, что конец списка достигнут ( если первый узел является адресом нулевого указателя, то это представляет собой пустой список).
С помощью связанного списка мы не можем получить доступ к элементу напрямую, используя его индекс, потому что компьютер не может вычислить его адрес в памяти, он должен пройтись по списку узел за узлом за O(n). Это первый крупный недостаток связанного списка.
С другой стороны, динамика этой структуры данных делает самым простым добавление, удаление или вставку узлов из любого места в списке, если у нас есть адрес узла. Все эти операции, требующие O(n) времени для массива, теперь выполняются за O(1) со связанным списком.
При всем этом мы должны иметь в виду, что такие огромные преимущества имеют стоимость в памяти: для каждого значения мы должны хранить дополнительный указатель на следующее (это может удвоить объем памяти, используемый для того же объема данных по сравнению с массив).
Цели
Создайте собственную структуру связанного списка
Играйте с указателями
Итерируйте узел за узлом (цикл)
Управляйте выделением памяти
Мы напишем наш собственный простой связанный список, чтобы получить краткий обзор того, как выполнять операции вставки, обхода и обновления с помощью указателей.
Что следующее?
Как только мы поймем интерес этой структуры данных, мы можем перейти к чтению о сложности или рассмотреть другие структуры данных, которые используют преимущества связанных списков: двойные связанные списки, списки смежности, графы…
Мы также можем взглянуть на алгоритмы сортировки, чтобы понять, почему большинство из них будут давать сбои в работе, если мы будем использовать связанный список вместо массива (связанный список не приспособлен для переупорядочивания).
Создадим собственный
Сначала мы воспользуемся необработанным указателем, чтобы проиллюстрировать механизм этой структуры данных, а в конце сделаем упрощенную версию с использованием современного C++.
Единственные данные, которые непосредственно хранит класс, — это указатель на первый узел (голову). Объявление узла списка также должно быть известно, чтобы иметь возможность обрабатывать его (это может быть независимый класс):
Вставить новый элемент
Чтобы вставить элемент в начало списка, нам сначала нужно выделить память для создания нового узла. Затем мы устанавливаем указатель узла рядом, чтобы он указывал на начало списка, и обновляем новый заголовок списка.
Что, если мы хотим иметь возможность помещать элементы в конец списка в O(1)?
Мы можем отслеживать хвостовой узел в LinkedList.
Изображение ниже иллюстрирует операцию вставки и показывает, что код будет использовать одну и ту же стратегию независимо от позиции вставки в списке.
Будьте осторожны: деструктор нельзя запрещать, чтобы избежать утечек памяти!
Это очень важно, поскольку новые узлы будут создаваться с использованием динамически выделяемой памяти и, следовательно, их необходимо освобождать при уничтожении списка. Деструктор также прекрасно иллюстрирует, как перемещаться по списку.
Молодцы!
У нас есть все знания, необходимые для создания других методов/функций, которые мы хотим. Для практики рекомендуем попробовать самому реализовать PopNode(int index), удаляющий узел в заданной позиции (index).
Более чистая версия с использованием современного C++
Та же самая структура данных, закодированная с использованием современного C++, намного компактнее и позволяет избежать управления памятью, просто изменив Node* на unique_ptr‹ Node › :
Стек — ЛИФО
Стек — это структура данных, соответствующая принципу LIFO (последним пришел — первым обслужен). Другими словами: структура данных, в которой элемент, вставленный последним, выходит первым.
И наоборот, это также означает, что элемент, помещенный первым в стек, всегда будет последним удаленным.
Эта ограничивающая концепция чрезвычайно полезна и позволяет легко манипулировать структурами, представляющими структуры нашего реального мира. Например, стопка может представлять собой стопку тарелок или книг, в которой мы можем только удалять/добавлять каждый элемент наверх.
Эта структура используется во всем программировании. Вот некоторые примеры:
Он может отлично имитировать карточную игру.
Стек вызовов относится ко всем вызовам функций, происходящим во время выполнения программы. Стек вызовов необходим для эффективного следования по пути программы.
Примечание: стек вызовов JS, созданный с использованием H.urna Explorer.
Цели
Управляйте стеком.
Получите лучшее представление о рекурсии.
Создавайте собственные структуры стека.
Применяйте на практике массивы и связанные списки.
Понимайте преимущества и недостатки каждой реализации.
Что следующее?
Теперь мы можем играть с продвинутыми алгоритмами, такими как генерация лабиринта с использованием глубокого поиска (DFS).
использование
Стек используется для следующих двух основных операций:
Для правильного использования стека добавлены следующие функции:
Пример
Строим сами
Круто, теперь, когда мы знаем, что такое стек, остается вопрос: как его построить? Хорошие новости! Ответ: довольно просто. Ниже мы рассмотрим реализации, основанные на массивах и связанных списках, чтобы решить, какая из них лучше всего подходит для нашего случая.
Примечание. Стек — это абстрактная структура данных. Определение их структуры основано исключительно на их поведении, а не на базовой реализации. Это контрастирует с более фундаментальными структурами данных, такими как массивы и связанные списки, которые имеют строгие требования к тому, как реализовано хранение их данных.
Реализация связанного списка
Базовая реализация связанного списка — одна из самых простых реализаций стека, которые мы можем сделать. Вернемся к скелету нашей структуры, который мы видели в курсе связный список.
Когда мы хотим что-то добавить в стек (Push), нам просто нужно добавить это в начало списка (на вершину нашего стека).
Но подождите… это именно то, что делает PushFront, не так ли?
Для операции Pop нет ничего проще: просто удалите первый элемент в списке.
Функции Empty и Top также тривиальны.
Приведенная выше реализация дает вам необходимые идеи, и любую оптимизацию можно выполнить, изменив код связанного списка.
Реализация массива
Использование реализации таблицы для стека является простым подходом и требует только ведения счета.
Чтобы добавить что-то в стек (Push), нам просто нужно поместить это в индекс счетчика и увеличить счетчик.
Для функции Pop нет ничего проще: мы просто уменьшаем индекс.
Функции Empty и Top также по-прежнему тривиальны.
Переполнение стека !
Вот что произойдет, если мы попытаемся добавить элемент в полный стек.
Переполнение стека происходит, если указатель стека вызовов превышает границу стека. Стек вызовов может состоять из ограниченного объема адресного пространства, часто определяемого в начале программы.
В случае со стеком вызовов это произойдет, если у нас будет бесконечный цикл/рекурсия. (довольно распространенная ошибка!)
Реализация динамического массива (вектора)
Если бы мы использовали динамическую реализацию, то, когда наш верхний индекс достигает индекса емкости, мы просто удваиваем размер стека. Это подразумевает потерю производительности, поскольку требует выделения памяти, а также копии всех элементов.
Короче
Связанный список
Операции вставки и удаления в O(1).
Может динамически увеличиваться.
Выделение/освобождение памяти требуется для операций вставки и удаления.
Немного больше использование памяти из-за дополнительного хранения указателей.
Массив
Операции вставки и удаления в O(1).
Не может динамически увеличиваться: при инициализации требуется максимальный размер.
Слишком большая таблица приводит к потере memory.
Возможная проблема с переполнением стека.
Динамический массив (вектор)
Операции вставки и удаления за O(1) (кроме изменения размера).
Может динамически увеличиваться.
Операция изменения размера за O(n) .
Слишком большая таблица приводит к потере памяти.
ОЧЕРЕДЬ — ФИФО
Очередь — это структура данных, соответствующая принципу FIFO (First In First Out). В отличие от Стеков, элемент, вставленный первым, должен быть первым выводимым элементом.
И наоборот, это также означает, что последний элемент, помещенный в стек, всегда будет последним удаленным.
Мы можем легко визуализировать это, представляя себе очередь ожидания. Очереди используются во всем программировании, вот несколько примеров:
Он может прекрасно имитировать очередь ожидания.
Алгоритм поиска в ширину, генерирующий минимальное остовное дерево.
Примечание: остовное дерево — это ациклический подграф связного и неориентированного графа, соединяющий все вершины.
Очередь действует как буфер между задачей и вызываемой службой. Он смягчает прерывистые перегрузки (которые могут привести к сбою в обслуживании) за счет уменьшения влияния пиковых нагрузок (например, конденсатора в электронике).
Цели
Управляйте очередью.
Создавайте собственные структуры очередей.
Применяйте на практике массивы и связанные списки.
Понимайте преимущества и недостатки каждой реализации.
использование
Очередь используется для следующих двух основных операций:
Следующие функции добавлены для правильного использования очереди:
Строим сами
Как построить один? Хорошие новости! Ответ: довольно просто. Мы рассмотрим реализации, основанные на массивах и связанных списках, чтобы решить, какая из них лучше всего подходит для нашего случая.
Примечание. Очередь — это абстрактная структура данных (как стек). Определение их структуры основано исключительно на их поведении, а не на базовой реализации. Это контрастирует с более фундаментальными структурами данных, такими как массивы и связанные списки, которые имеют строгие требования к тому, как реализовано хранение их данных.
Реализация связанного списка
Мы используем связанный список с дополнительным указателем в конце очереди. Вернемся к скелету нашей структуры, увиденному в связном списке.
Когда мы хотим что-то добавить в очередь (Поставить в очередь), нам просто нужно добавить это в конец списка.
Мы запоминаем последний элемент списка, чтобы делать эффективные вставки.
Для операции Удалить из очереди нет ничего проще: просто удалить первый элемент в списке (как в стопках).
Функции Empty и Seek также тривиальны.
Приведенная выше реализация дает вам необходимые идеи, и любую оптимизацию можно выполнить, изменив код связанного списка.
Реализация массива
Использование табличной реализации для очереди — не самый простой подход, но он остается очень интересным. Это включает в себя использование круговой таблицы, часто называемой кольцевым буфером. Это также часто используется для создания кэшей памяти.
Когда мы хотим что-то добавить в очередь (Поставить в очередь), нам просто нужно добавить это в конец очереди и увеличить счетчик.
Короче
Связанный список
Операции вставки и удаления в O(1).
Может динамически увеличиваться.
Выделение/освобождение памяти требуется для операций вставки и удаления.
Немного больше использование памяти из-за дополнительного хранения указателей.
Круговой массив
Операции вставки и удаления в O(1).
Не может динамически увеличиваться: при инициализации требуется максимальный размер.
Слишком большая таблица приводит к увеличению потраченная впустую память.
Используется понятие кругового массива (например, буферы, кэши и т. д.).
Надеюсь, вам понравилось это небольшое исследование четвертых столпов структур данных.
