Algoritmos e Estruturas de Dados em C++: Guia Completo para Iniciantes

Algoritmos e Estruturas de Dados em C++: do básico às técnicas avançadas

Algoritmos e estruturas de dados são a base de qualquer programa eficiente. Em C++, você tem controle total sobre memória e desempenho, o que torna esta linguagem ideal para aprender pensamento algorítmico. Neste artigo, abordaremos conceitos-chave, forneceremos exemplos de código e mostraremos como aplicá-los na prática. O material é adequado tanto para iniciantes quanto para desenvolvedores que desejam sistematizar seus conhecimentos.

Abordaremos três grupos principais: estruturas de dados lineares (arrays, listas, pilhas, filas), estruturas hierárquicas (árvores) e algoritmos de processamento (ordenação e busca). Cada seção contém código pronto em C++ e explicações.

1. Estruturas de dados lineares: arrays, listas encadeadas, pilha e fila

Estruturas lineares são a base com a qual se começa a trabalhar com dados. Em C++, elas são implementadas tanto por meio de recursos internos quanto por classes definidas pelo usuário.

Arrays e arrays dinâmicos (std::vector)

Um array é a estrutura mais simples com tamanho fixo. Para flexibilidade, use std::vector:

#include <iostream>#include <vector>

int main() {    std::vector<int> numbers = {5, 2, 8, 1, 9};        // Adicionando elemento    numbers.push_back(3);        // Acesso por índice    std::cout << "Terceiro elemento: " << numbers[2] << std::endl;        // Iteração    for (int num : numbers) {        std::cout << num << " ";    }    return 0;}

Vantagens: acesso rápido O(1), localidade de cache. Desvantagens: inserção/remoção no meio — O(n).

Lista encadeada (simplesmente encadeada)

A lista consiste em nós, cada um armazena dados e um ponteiro para o próximo elemento. Implementação em 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;        }    }};

Quando usar: inserções/remoções frequentes no início da lista. Busca — O(n).

Pilha e fila

Pilha (LIFO) e fila (FIFO) são estruturas especializadas. Em C++, existem adaptadores prontos:

#include <stack>#include <queue>

int main() {    // Pilha    std::stack<int> st;    st.push(10);    st.push(20);    std::cout << "Topo da pilha: " << st.top() << std::endl; // 20    st.pop();        // Fila    std::queue<int> q;    q.push(1);    q.push(2);    std::cout << "Primeiro da fila: " << q.front() << std::endl; // 1    q.pop();        return 0;}

2. Estruturas hierárquicas: árvores binárias de busca

Árvores permitem armazenar dados hierárquicos de forma eficiente. A árvore binária de busca (BST) é um clássico dos algoritmos em C++.

Implementação de 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 =