Bem-vindo ao décimo nono capítulo da Especialização em Engenharia de Sistemas com Linguagem C (C17/C23)! ⚡

Vetores contíguos no Heap (como visto no Cap 15) são excelentes para acesso indexado $O(1)$, mas sofrem penalidades severas de desempenho ao inserir ou remover elementos no meio da coleção (exigindo deslocar milhares de elementos). As Estruturas de Dados Dinâmicas Encadeadas utilizam nós dispersos na memória RAM interligados por ponteiros. Neste capítulo, você dominará Listas Simplesmente e Duplamente Encadeadas, Pilhas LIFO, Filas FIFO e Árvores Binárias de Busca (BST).

💡 Se você já viu listas encadeadas, pilhas e filas no Módulo 02 (Caps. 14-15), isso é reforço, não repetição perdida: aqui a ênfase é em ponteiros duplos e callbacks (Cap. 14) já dominados, e a novidade real é a Árvore Binária de Busca (BST), que o Módulo 02 não cobre.

Estruturas de Dados Dinâmicas, Listas Encadeadas, Pilhas, Filas e Árvores em C

🗺️ Mapa Conceitual do Capítulo

graph TD
    A["Estruturas Dinâmicas em C"] --> B["1. O Nó Auto-referenciado"]
    A --> C["2. Listas Encadeadas (1D e 2D)"]
    A --> D["3. Pilha LIFO & Fila FIFO"]
    A --> E["4. Árvores Binárias de Busca (BST)"]

    B --> B1["struct No { int dado; struct No *prox; };"]
    C --> C1["Inserção O(1) no início, busca linear e liberação segura"]
    D --> D1["push/pop no Topo vs enqueue no Fim / dequeue no Início"]
    E --> E1["Nós esq/dir, busca O(log N) e percurso In-Order ordenado"]

🧩 1. A Abstração do Nó Auto-referenciado

O bloco fundamental de qualquer estrutura encadeada é o Nó (Node), uma estrutura que guarda o dado útil e um ou mais ponteiros para nós do mesmo tipo:

typedef struct No {
    int dado;               // Carga útil de dados
    struct No *prox;        // Ponteiro para o próximo nó na memória Heap
} No;

🔗 2. Listas Simplesmente Encadeadas (Singly Linked List)

Uma lista encadeada é uma sequência de nós onde cada elemento aponta para o sucessor, terminando com o ponteiro NULL.

Inserção no Início em Tempo Constante $O(1)$:

No* inserirInicio(No *head, int novoDado) {
    No *novoNo = (No*)malloc(sizeof(No));
    if (novoNo == NULL) return head;

    novoNo->dado = novoDado;
    novoNo->prox = head; // O novo nó aponta para a cabeça antiga
    return novoNo;       // O novo nó torna-se a nova cabeça
}

Desalocação Segura de Toda a Lista:

[!CAUTION] Ordem Correta de Liberação: Você deve salvar o ponteiro do próximo nó antes de liberar o nó atual com free():

void liberarLista(No *head) {
    No *atual = head;
    while (atual != NULL) {
        No *proximo = atual->prox; // Salva antes de destruir
        free(atual);
        atual = proximo;
    }
}

🥞 3. Pilhas Dinâmicas (LIFO) e Filas Dinâmicas (FIFO)

Estrutura Mecânica Operações Principais Aplicação Prática
Pilha (Stack) LIFO (Last-In, First-Out) push(topo, x) / pop(topo) Avaliação de expressões, Call Stack de compiladores, histórico “Desfazer”.
Fila (Queue) FIFO (First-In, First-Out) enqueue(fim, x) / dequeue(inicio) Buffers de pacotes de rede, escalonadores de processos do SO, spooler de impressão.

🌳 4. Árvores Binárias de Busca (Binary Search Tree - BST)

Em uma BST, cada nó possui no máximo dois filhos (esquerdo e direito), respeitando a propriedade invariante:

  • Subárvore Esquerda: Contém apenas nós com chaves estritamente menores que a raiz.
  • Subárvore Direita: Contém apenas nós com chaves estritamente maiores que a raiz.
typedef struct NoArvore {
    int chave;
    struct NoArvore *esq;
    struct NoArvore *dir;
} NoArvore;

