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

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

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

Почему важно изучать алгоритмы и структуры данных на C++?

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

Кроме того, знание алгоритмов — это обязательное требование для прохождения собеседований в IT-компании. Даже если вы планируете работать с Python или Java, алгоритмическая база на C++ даёт глубокое понимание того, что происходит «под капотом».

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

1. Массивы (Array)

Массив — это самая простая и быстрая структура данных. Все элементы располагаются в памяти последовательно, доступ к любому элементу по индексу занимает O(1). Однако размер массива фиксирован: его нельзя изменить после создания.

#include <iostream>
using namespace std;

int main() {
    // Статический массив
    int arr[5] = {10, 20, 30, 40, 50};
    
    // Доступ по индексу
    cout << "Третий элемент: " << arr[2] << endl;
    
    // Перебор элементов
    for (int i = 0; i < 5; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Когда использовать: когда количество элементов известно заранее и не меняется. Например, хранение коэффициентов или таблицы констант.

2. Динамические массивы (std::vector)

В C++ стандартная библиотека предоставляет std::vector — динамический массив, который может расти автоматически. Это удобная альтернатива обычным массивам.

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

int main() {
    vector<int> vec = {1, 2, 3, 4, 5};
    
    // Добавление элемента
    vec.push_back(6);
    
    // Удаление последнего элемента
    vec.pop_back();
    
    // Вывод размера
    cout << "Размер: " << vec.size() << endl;
    
    for (int x : vec) {
        cout << x << " ";
    }
    return 0;
}

Важно: push_back может вызвать перераспределение памяти, что занимает O(n) в худшем случае. Если вы заранее знаете размер, используйте reserve().

3. Связные списки (std::list, std::forward_list)

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

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

int main() {
    list<int> myList = {10, 20, 30};
    
    // Вставка в начало
    myList.push_front(5);
    
    // Вставка после первого элемента
    auto it = myList.begin();
    advance(it, 1);
    myList.insert(it, 15);
    
    for (int x : myList) {
        cout << x << " ";
    }
    return 0;
}

Когда использовать: когда требуется часто вставлять или удалять элементы в середине коллекции. Например, реализация очереди или буфера.

4. Стек (std::stack) и очередь (std::queue)

Стек работает по принципу LIFO (Last In, First Out) — последний добавленный элемент извлекается первым. Очередь — FIFO (First In, First Out).

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

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

Применение: стек — для проверки скобок, отмены действий (undo); очередь — для задач планировщика, обработки запросов.

Базовые алгоритмы на C++

Линейный и бинарный поиск

Линейный поиск — простейший: проходим по массиву и сравниваем каждый элемент с искомым. Сложность O(n). Бинарный поиск работает только на отсортированных данных и за O(log n) находит элемент.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // не найдено
}

int main() {
    vector<int> data = {1, 3, 5, 7, 9, 11};
    int index = binarySearch(data, 7);
    cout << "Индекс: " << index << endl; // 3
    return 0;
}

Совет: для бинарного поиска можно использовать встроенную функцию std::binary_search из &