Conceitos Essenciais de Estruturas de Dados e Algoritmos

A organização eficiente de dados é crucial para o desenvolvimento de software robusto e performático. Estruturas de dados são formas de armazenar e organizar informações, enquanto algoritmos são sequências de passos para resolver um problema. A escolha adequada de ambos impacta diretamente a eficiência de um sistema.

Estruturas Lógicas e Físicas

As estruturas lógicas descrevem as relações abstratas entre os dados. Por exemplo, uma estrutura linear implica que cada elemento possui um predecessor e um sucessor único (exceto o primeiro e o último).

As estruturas de armazenamenot (ou físicas) detalham como os dados são realmente dispostos na memória. As principais abordagens incluem:

• Armazenamento Sequencial: Elementos adjacentes logicamente são armazenados em posições de memória fisicamente contíguas.
• Armazenamento Encadeado: Elementos logicamente adjacentes podem estar em locais físicos não contíguos. A conexão é feita através de ponteiros ou referências que indicam o endereço do próximo elemento.
• Armazenamento por Índice: Além dos dados, uma tabela de índices é criada, onde cada entrada (chave, endereço) aponta para a localização de um elemento.
• Armazenamento Hashing (Dispersão): O endereço de armazenamento de um elemento é calculado diretamente a partir de sua chave.

A estrutura de armazenamento escolhida influencia a alocação de espaço e a velocidade das operações.

Tipos de Dados e Tipos Abstratos de Dados (TAD)

Um tipo de dado é uma coleção de valores e um conjunto de operações definidas sobre esses valores. Podem ser:

• Tipos Atômicos: Valores indivisíveis (ex: inteiro, caractere).
• Tipos Estruturados: Valores que podem ser decompostos em componentes (ex: arrays, structs).

Um Tipo Abstrato de Dados (TAD) define um conjunto de dados e as operações que podem ser realizadas sobre eles, sem especificar a implementação subjacente. Foca no "o quê" pode ser feito, e não no "como".

Complexidade de Tempo e Espaço

A eficiência de um algoritmo é medida por sua complexidade de tempo (quantos passos ou operações) e complexidade de espaço (quanto de memória). Elas são geralmente expressas usando a notação Big O (O(n)).

Classes comuns de complexidade de tempo, do mais eficiente ao menos eficiente:

• O(1): Constante
• O(log n): Logarítmica
• O(n): Linear
• O(n log n): Linear-logarítmica
• O(n²): Quadrática
• O(n³): Cúbica
• O(2ⁿ): Exponencial
• O(n!): Fatorial

É importante considerar:

• Complexidade de Tempo no Pior Caso: O tempo máximo que um algoritmo pode levar.
• Complexidade de Tempo Média: O tempo esperado de execução, considerando todas as entradas possíveis com igual probabilidade.
• Complexidade de Tempo no Melhor Caso: O tempo mínimo que um algoritmo pode levar.

Análise da Complexidade de Tempo em Algoritmos

Para estimar a complexidade, focamos no número de iterações em laços e chamadas recursivas.

• Laços Simples: O número de repetições é o fator dominante. Identifique a condição de término e a relação com o tamanho da entrada.
• Laços Aninhados: Multiplique o número de iterações dos laços internos e externos.
• Recursão (com Master Theorem): Para algoritmos recursivos que dividem o problema em subproblemas, o Teorema Mestre pode ajudar a determinar a complexidade.

Listas Sequenciais

Uma lista sequencial armazena elementos em posições de memória adjacentes, geralmente utilizando um array. Permite acesso direto a qualquer elemento, mas inserções e remoções podem ser custosas.

Alocação Estática

A capacidade máxima é definida em tempo de compilação.

#include <cstddef> // Para nullptr

const int CAPACIDADE_MAXIMA = 10;

template <typename T>
struct ListaSequencialEstatica {
    T dados[CAPACIDADE_MAXIMA]; // Espaço contínuo usando array
    int tamanho;                // Tamanho atual da lista
};

// Exemplo de inicialização (tamanho = 0)
// ListaSequencialEstatica<int> minhaLista;
// minhaLista.tamanho = 0;

Alocação Dinâmica

A capacidade pode ser ajustada em tempo de execução.

#include <iostream>
#include <stdexcept> // Para std::invalid_argument

template <typename T>
struct ListaSequencialDinamica {
    T* elementos;     // Ponteiro para o array alocado dinamicamente
    int capacidade;   // Capacidade total do array
    int tamanhoAtual; // Número de elementos atualmente na lista

    // Construtor padrão
    ListaSequencialDinamica() : elementos(nullptr), capacidade(0), tamanhoAtual(0) {}
};

// Inicializa a lista com uma capacidade inicial
template <typename T>
void InicializarLista(ListaSequencialDinamica<T>& lista, int capInicial = 10) {
    if (capInicial <= 0) {
        throw std::invalid_argument("Capacidade inicial deve ser positiva.");
    }
    lista.elementos = new T[capInicial];
    lista.tamanhoAtual = 0;
    lista.capacidade = capInicial;
}

// Aumenta a capacidade da lista
template <typename T>
void AumentarCapacidade(ListaSequencialDinamica<T>& lista, int adicional) {
    if (adicional <= 0) return;
    T* novoArray = new T[lista.capacidade + adicional];
    for (int i = 0; i < lista.tamanhoAtual; ++i) {
        novoArray[i] = lista.elementos[i];
    }
    delete[] lista.elementos; // Libera a memória antiga
    lista.elementos = novoArray;
    lista.capacidade += adicional;
}

// Obtém o número de elementos na lista
template <typename T>
int ObterTamanho(const ListaSequencialDinamica<T>& lista) {
    return lista.tamanhoAtual;
}

// Libera toda a memória da lista
template <typename T>
void DestruirLista(ListaSequencialDinamica<T>& lista) {
    delete[] lista.elementos;
    lista.elementos = nullptr;
    lista.capacidade = 0;
    lista.tamanhoAtual = 0;
}

