Рубрики

Введение в структуры данных | 10 наиболее часто используемых структур данных

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

Ниже приведен обзор некоторых популярных структур данных:

  1. Массив . Массив — это набор элементов, хранящихся в смежных местах памяти. Идея состоит в том, чтобы хранить несколько предметов одного типа вместе. Это облегчает вычисление положения каждого элемента, просто добавляя смещение к базовому значению, то есть ячейке памяти первого элемента массива (обычно обозначается именем массива).

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

  3. Стек : Стек — это линейная структура данных, которая следует определенному порядку, в котором выполняются операции. Порядок может быть LIFO (первым пришел — первым вышел) или FILO (первым пришел последним вышел).

    В основном в стеке выполняются следующие три основные операции:

    • Push: добавляет элемент в стек. Если стек заполнен, это называется условием переполнения.
    • Pop: удаляет элемент из стека. Элементы появляются в обратном порядке, в котором они помещены. Если стек пуст, то говорят, что это условие Underflow.
    • Peek или Top: возвращает верхний элемент стека.
    • isEmpty: возвращает true, если стек пуст, иначе false.
  4. Очередь : Как и Стек, Очередь — это линейная структура, которая следует определенному порядку, в котором выполняются операции. Порядок «первым пришел — первым вышел» (FIFO). Хорошим примером очереди является любая очередь потребителей для ресурса, где первым обслужен потребитель, который пришел первым. Разница между стеками и очередями заключается в удалении. В стеке мы удаляем элемент, который был добавлен последним; в очереди удаляем элемент, наименее добавленный за последнее время.

    В основном следующие четыре основные операции выполняются в очереди:

    • Постановка в очередь: добавляет элемент в очередь. Если очередь заполнена, это называется условием переполнения.
    • Dequeue: удаляет элемент из очереди. Элементы появляются в том же порядке, в котором они помещены. Если очередь пуста, то говорят, что это условие Underflow.
    • Front: получить передний элемент из очереди.
    • Сзади: получить последний элемент из очереди.
  5. Двоичное дерево : в отличие от массивов, связанных списков, стека и очередей, которые являются линейными структурами данных, деревья являются иерархическими структурами данных. Бинарное дерево — это древовидная структура данных, в которой каждый узел имеет не более двух дочерних элементов, которые называются левым и правым дочерними элементами. Это реализовано в основном с использованием ссылок.

    Двоичное дерево представлено указателем на самый верхний узел в дереве. Если дерево пусто, тогда значение root равно NULL. Узел двоичного дерева содержит следующие части.

    1. Data
    2. Pointer to left child
    3. Pointer to the right child
  6. Двоичное дерево поиска . В Двоичном дереве поиска есть Двоичное дерево со следующими дополнительными свойствами:
    • Левое поддерево узла содержит только узлы с ключами, меньшими, чем ключ узла.
    • Правое поддерево узла содержит только узлы с ключами, которые больше ключа узла.
    • Левое и правое поддерево каждого также должно быть двоичным деревом поиска.
  7. Куча : Куча — это особая древовидная структура данных, в которой дерево представляет собой полное двоичное дерево. Как правило, кучи могут быть двух типов:
    • Max-Heap: В Max-Heap ключ, присутствующий в корневом узле, должен быть наибольшим среди ключей, присутствующих во всех его дочерних элементах. Одно и то же свойство должно быть рекурсивно истинным для всех поддеревьев в этом двоичном дереве.
    • Min-Heap: в Min-Heap ключ, присутствующий в корневом узле, должен быть минимальным среди ключей, присутствующих во всех его дочерних элементах. Одно и то же свойство должно быть рекурсивно истинным для всех поддеревьев в этом двоичном дереве.

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

    Пусть хеш-функция H (x) отображает значение x по индексу x% 10 в массиве. Например, если список значений [11, 12, 13, 14, 15], он будет сохранен в позициях {1, 2, 3, 4, 5} в массиве или хэш-таблице соответственно.

  9. Матрица : Матрица представляет собой набор чисел, расположенных в порядке строк и столбцов. Необходимо заключить элементы матрицы в скобки или скобки.

    Матрица с 9 элементами показана ниже.

  10. Trie : Trie — это эффективная информационная структура данных Trie val. Используя Trie, сложности поиска могут быть доведены до оптимального предела (длина ключа). Если мы храним ключи в бинарном дереве поиска, для хорошо сбалансированного BST потребуется время, пропорциональное M * log N, где M — максимальная длина строки, а N — количество ключей в дереве. Используя Trie, мы можем искать ключ за O (M) время. Однако, штраф на требованиях к хранению Trie.

Рекомендуемые посты:

Введение в структуры данных | 10 наиболее часто используемых структур данных

0.00 (0%) 0 votes