Алгоритмы и структуры данных на C++: полное руководство для начинающих

Онлайн-тренажер Python для начинающих

Изучайте Python легко и без перегрузки теорией. Решайте практические задачи с автоматической проверкой, получайте подсказки на русском языке и пишите код прямо в браузере — без необходимости что-либо устанавливать.

Начать курс

Алгоритмы и структуры данных на C++: от основ до практики

Освоение алгоритмов и структур данных — ключевой этап в становлении любого программиста. В этой статье мы разберем фундаментальные концепции на примере языка C++. Вы узнаете, как эффективно организовывать данные и писать быстрые алгоритмы, которые лягут в основу ваших проектов. Материал рассчитан на начинающих и intermediate-разработчиков.

Что такое алгоритмы и структуры данных?

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

Основные структуры данных в C++:

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

Массивы и работа с ними

Массив — простейшая структура данных, где элементы хранятся в непрерывной области памяти. В C++ массивы бывают статическими и динамическими.

#include <iostream>
using namespace std;

int main() {
    // Статический массив
    int arr[5] = {10, 20, 30, 40, 50};
    
    // Динамический массив (через new)
    int* dynArr = new int[3];
    dynArr[0] = 1;
    dynArr[1] = 2;
    dynArr[2] = 3;
    
    // Вывод элементов
    for (int i = 0; i < 5; i++) {
        cout << arr[i] << " ";
    }
    
    delete[] dynArr; // Освобождение памяти
    return 0;
}

Алгоритм линейного поиска в массиве:

int linearSearch(int arr[], int n, int x) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == x)
            return i; // Возвращаем индекс
    }
    return -1; // Не найден
}

Сложность: O(n). Для ускорения используйте std::vector из STL — он автоматически управляет памятью.

Связные списки: односвязные и двусвязные

Связный список состоит из узлов, каждый из которых содержит данные и указатель на следующий (или предыдущий) элемент. В C++ часто используют std::forward_list (односвязный) и std::list (двусвязный).

Реализация простого односвязного списка:

struct Node {
    int data;
    Node* next;
};

class LinkedList {
private:
    Node* head;
public:
    LinkedList() : head(nullptr) {}
    
    void insert(int val) {
        Node* newNode = new Node{val, nullptr};
        if (!head) {
            head = newNode;
            return;
        }
        Node* temp = head;
        while (temp->next) temp = temp->next;
        temp->next = newNode;
    }
    
    void display() {
        Node* temp = head;
        while (temp) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "nullptr" << endl;
    }
};

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

Динамический размер
Быстрая вставка и удаление в середине (O(1) если есть указатель)

Недостатки:

Медленный доступ по индексу (O(n))
Дополнительная память под указатели

Стек и очередь: принципы LIFO и FIFO

Стек (Stack) работает по принципу "последним пришел — первым вышел" (LIFO). Очередь (Queue) — "первым пришел — первым вышел" (FIFO). В C++ они реализованы в STL.

Пример использования стека:

#include <stack>
#include <iostream>
using namespace std;

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);
    s.push(30);
    
    while (!s.empty()) {
        cout << s.top() << " "; // 30 20 10
        s.pop();
    }
    return 0;
}

Пример очереди:

#include <queue>
using namespace std;

int main() {
    queue<string> q;
    q.push("Задача 1");
    q.push("Задача 2");
    q.push("Задача 3");
    
    while (!q.empty()) {
        cout << q.front() << endl; // Задача 1, Задача 2, Задача 3
        q.pop();
    }
    return 0;
}

Где применяются:

Стек — проверка скобок, отмена операций (undo)
Очередь — обработка запросов, BFS (поиск в ширину)

Деревья и хеш-таблицы: продвинутые структуры

Бинарное дерево поиска (BST)

Дерево — иерархическая структура, где каждый узел имеет не более двух потомков. Бинарное дерево поиска обеспечивает быстрый поиск (O(log n) в среднем).

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BST {
public:
    TreeNode* insert(TreeNode* root, int val) {
        if (!root) return new TreeNode(val);
        if (val < root->val)
            root->left = insert(root->left, val);
        else
            root->right = insert(root->right, val);
        return root;
    }
    
    bool search(TreeNode* root, int val) {
        if (!root) return false;
        if (root->val == val) return true;
        if (val < root->val) return search(root->left, val);
        return search(root->right, val);
    }
};