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

Algoritmos e Estruturas de Dados em C++: do Básico à Prática

Dominar algoritmos e estruturas de dados é uma etapa fundamental na formação de qualquer programador. Neste artigo, vamos explorar conceitos fundamentais usando a linguagem C++. Você aprenderá como organizar dados de forma eficiente e escrever algoritmos rápidos que servirão de base para seus projetos. O material é voltado para desenvolvedores iniciantes e de nível intermediário.

O que são Algoritmos e Estruturas de Dados?

Um Algoritmo é uma sequência clara de ações para resolver um problema. Uma Estrutura de Dados é uma forma de organizar e armazenar dados, garantindo acesso e modificação eficientes. Em C++, ambos os conceitos estão intimamente ligados: escolher a estrutura de dados correta pode acelerar um algoritmo dezenas de vezes.

Principais estruturas de dados em C++:

• Arrays — conjunto fixo de elementos do mesmo tipo
• Listas Encadeadas — sequências dinâmicas
• Pilhas e Filas — estruturas com acesso limitado
• Árvores — estruturas hierárquicas
• Tabelas Hash — busca rápida por chave

Arrays e Trabalhando com Eles

Um array é a estrutura de dados mais simples, onde os elementos são armazenados em uma área contígua de memória. Em C++, os arrays podem ser estáticos ou dinâmicos.

#include <iostream>using namespace std;

int main() {    // Array estático    int arr[5] = {10, 20, 30, 40, 50};        // Array dinâmico (via new)    int* dynArr = new int[3];    dynArr[0] = 1;    dynArr[1] = 2;    dynArr[2] = 3;        // Exibindo elementos    for (int i = 0; i < 5; i++) {        cout << arr[i] << " ";    }        delete[] dynArr; // Liberando memória    return 0;}

Algoritmo de Busca Linear em um array:

int linearSearch(int arr[], int n, int x) {    for (int i = 0; i < n; i++) {        if (arr[i] == x)            return i; // Retorna o índice    }    return -1; // Não encontrado}

Complexidade: O(n). Para acelerar, use std::vector da STL — ele gerencia a memória automaticamente.

Listas Encadeadas: Simples e Duplamente Encadeadas

Uma lista encadeada consiste em nós, cada um contendo dados e um ponteiro para o próximo (ou anterior) elemento. Em C++, são frequentemente usados std::forward_list (simplesmente encadeada) e std::list (duplamente encadeada).

Implementação de uma lista simplesmente encadeada:

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;    }};

Vantagens das listas:

• Tamanho dinâmico
• Inserção e remoção rápidas no meio (O(1) se houver ponteiro)

Desvantagens:

• Acesso lento por índice (O(n))
• Memória extra para ponteiros

Pilha e Fila: Princípios LIFO e FIFO

Pilha (Stack) funciona pelo princípio "último a entrar, primeiro a sair" (LIFO). Fila (Queue) funciona pelo princípio "primeiro a entrar, primeiro a sair" (FIFO). Em C++, elas são implementadas na STL.

Exemplo de uso de uma pilha:

#include <stack>#include