// Remove todos os elementos da lista (mas não libera a memória do array)
template <typename T>
void LimparLista(ListaSequencialDinamica<T>& lista) {
    lista.tamanhoAtual = 0;
}

// Verifica se a lista está vazia
template <typename T>
bool EstaVazia(const ListaSequencialDinamica<T>& lista) {
    return lista.tamanhoAtual == 0;
}

// Exibe os elementos da lista
template <typename T>
void ExibirLista(const ListaSequencialDinamica<T>& lista) {
    std::cout << "[";
    for (int i = 0; i < lista.tamanhoAtual; ++i) {
        std::cout << lista.elementos[i] << (i == lista.tamanhoAtual - 1 ? "" : ", ");
    }
    std::cout << "]" << std::endl;
}

// Obtém o elemento na posição i (1-base)
template <typename T>
bool ObterElemento(const ListaSequencialDinamica<T>& lista, int indice, T& valor) {
    if (indice < 1 || indice > lista.tamanhoAtual) {
        return false; // Índice inválido
    }
    valor = lista.elementos[indice - 1];
    return true;
}

// Busca um elemento por valor e retorna sua posição (1-base)
template <typename T>
int BuscarPorValor(const ListaSequencialDinamica<T>& lista, const T& valor) {
    for (int i = 0; i < lista.tamanhoAtual; ++i) {
        if (lista.elementos[i] == valor) {
            return i + 1; // Retorna posição 1-base
        }
    }
    return -1; // Elemento não encontrado
}

// Insere um elemento na posição i (1-base)
template <typename T>
bool InserirElemento(ListaSequencialDinamica<T>& lista, int indice, const T& valor) {
    if (indice < 1 || indice > lista.tamanhoAtual + 1) {
        return false; // Posição inválida
    }
    if (lista.tamanhoAtual == lista.capacidade) {
        AumentarCapacidade(lista, 10); // Aumenta em 10 elementos se estiver cheia
    }
    for (int k = lista.tamanhoAtual; k >= indice; --k) {
        lista.elementos[k] = lista.elementos[k - 1];
    }
    lista.elementos[indice - 1] = valor;
    lista.tamanhoAtual++;
    return true;
}

// Remove um elemento na posição i (1-base)
template <typename T>
bool RemoverElemento(ListaSequencialDinamica<T>& lista, int indice, T& valorRemovido) {
    if (indice < 1 || indice > lista.tamanhoAtual) {
        return false; // Posição inválida
    }
    valorRemovido = lista.elementos[indice - 1];
    for (int k = indice - 1; k < lista.tamanhoAtual - 1; ++k) {
        lista.elementos[k] = lista.elementos[k + 1];
    }
    lista.tamanhoAtual--;
    return true;
}

// Função de teste principal
int main_lista_seq() {
    ListaSequencialDinamica<int> minhaLista;
    InicializarLista(minhaLista, 5); // Inicializa com capacidade 5

    InserirElemento(minhaLista, 1, 10);
    InserirElemento(minhaLista, 2, 20);
    InserirElemento(minhaLista, 1, 5); // Insere no início
    ExibirLista(minhaLista); // Saída esperada: [5, 10, 20]

    std::cout << "Está vazia? " << EstaVazia(minhaLista) << std::endl; // Saída: 0 (false)
    std::cout << "Tamanho: " << ObterTamanho(minhaLista) << std::endl; // Saída: 3

    int valorBusca = 10;
    int pos = BuscarPorValor(minhaLista, valorBusca);
    if (pos != -1) {
        std::cout << "Valor " << valorBusca << " encontrado na posição " << pos << std::endl; // Saída: 10 encontrado na posição 2
    } else {
        std::cout << "Valor " << valorBusca << " não encontrado." << std::endl;
    }

    int elementoRemovido;
    if (RemoverElemento(minhaLista, 2, elementoRemovido)) {
        std::cout << "Elemento " << elementoRemovido << " removido." << std::endl; // Saída: Elemento 10 removido.
    }
    ExibirLista(minhaLista); // Saída esperada: [5, 20]

    DestruirLista(minhaLista);
    return 0;
}

Listas Encadeadas

Diferentemente das listas sequenciais, as listas encadeadas armazenam elementos em nós que podem estar espalhados na memória. Cada nó contém o dado e um ponteiro para o próximo nó. Isso facilita inserções e remoções, mas impede o acesso direto (aleatório).

Lista Encadeada Simples

Cada nó aponta apenas para o próximo, dificultando a navegação reversa.

#include <iostream>
#include <cstddef> // Para nullptr

template <typename T>
struct NoListaSimples {
    T valor;
    NoListaSimples* proximo;
};

template <typename T>
using ListaEncadeadaSimples = NoListaSimples<T>*; // Ponteiro para o primeiro nó ou nó cabeça

// Inicializa a lista (com nó cabeça, que não armazena dados)
template <typename T>
bool InicializarLista(ListaEncadeadaSimples<T>& lista) {
    lista = new NoListaSimples<T>; // Aloca um nó cabeça
    if (lista == nullptr) {
        return false; // Falha na alocação
    }
    lista->proximo = nullptr; // Nó cabeça aponta para nullptr
    return true;
}

// Verifica se a lista está vazia (com nó cabeça)
template <typename T>
bool EstaVazia(const ListaEncadeadaSimples<T>& lista) {
    return lista == nullptr || lista->proximo == nullptr;
}

// Insere um elemento 'val' na posição 'indice' (1-base)
template <typename T>
bool InserirNaPosicao(ListaEncadeadaSimples<T>& lista, int indice, T val) {
    if (indice < 1 || lista == nullptr) {
        return false;
    }

    NoListaSimples<T>* anterior = lista; // Começa no nó cabeça (posição 0)
    int count = 0;
    while (anterior != nullptr && count < indice - 1) {
        anterior = anterior->proximo;
        count++;
    }

    if (anterior == nullptr) { // Índice muito grande
        return false;
    }

    NoListaSimples<T>* novoNo = new NoListaSimples<T>;
    if (novoNo == nullptr) return false;
    
    novoNo->valor = val;
    novoNo->proximo = anterior->proximo;
    anterior->proximo = novoNo;
    return true;
}

