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

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

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

Мы рассмотрим три основные группы: линейные структуры данных (массивы, списки, стеки, очереди), иерархические структуры (деревья) и алгоритмы обработки (сортировка и поиск). Каждый раздел содержит готовый код на C++ и пояснения.

1. Линейные структуры данных: массивы, связные списки, стек и очередь

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

Массивы и динамические массивы (std::vector)

Массив — простейшая структура с фиксированным размером. Для гибкости используйте std::vector:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9};
    
    // Добавление элемента
    numbers.push_back(3);
    
    // Доступ по индексу
    std::cout << "Третий элемент: " << numbers[2] << std::endl;
    
    // Перебор
    for (int num : numbers) {
        std::cout << num << " ";
    }
    return 0;
}

Преимущества: быстрый доступ O(1), кеш-локальность. Недостатки: вставка/удаление в середине — O(n).

Связный список (односвязный)

Список состоит из узлов, каждый хранит данные и указатель на следующий элемент. Реализация на C++:

struct Node {
    int data;
    Node* next;
    
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
private:
    Node* head;
public:
    LinkedList() : head(nullptr) {}
    
    void pushFront(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
    }
    
    void print() {
        Node* current = head;
        while (current) {
            std::cout << current->data << " -> ";
            current = current->next;
        }
        std::cout << "nullptr" << std::endl;
    }
    
    ~LinkedList() {
        Node* current = head;
        while (current) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }
};

Когда использовать: частые вставки/удаления в начале списка. Поиск — O(n).

Стек и очередь

Стек (LIFO) и очередь (FIFO) — специализированные структуры. В C++ есть готовые адаптеры:

#include <stack>
#include <queue>

int main() {
    // Стек
    std::stack<int> st;
    st.push(10);
    st.push(20);
    std::cout << "Верхушка стека: " << st.top() << std::endl; // 20
    st.pop();
    
    // Очередь
    std::queue<int> q;
    q.push(1);
    q.push(2);
    std::cout << "Первый в очереди: " << q.front() << std::endl; // 1
    q.pop();
    
    return 0;
}

2. Иерархические структуры: бинарные деревья поиска

Деревья позволяют эффективно хранить иерархические данные. Бинарное дерево поиска (BST) — классика алгоритмов на C++.

Реализация BST

struct TreeNode {
    int key;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int k) : key(k), left(nullptr), right(nullptr) {}
};

TreeNode* insert(TreeNode* root, int key) {
    if (!root) return new TreeNode(key);
    
    if (key < root->key)
        root->left = insert(root->left, key);
    else if (key > root->key)
        root->right = insert(root->right, key);
        
    return root;
}

bool search(TreeNode* root, int key) {
    if (!root) return false;
    if (root->key == key) return true;
    
    return (key < root->key) ? 
           search(root->left, key) : 
           search(root->right, key);
}

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    std::cout << root->key << " ";
    inorder(root->right);
}

Сложность: в среднем O(log n) для поиска и вставки, в худшем случае (вырожденное дерево) — O(n). Для гарантированной эффективности используйте сбалансированные деревья (AVL, красно-черные), реализованные в std::map и std::set.

3. Алгоритмы сортировки на C++

Сортировка — одна из самых изучаемых тем. Рассмотрим три популярных алгоритма с реализацией на C++.

Быстрая сортировка (Quicksort)

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(std::vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

Средняя сложность O(n log n), но в худшем случае O(n²). На практике — один из самых быстрых.

Сортировка слиянием (Merge Sort)

void merge(std::vector<int>& arr, int left,