// Inserção Recursiva Elegante:
NoArvore* inserirBST(NoArvore *raiz, int chave) {
    if (raiz == NULL) {
        NoArvore *novo = (NoArvore*)malloc(sizeof(NoArvore));
        novo->chave = chave;
        novo->esq = novo->dir = NULL;
        return novo;
    }
    if (chave < raiz->chave) {
        raiz->esq = inserirBST(raiz->esq, chave);
    } else if (chave > raiz->chave) {
        raiz->dir = inserirBST(raiz->dir, chave);
    }
    return raiz;
}

Percurso Em-Ordem (In-Order Traversal):

O percurso recursivo Esquerda -> Raiz -> Direita visita todos os elementos da árvore em perfeita ordem crescente:

void percursoInOrder(const NoArvore *raiz) {
    if (raiz != NULL) {
        percursoInOrder(raiz->esq);
        printf("%d ", raiz->chave);
        percursoInOrder(raiz->dir);
    }
}

🔍 5. Diagnóstico & Resolução de Problemas (Troubleshooting)

Sintoma Observado Causa Provável Como Resolver
Loop infinito ao imprimir uma lista encadeada A lista foi corrompida e formou um ciclo fechado ou o último nó não recebeu NULL. Garanta que todo novo nó termine com ->prox = NULL;.
Crash SIGSEGV durante a desalocação da lista Tentativa de acessar atual->prox após executar free(atual) (Use-After-Free). Salve o próximo endereço em variável temporária antes de chamar free(atual).
A Árvore BST degenera para uma lista lenta $O(N)$ Os elementos foram inseridos já ordenados sequencialmente (árvore desbalanceada). Utilize técnicas de balanceamento (Árvores AVL ou Red-Black).

🏆 6. Desafio Prático de Consolidação

Enunciado do Desafio: Desenvolva um programa em C chamado gerenciador_tarefas_bst.c que gerencie uma fila de prioridades baseada em Árvore Binária de Busca:

  1. Crie a estrutura NoTarefa contendo: uint32_t prioridade;, char descricao[40];, struct NoTarefa *esq, *dir;.
  2. Implemente a inserção na árvore ordenada por prioridade.
  3. Implemente a função de percurso in-order para imprimir todas as tarefas em ordem crescente de prioridade.
  4. Implemente a função de desalocação recursiva em pós-ordem void destruirArvore(NoTarefa *raiz);.
  5. Valide a execução no terminal com limpeza completa de memória.
🔍 Ver Solução Comentada do Desafio 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct NoTarefa {
    uint32_t prioridade;
    char descricao[40];
    struct NoTarefa *esq, *dir;
} NoTarefa;

NoTarefa* inserirTarefa(NoTarefa *raiz, uint32_t prio, const char *desc) {
    if (raiz == NULL) {
        NoTarefa *novo = (NoTarefa*)malloc(sizeof(NoTarefa));
        novo->prioridade = prio;
        strncpy(novo->descricao, desc, sizeof(novo->descricao) - 1);
        novo->descricao[sizeof(novo->descricao) - 1] = '\0';
        novo->esq = novo->dir = NULL;
        return novo;
    }
    if (prio < raiz->prioridade) raiz->esq = inserirTarefa(raiz->esq, prio, desc);
    else raiz->dir = inserirTarefa(raiz->dir, prio, desc);
    return raiz;
}

void percursoInOrder(const NoTarefa *raiz) {
    if (raiz != NULL) {
        percursoInOrder(raiz->esq);
        printf("[Prioridade %u]: %s\n", raiz->prioridade, raiz->descricao);
        percursoInOrder(raiz->dir);
    }
}

void destruirArvore(NoTarefa *raiz) {
    if (raiz != NULL) {
        destruirArvore(raiz->esq);
        destruirArvore(raiz->dir);
        free(raiz);
    }
}

int main(void) {
    NoTarefa *raiz = NULL;
    raiz = inserirTarefa(raiz, 3, "Compilar Kernel");
    raiz = inserirTarefa(raiz, 1, "Inicializar Hardware");
    raiz = inserirTarefa(raiz, 2, "Carregar Drivers");

    printf("Tarefas em Ordem de Prioridade (In-Order):\n");
    percursoInOrder(raiz);

    destruirArvore(raiz);
    return 0;
}

🧭 Navegação Rápida

| 📖 Teoria | 📊 Slides | 🧠 Quiz | 💻 Exemplos | 🧩 Exercícios | | :— | :— | :— | :— | :— | | Ler Teoria | Ver Slides | Fazer Quiz | Ver Exemplos | Praticar Exercícios |

🧭 Navegação do Capítulo: ⬅️ Capítulo Anterior · 📚 Sumário do Módulo · ➡️ Próximo Capítulo