// Insere um elemento no final da lista (cauda)
template <typename T>
void InserirNaCauda(ListaEncadeadaSimples<T>& lista, T val) {
    if (lista == nullptr) { // Se a lista não foi inicializada
        InicializarLista(lista);
    }
    NoListaSimples<T>* cursor = lista;
    while (cursor->proximo != nullptr) {
        cursor = cursor->proximo;
    }
    NoListaSimples<T>* novoNo = new NoListaSimples<T>;
    novoNo->valor = val;
    novoNo->proximo = nullptr;
    cursor->proximo = novoNo;
}

// Insere um elemento no início da lista (após o nó cabeça)
template <typename T>
void InserirNaCabeca(ListaEncadeadaSimples<T>& lista, T val) {
    if (lista == nullptr) { // Se a lista não foi inicializada
        InicializarLista(lista);
    }
    NoListaSimples<T>* novoNo = new NoListaSimples<T>;
    novoNo->valor = val;
    novoNo->proximo = lista->proximo; // O novo nó aponta para o que era o primeiro
    lista->proximo = novoNo;           // O nó cabeça aponta para o novo nó
}

// Exibe os elementos da lista
template <typename T>
void ExibirListaEncadeada(const ListaEncadeadaSimples<T>& lista) {
    if (lista == nullptr) {
        std::cout << "Lista não inicializada." << std::endl;
        return;
    }
    NoListaSimples<T>* atual = lista->proximo; // Começa após o nó cabeça
    std::cout << "{";
    while (atual != nullptr) {
        std::cout << atual->valor << (atual->proximo == nullptr ? "" : ", ");
        atual = atual->proximo;
    }
    std::cout << "}" << std::endl;
}

// Função de teste principal para lista encadeada simples
int main_lista_encadeada() {
    ListaEncadeadaSimples<int> minhaLista = nullptr;
    InicializarLista(minhaLista);

    InserirNaCauda(minhaLista, 10);
    InserirNaCauda(minhaLista, 20);
    InserirNaCabeca(minhaLista, 5); // Insere 5 no início
    InserirNaPosicao(minhaLista, 2, 15); // Insere 15 na posição 2 (entre 5 e 10)

    ExibirListaEncadeada(minhaLista); // Saída esperada: {5, 15, 10, 20}

    NoListaSimples<int>* atual = minhaLista->proximo;
    while (atual != nullptr) {
        NoListaSimples<int>* temp = atual;
        atual = atual->proximo;
        delete temp;
    }
    delete minhaLista; // Libera o nó cabeça
    minhaLista = nullptr;

    return 0;
}

A complexidade para a maioria das operações (inserção/remoção em posição arbitrária, busca) é O(n), enquanto a inserção/remoção no início (com nó cabeça) é O(1) e no final (sem manter ponteiro para cauda) é O(n).

Lista Duplamente Encadeada

Cada nó possui ponteiros para o próximo e para o nó anterior, permitindo navegação em ambas as direções, mas com um custo ligeiramente maior de espaço por nó.

#include <cstddef> // Para nullptr

template <typename T>
struct NoDuplo {
    T valor;
    NoDuplo* anterior;
    NoDuplo* proximo;
};

template <typename T>
using ListaDuplamenteEncadeada = NoDuplo<T>*;

// Inicializa uma lista duplamente encadeada (com nó cabeça)
template <typename T>
bool InicializarListaDupla(ListaDuplamenteEncadeada<T>& lista) {
    lista = new NoDuplo<T>; // Aloca o nó cabeça
    if (lista == nullptr) return false;
    lista->anterior = nullptr; // Nó cabeça não tem anterior lógico
    lista->proximo = nullptr;  // Lista vazia
    return true;
}

// Verifica se a lista duplamente encadeada está vazia
template <typename T>
bool EstaVaziaDupla(const ListaDuplamenteEncadeada<T>& lista) {
    return lista->proximo == nullptr;
}

// Insere um nó 'novoNo' após o nó 'posicao'
template <typename T>
bool InserirAposNo(NoDuplo<T>* posicao, NoDuplo<T>* novoNo) {
    if (posicao == nullptr || novoNo == nullptr) {
        return false;
    }
    novoNo->proximo = posicao->proximo;
    novoNo->anterior = posicao;
    if (posicao->proximo != nullptr) { // Se 'posicao' não era o último nó
        posicao->proximo->anterior = novoNo;
    }
    posicao->proximo = novoNo;
    return true;
}

// Remove o nó que está após o nó 'posicao'
template <typename T>
bool RemoverProximoNo(NoDuplo<T>* posicao, T& valorRemovido) {
    if (posicao == nullptr || posicao->proximo == nullptr) {
        return false; // Nó 'posicao' é nulo ou é o último
    }
    NoDuplo<T>* aRemover = posicao->proximo;
    valorRemovido = aRemover->valor;

    posicao->proximo = aRemover->proximo;
    if (aRemover->proximo != nullptr) { // Se 'aRemover' não era o último nó
        aRemover->proximo->anterior = posicao;
    }
    delete aRemover;
    return true;
}

// Libera todos os nós da lista, incluindo o nó cabeça
template <typename T>
void DestruirListaDupla(ListaDuplamenteEncadeada<T>& lista) {
    if (lista == nullptr) return;
    NoDuplo<T>* atual = lista->proximo;
    while (atual != nullptr) {
        NoDuplo<T>* proximoTemp = atual->proximo;
        delete atual;
        atual = proximoTemp;
    }
    delete lista; // Libera o nó cabeça
    lista = nullptr;
}

