Вот список из 5 наиболее важных абстрактных типов данных, которые вы ДОЛЖНЫ знать, если хотите стать компетентным программистом, с соответствующими упражнениями для каждого из них.

Связанный список

Связанный список похож на массив тем, что в нем хранится «список» данных. Однако вместо непрерывной памяти каждый элемент в связанном списке хранится отдельно и подключается к следующему через указатели:

Пример C-кода

typedef struct Node
{
    uint32_t data; // use any data type you need
    Node* next; // must be set to NULL or next node in list
}
Node;

Преимущества

  • Динамические массивы
  • Простая вставка/удаление (O(1))

Недостатки

  • Не могу сделать произвольный доступ
  • Следовательно, поиск неэффективен, поскольку нельзя использовать такие алгоритмы, как бинарный поиск (поэтому поиск выполняется за O(n) вместо O(log2(n)))

Дальнейшая проверка

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

Очередь

Однако очередь снова содержит непрерывные данные, но только определенного размера, и данные хранятся в очереди в порядке FIFO (первым пришел, первым вышел).

Пример C-кода

typedef struct Queue
{
    int front, rear, size;
    int* array; // initialise to malloc(size*sizeof(int))
}
Queue;

Преимущества

  • Постановка в очередь, удаление из очереди и получение вперед и назад - это O (1).
  • Полезно в ситуациях, которые работают по принципу FIFO

Недостатки

  • Исправленный размер
  • Может привести к переполнению, как если бы мы продолжали исключать из очереди начало и ставить в конец, индексы становятся слишком большими.

Дальнейшая проверка

  • Циклическая очередь: индексы зацикливаются, так что даже если мы удаляем очередь и все перемещается на единицу, у нас не заканчивается место.
  • Очередь с приоритетом — похожа на очередь, но каждый элемент имеет связанное с ней значение, так что более важные значения удаляются из очереди раньше. (Например, если приоритет зависит от того, насколько велико число, то удаление из очереди удалит не первый входной элемент, а самый большой)

Куча

Стек — это то же самое, что и очередь, за исключением структуры LIFO (последний пришел — первый вышел).

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

Пример C-кода

typedef struct Stack
{
    int *arr;
    int size;
    int t; // must be inited to -1
}
Stack;
// example of push and of pop
void push(Stack& s, int i)
{
    s.t++;
    if (s.t == s.size) return; // overflow
    *(s.arr+s.t) = i;
}
int pop(Stack& s)
{
    if (s.t == -1) return; // underflow
    int r = *(s.arr+s.t);
    s.t--;
    return r;
}

Использование

  • Архитектура «ханойских башен»: вещи кладут и выносят с одной стороны

Дальнейший осмотр (упражнения для читателя)

  • Объединяемые стеки: подсказка: использование связанных списков
  • Реализуйте стек с помощью очередей или наоборот.

Бинарное дерево

Нелинейное иерархическое представление. Он не имеет верхней границы, поскольку хранится с использованием указателей. Его можно использовать для хранения файлов, деревьев решений и алгоритмов маршрутизатора, среди прочего. Вы можете вставлять, удалять, искать и перемещаться по деревьям.

Пример C-кода

typedef struct Node
{
    int data;
    Node *left, *right;
}
Node;

Преимущества:

  • Вставка быстрее, чем связанные списки и массивы,
  • отражает структурное отношение
  • можно использовать (аналогично очереди приоритетов) для нахождения минимума за O(1)

Недостатки:

  • Медленный доступ и удаление
  • Многие указатели являются нулевыми и не используются

Дальнейший осмотр:

  • Обход и обращение бинарного дерева
  • Алгоритмы поиска, такие как поиск в глубину и поиск в ширину
  • Складные бинарные деревья

куча

Куча — это полное бинарное дерево. Это очень важно, так как это фундаментально для компьютеров и языков программирования.

C-код

typedef struct Heap
{
    int *arr; // since we know it is fully populated, we can predict  
              // array size
    int size;
    int max_size;
}
Heap;

Обратите внимание, что куча хранится отсортированной по минимуму или по максимуму в корне.

Преимущества:

  • вставка и удаление в O (log (n)) (лучше, чем обычный массив)
  • Мин и макс эффективны

Недостатки:

  • вставка и удаление за O (log (n)) (хуже, чем двоичное дерево для вставки и хуже, чем связанный список). Это потому, что он отсортирован.
  • «Наращивание» массива требует больших затрат O(n log(n))

Дальнейшая проверка

  • Полностью функциональная куча
  • куча Фибоначчи
  • Соединяйте веревки с минимальными затратами / кодирование Хаффмана

КОНЕЦ

Ну вот! Я надеюсь, что этого было достаточно, чтобы вы начали (я не хотел раскрывать слишком много…), и достаточно, чтобы указать вам правильное направление, не портя радость от самостоятельного изучения. Если вам понравилась эта статья, обязательно хлопните в ладоши и подпишитесь на меня.