Listas Encadeadas Circulares

O último nó aponta para o primeiro nó (ou para o nó cabeça), formando um ciclo. Permite percorrer a lista continuamente de qualquer ponto.

Lista Circular Simples

O ponteiro proximo do último nó aponta para o nó cabeça (ou para o primeiro nó real).

#include <cstddef> // Para nullptr

template <typename T>
struct NoCircularSimples {
    T valor;
    NoCircularSimples* proximo;
};

template <typename T>
using ListaCircularSimples = NoCircularSimples<T>*;

// Inicializa uma lista circular simples (com nó cabeça)
template <typename T>
bool InicializarListaCircular(ListaCircularSimples<T>& lista) {
    lista = new NoCircularSimples<T>;
    if (lista == nullptr) return false;
    lista->proximo = lista; // Nó cabeça aponta para si mesmo (lista vazia)
    return true;
}

// Verifica se a lista circular simples está vazia
template <typename T>
bool EhVaziaCircular(const ListaCircularSimples<T>& lista) {
    return lista->proximo == lista;
}

// Verifica se um nó 'p' é o nó da cauda de uma lista circular (assumindo nó cabeça 'lista')
template <typename T>
bool EhNoCaudaCircular(const ListaCircularSimples<T>& lista, NoCircularSimples<T>* p) {
    return p->proximo == lista;
}

Lista Duplamente Encadeada Circular

Similar à lista dupla, mas o ponteiro proximo do último nó aponta para o primeiro, e o ponteiro anterior do primeiro nó aponta para o último. O nó cabeça também participa do ciclo.

#include <cstddef> // Para nullptr

template <typename T>
struct NoDuploCircular {
    T valor;
    NoDuploCircular* anterior;
    NoDuploCircular* proximo;
};

template <typename T>
using ListaDuplamenteCircular = NoDuploCircular<T>*;

// Inicializa uma lista duplamente encadeada circular (com nó cabeça)
template <typename T>
bool InicializarListaDuplaCircular(ListaDuplamenteCircular<T>& lista) {
    lista = new NoDuploCircular<T>;
    if (lista == nullptr) return false;
    lista->anterior = lista; // Nó cabeça aponta para si mesmo
    lista->proximo = lista;  // Nó cabeça aponta para si mesmo (lista vazia)
    return true;
}

// Verifica se a lista duplamente circular está vazia
template <typename T>
bool EhVaziaDuplaCircular(const ListaDuplamenteCircular<T>& lista) {
    return lista->proximo == lista;
}

// Verifica se um nó 'p' é o nó da cauda de uma lista duplamente circular (assumindo nó cabeça 'lista')
template <typename T>
bool EhNoCaudaDuplaCircular(const ListaDuplamenteCircular<T>& lista, NoDuploCircular<T>* p) {
    return p->proximo == lista;
}

Lista Estática Encadeada (Usando Array)

Implementa uma lista encadeada usando um array contíguo. Cada elemento do array representa um nó e contém o dado e o índice do próximo elemento. Útil em ambientes sem suporte a ponteiros ou onde a alocação dinâmica é restrita.

const int CAPACIDADE_ESTATICA = 10;

template <typename T>
struct NoEstatico {
    T valor;
    int proximoIndice; // Índice do próximo nó no array
};

template <typename T>
using ListaEstatica = NoEstatico<T>[CAPACIDADE_ESTATICA];

// Exemplo de como declarar uma lista estática
int main_lista_estatica() {
    ListaEstatica<int> minhaListaEstatica;
    // ... inicialização e operações
    return 0;
}

Comparativo: Listas Sequenciais vs. Encadeadas

Ambas são formas de implementar a estrutura lógica de uma lista linear, mas com diferentes trade-offs:

Listas Sequenciais:

• Acesso: Permitem acesso aleatório (O(1)) a qualquer elemento pelo seu índice.
• Alocação de Espaço: Mais eficiente em termos de densidade de armazenamento, pois não há sobrecarga de ponteiros por nó. No entanto, podem exigir realocação e cópia de elementos ao redimensionar.
• Inserções/Remoções: Custosas (O(n)) no meio da lista, pois exigem o deslocamento de múltiplos elementos.
• Uso: Ideal quando o tamanho da lista é previsível e operações de busca são frequentes, com poucas inserções/remoções.

Listas Encadeadas:

• Acesso: Acesso sequencial (O(n)), pois é necessário percorrer a lista a partir do início para encontrar um elemento.
• Alocação de Espaço: Flexível, pois a memória é alocada e liberada nó a nó. No entanto, cada nó tem uma sobrecarga de espaço para os ponteiros.
• Inserções/Remoções: Eficientes (O(1)) uma vez que a posição de inserção/remoção é encontrada, pois apenas alguns ponteiros precisam ser atualizados.
• Uso: Ideal para listas com tamanho imprevisível, onde inserções e remoções são frequentes, especialmente no início ou fim (se ponteiros para cauda forem mantidos).

Pilha (Stack)

Uma pilha é uma estrutura de dados linear que segue o princípio LIFO (Last In, First Out - Último a Entrar, Primeiro a Sair). As operações são realizadas apenas em uma extremidade, chamada de topo da pilha.

• Empilhar (Push): Adicionar um elemento ao topo.
• Desempilhar (Pop): Remover um elemento do topo.
• Topo (Peek): Acessar o elemento no topo sem removê-lo.

Pilha Sequencial (Usando Array)

#include <iostream> // Para std::cout, std::endl
#include <cstddef>  // Para nullptr

const int CAPACIDADE_PILHA = 10;

template <typename T>
struct PilhaSequencial {
    T elementos[CAPACIDADE_PILHA]; // Array estático para armazenar elementos
    int topo;                       // Índice do elemento no topo da pilha
};

// Inicializa a pilha
template <typename T>
void InicializarPilha(PilhaSequencial<T>& pilha) {
    pilha.topo = -1; // Topo -1 indica pilha vazia
}

// Verifica se a pilha está vazia
template <typename T>
bool PilhaVazia(const PilhaSequencial<T>& pilha) {
    return pilha.topo == -1;
}

// Insere um elemento na pilha
template <typename T>
bool Empilhar(PilhaSequencial<T>& pilha, T valor) {
    if (pilha.topo == CAPACIDADE_PILHA - 1) {
        return false; // Pilha cheia
    }
    pilha.elementos[++pilha.topo] = valor; // Incrementa topo e insere
    return true;
}

// Remove um elemento da pilha e o retorna
template <typename T>
bool Desempilhar(PilhaSequencial<T>& pilha, T& valorRetornado) {
    if (pilha.topo == -1) {
        return false; // Pilha vazia
    }
    valorRetornado = pilha.elementos[pilha.topo--]; // Retorna valor e decrementa topo
    return true;
}

// Função de teste principal para pilha sequencial
int main_pilha_seq() {
    PilhaSequencial<int> minhaPilha;
    InicializarPilha(minhaPilha);

    std::cout << "Pilha vazia? " << PilhaVazia(minhaPilha) << std::endl; // Saída: 1 (true)

    Empilhar(minhaPilha, 10);
    Empilhar(minhaPilha, 20);
    Empilhar(minhaPilha, 30);

    std::cout << "Pilha vazia? " << PilhaVazia(minhaPilha) << std::endl; // Saída: 0 (false)

    int valor;
    if (Desempilhar(minhaPilha, valor)) {
        std::cout << "Desempilhado: " << valor << std::endl; // Saída: Desempilhado: 30
    }
    if (Desempilhar(minhaPilha, valor)) {
        std::cout << "Desempilhado: " << valor << std::endl; // Saída: Desempilhado: 20
    }

    Empilhar(minhaPilha, 40);

    while (!PilhaVazia(minhaPilha)) {
        Desempilhar(minhaPilha, valor);
        std::cout << "Desempilhado: " << valor << std::endl; // Saída: 40, 10
    }
    return 0;
}

Pilha Compartilhada

Uma técnica para otimizar o uso de espaço, onde duas pilhas compartilham o mesmo array de armazenamento, crescendo em direções opostas.

const int CAPACIDADE_COMPARTILHADA = 20;

template <typename T>
struct PilhaCompartilhada {
    T elementos[CAPACIDADE_COMPARTILHADA];
    int topo0; // Topo da pilha 0 (cresce da esquerda para a direita)
    int topo1; // Topo da pilha 1 (cresce da direita para a esquerda)
};

template <typename T>
void InicializarPilhaCompartilhada(PilhaCompartilhada<T>& pilha) {
    pilha.topo0 = -1;
    pilha.topo1 = CAPACIDADE_COMPARTILHADA;
}
// Condição de pilha cheia: pilha.topo0 + 1 == pilha.topo1

Pilha Encadeada (Usando Lista Encadeada)

Uma pilha pode ser implementada usando uma lista encadeada simples. O topo da pilha corresponde ao início da lista.

Fila (Queue)

Uma fila é uma estrutura de dados linear que segue o princípio FIFO (First In, First Out - Primeiro a Entrar, Primeiro a Sair). As inserções (enfileirar) ocorrem na parte traseira (fim da fila) e as remoções (desenfileirar) ocorrem na parte dianteira (início da fila).

• Anfileirar (Enqueue): Adicionar um elemento à cauda.
• Desenfileirar (Dequeue): Remover um elemento da cabeça.
• Cabeça (Front/Peek): Acessar o elemento da cabeça sem removê-lo.

Fila Sequencial (Usando Array)

Pode ser implementada com um array, utilizando ponteiros para o início e fim da fila. Para evitar o problema de "fila cheia" em um array parcialmente vazio, é comum usar uma fila circular.

#include <cstddef> // Para nullptr

template <typename T>
struct NoFila {
    T* dado; // Ponteiro para o dado da árvore (neste contexto, BiTNode*)
    NoFila* proximo;
};

template <typename T>
struct FilaEncadeada {
    NoFila<T>* frente; // Ponteiro para o nó da frente da fila
    NoFila<T>* tras;   // Ponteiro para o nó da trás da fila

    // Construtor padrão
    FilaEncadeada() : frente(nullptr), tras(nullptr) {}
};

// Inicializa uma fila encadeada
template <typename T>
void InicializarFila(FilaEncadeada<T>& fila) {
    fila.frente = nullptr;
    fila.tras = nullptr;
}

// Verifica se a fila está vazia
template <typename T>
bool FilaVazia(const FilaEncadeada<T>& fila) {
    return fila.frente == nullptr;
}

// Enfileira um elemento
template <typename T>
void Enfileirar(FilaEncadeada<T>& fila, T* valor) { // Assume que 'valor' é um ponteiro para T
    NoFila<T>* novoNo = new NoFila<T>;
    novoNo->dado = valor;
    novoNo->proximo = nullptr;
    if (fila.tras == nullptr) { // Fila vazia
        fila.frente = novoNo;
        fila.tras = novoNo;
    } else {
        fila.tras->proximo = novoNo;
        fila.tras = novoNo;
    }
}

// Desenfileira um elemento
template <typename T>
bool Desenfileirar(FilaEncadeada<T>& fila, T*& valorRetornado) { // Assume que 'valorRetornado' é um ponteiro para T*
    if (FilaVazia(fila)) {
        return false;
    }
    NoFila<T>* temp = fila.frente;
    valorRetornado = temp->dado;
    fila.frente = fila.frente->proximo;
    if (fila.frente == nullptr) { // Fila ficou vazia
        fila.tras = nullptr;
    }
    delete temp;
    return true;
}

Árvores

Uma árvore é uma estrutura de dados hierárquica composta por nós, onde cada nó pode ter múltiplos nós filhos. As árvores modelam relações hierárquicas, como sistemas de arquivos, estruturas organizacionais, etc.

Definições Fundamentais

• Nó Raiz: O nó superior da árvore, sem pai. Toda árvore não vazia tem exatamente um nó raiz.
• Nó Folha: Um nó que não possui filhos.
• Nó Interno (ou Ramo): Um nó que possui pelo menos um filho.
• Nó Ancestral: Qualquer nó no caminho da raiz até o nó em questão (incluindo a raiz e o próprio nó).
• Nó Descendente: Qualquer nó no subárvore de um determinado nó.
• Nó Pai (Parenet): O predecessor direto de um nó.
• Nó Filho (Child): Os sucessores diretos de um nó.
• Nós Irmãos (Siblings): Nós que compartilham o mesmo pai.
• Nós Primos (Cousins): Nós que estão no mesmo nível, mas têm pais diferentes.
• Caminho: Uma sequência de nós de um nó para outro. O caminho em árvores geralmente é unidirecional (de cima para baixo).
• Comprimento do Caminho: O número de arestas entre dois nós.

Atributos da Árvore

• Nível (Profundidade) de um Nó: Distância da raiz. A raiz está no nível 1 (ou 0, dependendo da convenção).
• Altura de um Nó: O número de arestas no caminho mais longo do nó até uma folha descendente.
• Altura (ou Profundidade) da Árvore: A altura da raiz, ou o número de níveis na árvore.
• Grau de um Nó: O número de filhos que um nó possui.
• Grau da Árvore: O maior grau entre todos os nós da árvore.

Árvores Ordenadas e Não Ordenadas

Em uma árvore ordenada, a ordem relativa dos filhos de um nó importa (ex: filho esquerdo vs. filho direito). Em uma árvore não ordenada, a ordem dos filhos é irrelevante.

Florestas

Uma floresta é um conjunto de zero ou mais árvores disjuntas (não conectadas).

Propriedades Gerais das Árvores

1. O número total de nós em uma árvore é igual à soma dos graus de todos os nós mais um (N = Σgraus + 1).
2. O número máximo de nós em uma árvore m-ária de altura h (onde cada nó tem no máximo m filhos) é (m^h - 1) / (m - 1).

Árvores Binárias (Ordenadas)

Uma árvore binária é um tipo especial de árvore onde cada nó tem no máximo dois filhos, referidos como filho esquerdo e filho direito. A ordem dos filhos é significativa.

Pode ser:

• Uma árvore vazia (n=0).
• Composta por um nó raiz, uma subárvore esquerda e uma subárvore direita, que também são árvores binárias.

Tipos Específicos de Árvores Binárias

• Árvore Binária Cheia (Full Binary Tree): Todos os nós, exceto as folhas, têm dois filhos, e todas as folhas estão no mesmo nível.
• Árvore Binária Completa (Complete Binary Tree): Uma árvore binária cheia até o penúltimo nível. No último nível, os nós são preenchidos da esquerda para a direita.

Em uma árvore binária completa de n nós, numerados de 1 a n:

• O filho esquerdo do nó i é 2i (se 2i ≤ n).
• O filho direito do nó i é 2i + 1 (se 2i + 1 ≤ n).
• O pai do nó i é i/2 (se i > 1).

Tipos Especiais de Árvores Binárias

1. Árvore Binária de Busca (ABB / BST)

Uma árvore binária onde, para cada nó:

• Todos os valores na subárvore esquerda são menores que o valor do nó.
• Todos os valores na subárvore direita são maiores que o valor do nó.
• As subárvores esquerda e direita também são ABBs.

Facilitam operações eficientes de busca, inserção e remoção de elementos.

2. Árvore AVL (Balanceada)

Uma BST onde, para cada nó, a diferença entre as alturas de suas subárvores esquerda e direita (fator de balanceamento) nunca excede 1. Isso garante uma alta eficiência de busca (O(log n)), evitando o pior caso de uma BST degenerada (O(n)).

3. Árvore Binária Com Fios (Threaded Binary Tree)

Uma otimização de árvores binárias onde os ponteiros nulos (que seriam nullptr) são substituídos por ponteiros para o nó predecessor ou sucessor na travessia em ordem (inorder). Isso permite percorrer a árvore sem uma pilha explícita.

#include <cstddef> // Para nullptr

template <typename T>
struct NoArvoreBinaria {
    T dado;
    NoArvoreBinaria* esq;
    NoArvoreBinaria* dir;
};

// Estrutura para nós de uma árvore binária com fios
template <typename T>
struct NoComFio {
    T dado;
    NoComFio* esquerdo;
    NoComFio* direito;
    int tagEsq; // 0 = filho, 1 = fio (aponta para predecessor)
    int tagDir; // 0 = filho, 1 = fio (aponta para sucessor)
};

template <typename T>
using ArvoreComFio = NoComFio<T>*;

// Variável global auxiliar para o predecessor no percurso em ordem
template <typename T>
NoComFio<T>* predecessorGlobal = nullptr;

// Função auxiliar para processar um nó e criar fios
template <typename T>
void ProcessarNoParaFios(ArvoreComFio<T> noAtual) {
    if (noAtual->esquerdo == nullptr) { // Se a subárvore esquerda é nula
        noAtual->tagEsq = 1;         // É um fio
        noAtual->esquerdo = predecessorGlobal; // Aponta para o predecessor
    }
    if (predecessorGlobal != nullptr && predecessorGlobal->direito == nullptr) { // Se o predecessor não tem filho direito
        predecessorGlobal->tagDir = 1;         // É um fio
        predecessorGlobal->direito = noAtual;  // Aponta para o sucessor
    }
    predecessorGlobal = noAtual; // Atualiza o predecessor
}

// Percurso em ordem para criar os fios
template <typename T>
void CriarFiosInOrder(ArvoreComFio<T> raiz) {
    if (raiz != nullptr) {
        CriarFiosInOrder(raiz->esquerdo);
        ProcessarNoParaFios(raiz);
        CriarFiosInOrder(raiz->direito);
    }
}

Propriedades Adicionais de Árvores Binárias

1. Em qualquer árvore binária não vazia, o número de nós folha (grau 0) é um a mais do que o número de nós com grau 2 (n₀ = n₂ + 1).
2. Se uma árvore binária tem n nós, sua altura máxima é n e sua altura mínima é ⌈log₂(n+1)⌉.
3. Uma árvore binária de altura h possui no máximo 2ʰ - 1 nós.
4. Em uma árvore binária completa, se o número total de nós n é 2k (par), então há um nó com grau 1. Se n é 2k-1 (ímpar), então não há nós com grau 1.

Percursos de Árvores Binárias

Percurso é o processo de visitar cada nó de uma árvore exatamente uma vez de forma sistemática.

1. Percurso em Pré-Ordem (NLR: Nó, Esquerda, Direita)

Visita a raiz, depois percorre a subárvore esquerda, e finalmente percorre a subárvore direita.

2. Percurso em Ordem (LNR: Esquerda, Nó, Direita)

Percorre a subárvore esquerda, visita a raiz, e finalmente percorre a subárvore direita.

3. Percurso em Pós-Ordem (LRN: Esquerda, Direita, Nó)

Percorre a subárvore esquerda, percorre a subárvore direita, e finalmente visita a raiz.

Exemplo:

      A
     / \
    B   C
   / \ / \
  D  E F  G

• Pré-Ordem: A, B, D, E, C, F, G
• Em Ordem: D, B, E, A, F, C, G
• Pós-Ordem: D, E, B, F, G, C, A

#include <iostream> // Para std::cout, std::max

template <typename T>
struct NoArvoreBinaria {
    T dado;
    NoArvoreBinaria* filhoEsquerdo;
    NoArvoreBinaria* filhoDireito;

    NoArvoreBinaria(T val) : dado(val), filhoEsquerdo(nullptr), filhoDireito(nullptr) {}
};

// Percurso em Pré-Ordem (Nó, Esquerda, Direita)
template <typename T>
void PercursoPreOrdem(NoArvoreBinaria<T>* no) {
    if (no != nullptr) {
        std::cout << no->dado << " "; // Visita o nó
        PercursoPreOrdem(no->filhoEsquerdo);
        PercursoPreOrdem(no->filhoDireito);
    }
}

// Calcula a profundidade (altura) de uma árvore binária
template <typename T>
int CalcularProfundidade(NoArvoreBinaria<T>* raiz) {
    if (raiz == nullptr) {
        return 0; // Árvore vazia tem profundidade 0
    } else {
        int profundidadeEsquerda = CalcularProfundidade(raiz->filhoEsquerdo);
        int profundidadeDireita = CalcularProfundidade(raiz->filhoDireito);
        // A profundidade da árvore é o máximo das profundidades das subárvores + 1 (para o nó raiz)
        return std::max(profundidadeEsquerda, profundidadeDireita) + 1;
    }
}

4. Percurso em Nível (Largura)

Visita todos os nós de um nível antes de passar para o próximo. Geralmente implementado usando uma fila.

#include <queue>    // Para std::queue
#include <iostream> // Para std::cout

// Reutiliza a estrutura NoArvoreBinaria<T> definida anteriormente

template <typename T>
void PercursoEmNivel(NoArvoreBinaria<T>* raiz) {
    if (raiz == nullptr) {
        return;
    }
    std::queue<NoArvoreBinaria<T>*> filaDeNos;
    filaDeNos.push(raiz); // Começa enfileirando a raiz

    while (!filaDeNos.empty()) {
        NoArvoreBinaria<T>* noAtual = filaDeNos.front(); // Obtém o nó da frente
        filaDeNos.pop();                               // Desenfileira
        std::cout << noAtual->dado << " ";                 // Visita o nó

        if (noAtual->filhoEsquerdo != nullptr) {
            filaDeNos.push(noAtual->filhoEsquerdo); // Enfileira o filho esquerdo
        }
        if (noAtual->filhoDireito != nullptr) {
            filaDeNos.push(noAtual->filhoDireito); // Enfileira o filho direito
        }
    }
}

Determinação de Árvores Binárias a partir de Sequências de Percurso

Uma única sequência de percurso (pré-ordem, em ordem, pós-ordem ou em nível) não é suficiente para reconstruir unicamente uma árvore binária. No entanto, combinar certas sequências permite a reconstrução:

• Percurso em Ordem + qualquer outro percurso (Pré-ordem, Pós-ordem ou Nível) pode unicamente determinar uma árvore binária.
• Sem o percurso em ordem, geralmente não é possível determinar a árvore de forma única.

Grafos

Um grafo é uma estrutura não linear que consiste em um conjunto de vértices (ou nós) e um conjunto de arestas (ou arcos) que conectam pares de vértices. Grafos podem ser direcionados ou não direcionados, e podem ter pesos nas arestas.

Busca (Search)

A busca é o processo de localizar um elemento com uma determinada chave em uma coleção de dados.

1. Busca Sequencial (Linear)

Percorre a coleção de dados elemento por elemento até encontrar a chave desejada ou atingir o final da coleção. Pode ser aplicada a listas sequenciais ou encadeadas.

Para otimização, pode-se usar um "sentinela": o valor a ser buscado é colocado no final do array para evitar verificações de limite no loop principal.

#include <cstddef> // Para nullptr

template <typename T>
struct ElementoBusca {
    int chave; // Campo chave para busca
    T dadosAdicionais;
};

template <typename T>
struct TabelaSequencial {
    ElementoBusca<T>* registros; // Array de registros
    int totalRegistros;         // Número atual de registros
};

// Busca sequencial com sentinela. Assume que registros[0] pode ser usado como sentinela
// e que os registros válidos começam de 1 a totalRegistros.
template <typename T>
int BuscaLinearComSentinela(TabelaSequencial<T>& tabela, int chaveBuscada) {
    if (tabela.totalRegistros <= 0) {
        return -1; // Tabela vazia
    }
    // Coloca a chave buscada como sentinela na posição 0
    tabela.registros[0].chave = chaveBuscada; 
    int i = tabela.totalRegistros;
    while (tabela.registros[i].chave != chaveBuscada) {
        --i;
    }
    return i; // Retorna 0 se a chave for a sentinela, ou o índice real
}

// Busca sequencial padrão (sem sentinela)
template <typename T>
int BuscaLinear(const TabelaSequencial<T>& tabela, int chaveBuscada) {
    for (int i = 0; i < tabela.totalRegistros; ++i) {
        if (tabela.registros[i].chave == chaveBuscada) {
            return i; // Retorna o índice (0-base)
        }
    }
    return -1; // Não encontrado
}

A Complexidade Média de Busca (ASL) para uma busca sequencial bem-sucedida é (n+1)/2.

2. Busca Binária (Half-Interval Search)

Aplicável apenas a coleções de dados ordenadas (geralmente arrays). Divide repetidamente o intervalo de busca pela metade até encontrar o elemento ou determinar que ele não está presente.

A árvore de decisão de uma busca binária é sempre uma árvore binária de busca balanceada.

template <typename T>
struct ElementoOrdenado {
    int chave;
    T dadosAdicionais;
};

template <typename T>
struct TabelaOrdenada {
    ElementoOrdenado<T>* itens;
    int numeroItens;
};

template <typename T>
int BuscaBinaria(const TabelaOrdenada<T>& tabela, int chaveAlvo) {
    int limiteInferior = 0;
    int limiteSuperior = tabela.numeroItens - 1;
    while (limiteInferior <= limiteSuperior) {
        int meio = limiteInferior + (limiteSuperior - limiteInferior) / 2; // Evita overflow
        if (tabela.itens[meio].chave == chaveAlvo) {
            return meio; // Chave encontrada
        } else if (tabela.itens[meio].chave > chaveAlvo) {
            limiteSuperior = meio - 1; // Busca na metade inferior
        } else {
            limiteInferior = meio + 1; // Busca na metade superior
        }
    }
    return -1; // Chave não encontrada
}

Ordenação (Sorting)

A ordenação é o processo de organizar os elementos de uma coleção em uma determinada ordem (crescente ou decrescente) com base em suas chaves.

1. Ordenação por Seleção (Selection Sort)

Em cada iteração, o algoritmo encontra o menor (ou maior) elemento da parte não ordenada da lista e o troca com o elemento na primeira posição da parte não ordenada. Este processo se repete até que toda a lista esteja ordenada.

É um algoritmo de ordenação instável (a ordem relativa de elementos iguais pode ser alterada).

#include <algorithm> // Para std::swap

// Função auxiliar para trocar dois elementos
template <typename T>
void TrocarElementos(T& a, T& b) {
    T temp = a;
    a = b;
    b = temp;
}

// Ordenação por Seleção padrão
template <typename T>
void OrdenarPorSelecao(T* array, int tamanho) {
    for (int i = 0; i < tamanho - 1; ++i) {
        int indiceMinimo = i;
        // Encontra o menor elemento no restante do array
        for (int j = i + 1; j < tamanho; ++j) {
            if (array[j] < array[indiceMinimo]) {
                indiceMinimo = j;
            }
        }
        // Se o menor elemento não estiver na posição correta, troca
        if (indiceMinimo != i) {
            TrocarElementos(array[i], array[indiceMinimo]);
        }
    }
}

// Ordenação por Seleção otimizada (encontra min e max simultaneamente)
template <typename T>
void OrdenarPorSelecaoOtimizada(T* array, int tamanho) {
    int inicio = 0;
    int fim = tamanho - 1;
    while (inicio < fim) {
        int idxMax = inicio;
        int idxMin = inicio;
        for (int i = inicio + 1; i <= fim; ++i) {
            if (array[i] < array[idxMin]) {
                idxMin = i;
            }
            if (array[i] > array[idxMax]) {
                idxMax = i;
            }
        }

        // Troca o menor elemento para a posição 'inicio'
        if (idxMin != inicio) {
            TrocarElementos(array[inicio], array[idxMin]);
        }
        
        // Se o elemento que estava na posição 'inicio' (que pode ter sido o maior)
        // foi movido para 'idxMin', precisamos atualizar 'idxMax'
        if (idxMax == inicio) {
            idxMax = idxMin; 
        }

        // Troca o maior elemento para a posição 'fim'
        if (idxMax != fim) {
            TrocarElementos(array[fim], array[idxMax]);
        }
        
        inicio++;
        fim--;
    }
}

2. Ordenação por Bolha (Bubble Sort)

Compara e troca pares de elementos adjacentes se estiverem na ordem errada. O processo se repete, "borbulhando" os elementos maiores para o final da lista em cada passagem. Conhecido por sua simplicidade, mas ineficiência para grandes conjuntos de dados.

#include <algorithm> // Para std::swap

// Ordenação por Bolha
template <typename T>
void OrdenarPorBolha(T* array, int tamanho) {
    bool houveTroca;
    for (int i = 0; i < tamanho - 1; ++i) {
        houveTroca = false; // Flag para otimização
        // Percorre do final para o início, empurrando o menor para a esquerda
        for (int j = tamanho - 1; j > i; --j) {
            if (array[j - 1] > array[j]) { // Se os elementos estão fora de ordem
                TrocarElementos(array[j - 1], array[j]);
                houveTroca = true;
            }
        }
        // Se nenhuma troca ocorreu nesta passagem, a lista já está ordenada
        if (!houveTroca) {
            break; 
        }
    }
}

Ambos os algoritmos de ordenação por Seleção e Bolha têm complexidade de tempo O(n²) no pior e caso médio. A complexidade de espaço é O(1).