O primeiro post da categoria Programação tratava de uma introdução sobre a área de Ciência da Computação, com alguns princípios de como funciona a lógica de um computador, envolvendo memória, representação de dados, algoritmos…

Contudo, embora seja uma base importante, o verdadeiro foco da construção deste blog é impulsionar o meu entendimento a respeito dos conteúdos aqui apresentados. Então, visando esse aprofundamento, é preciso escolher temas enriquecedores. Portanto, sem rigor de ordem didática, neste post irei me aprofundar nos ponteiros em C, voltado à construção de estruturas de dados.

Sumário

• O que são ponteiros?
• *Arrays
• Linked Lists
• Hash Tables

O que são ponteiros?

Basicamente, ponteiros são “tipos” especiais de variáveis que armazenam endereços de memória de outras variáveis.

De forma abstrata, visualizamos como “setas” que indicam a localização de uma informação guardada na memória. Assim, o uso desses ponteiros permite acesso indireto a esses dados já existentes e uma manipulação eficiente da quantidade de memória utilizada em um programa.

Declaração e Uso básico

A declaração de um ponteiro é feita utilizando o tipo de dado para o qual ele irá apontar seguido de um asterisco (*), como int *ptr. Para esse tipo especial, temos duas operações importantes:

• Operador de endereço (&): retorna o endereço de uma variável.
• Operador de desreferência (*): isso pode ser um pouco confuso, por também se tratar do asterisco que declara o ponteiro, mas no contexto de operação, esse operador acessa o valor armazenado no endereço que o ponteiro está localizando.

Um operador importantíssimo também é o “->”, que na realidade é uma syntactic sugar para o uso do operador de desreferência (*) e o (.) que acessa um membro de uma struct. Ou seja, basicamente, ao invés de colocar (*ptr_para_struct).membro (que significa acesse o valor dessa memória e depois o membro da struct), utilizamos simplesmente ptr_para_struct->membro.

#include <stdio.h>
#include <stdlib.h>

int main() {
    int numero = 42;
    int *ptr;           // Declaração de ponteiro
    
    ptr = &numero;      // ptr aponta para numero
    
    printf("Valor de numero: %d\n", numero); //42
    printf("Endereço de numero: %p\n", &numero);
    printf("Valor de ptr: %p\n", ptr);
    printf("Valor apontado: %d\n", *ptr); //42
    
    // Modificando valor através do ponteiro
    *ptr = 100; 
    printf("Novo valor de numero: %d\n", numero);
    
    return 0;
}

Arrays

Antes de explorarmos estruturas de dados que utilizam diretamente os ponteiros, precisamos entender a estrutura de dados básica que é o array.

Ele funciona como um grupo de elementos do mesmo tipo que são armazenados em posições contínuas, ou seja, quando declaramos um int numeros[5], estamos reservando 5 espaços sequenciais na memória que conseguem armazenar inteiros.

Esse entendimento de espaço sequencial é a base para compreender os ponteiros, porque na realidade um array também é um ponteiro que aponta para o elemento na primeira posição, e a notação numeros[i] que acessa os elementos de um array, na verdade é uma syntactic sugar para *(array + i), que basicamente muda o endereço do ponteiro uma posição adiante.

É por isso que todos os elementos precisam estar em sequência na memória para que seja possível navegar com uma simples operação de soma (ou subtração), conhecida como aritmética de ponteiros.

Sendo assim, o array numeros por si só é o mesmo que &numeros e &numeros[0], visto que todos esses possuem o mesmo valor, que é o endereço do primeiro elemento do array.

Embora eles possuam o mesmo valor, seus tipos são diferentes, onde o &numeros é o endereço de memória do array completo (int(*)[5]), então a aritmética de ponteiros com esse valor funcionaria de forma diferente.

numeros + 1 = numeros + 1 * sizeof(int)
&numeros + 1 = numeros + 5 * sizeof(int)

Linked Lists

Em tradução, listas encadeadas se referem a valores que estão diretamente ligados um após o outro (“em cadeia”), e os ponteiros funcionam como as “correntes” que estruturam essa cadeia.

Basicamente, cada valor da lista é representado por um Node (nó) que contém um dado a ser armazenado e um ponteiro que armazena a localização do próximo nó. Sendo assim, cria-se um ponteiro de início (head) que, a partir dele, pode-se navegar pelos valores da lista, respeitando a sequência dos nós.

Mas afinal, qual é a vantagem de se utilizar essas listas? Embora não seja possível acessar diretamente um valor de uma lista encadeada, visto que os endereços dos valores estão espalhados na memória, existe uma grande vantagem quando se trata da inserção e remoção de elementos, visto que é necessário apenas reajustar alguns ponteiros.

Nos arrays, precisaríamos de uma nova alocação na memória e recopiar todos os valores anteriores para comportar mais valores em caso de inserção, ou mover todos os valores anteriores uma posição para trás em caso de remoção, buscando “preencher” a lacuna, duas operações que são muito ineficientes à medida que esses arrays se tornam maiores.

Em resumo, a escolha de qual estrutura de dado é melhor depende do contexto. Em casos onde o acesso a posições específicas é muito requisitado, um array possivelmente desempenhará melhor, mas quando o foco é adicionar ou remover elementos (especialmente no início ou no meio da lista), linked lists podem se destacar.

// Definição da estrutura do nó
typedef struct No {
    int dado;
    struct No* proximo;
} No;

// Função para criar um novo nó
No* criarNo(int valor) {
    No* novo = (No*)malloc(sizeof(No));
    if (novo != NULL) {
        novo->dado = valor;
        novo->proximo = NULL;
    }
    return novo;
}

Sobre a inserção de elementos na lista, quando essa inserção acontece no início da lista, o tempo de complexidade é O(1), já que basta fazer a head apontar para o novo elemento, e o novo elemento apontar para o antigo elemento inicial.

Contudo, se o objetivo for adicionar ao final da lista, a complexidade aumenta para O(n), onde “n” é a quantidade de elementos presentes na lista, já que antes de adicionar o novo elemento, precisamos percorrer a lista inteira. A remoção segue o mesmo princípio na complexidade.

Uma solução para diminuir a complexidade de inserção ao final é ter um ponteiro auxiliar que sempre aponta para o último elemento da lista, assim essa inserção também funciona com O(1).

void inserirInicio(No **cabeca, int valor) {
    No* novo = criarNo(valor);
    
    // O novo nó aponta para o antigo primeiro nó
    novo->proximo = *cabeca;
    
    // Atualizar a cabeça da lista
    *cabeca = novo;
}

Inserção ao final sem ponteiro auxiliar, complexidade O(n) a menos que a lista esteja vazia.

void inserirFinal(No **cabeca, int valor) {
    No* novo = criarNo(valor);
    
    // Se a lista está vazia
    if (*cabeca == NULL) {
        *cabeca = novo;
        return;
    }
    
    // Percorrer até o último nó
    No* atual = *cabeca;
    while (atual->proximo != NULL) {
        atual = atual->proximo;
    }
    
    // Conectar o novo nó ao final
    atual->proximo = novo;
}

O uso do operador de desreferência(*) duas vezes nos parâmetros das funções serve para indicar que o valor a ser ajustado é o próprio endereço que o ponteiro está armazenando.

void removeNode(Node** head_ref, int key) {
    // Ponteiro temporário para o nó a ser removido
    Node* current = *head_ref;
    // Ponteiro para o nó anterior
    Node* prev = NULL;

    while (current != NULL && current->data != key) {
        prev = current;
        current = current->next;
    }

    // Caso 3: O elemento não foi encontrado
    if (current == NULL) {
        printf("Elemento %d não encontrado na lista.\n", key);
        return;
    }

    // Caso 4: O elemento foi encontrado. Ajusta os ponteiros
    // Faz com que o nó anterior aponte para o próximo do nó a ser removido
    prev->next = current->next;

    free(current);
    printf("Elemento %d removido da lista.\n", key);
}

Hash Tables

Aqui, avançamos para uma estrutura mais complexa, que se assemelha aos dicionários presentes no Python. As hash tables mapeiam chaves para valores usando uma função hash.

Essas tabelas hash são definidas como um array de ponteiros que são heads para listas encadeadas, onde cada posição desse array aponta para uma head que armazena elementos com o mesmo valor de hash, que varia a depender de como o desenvolvedor quer agrupar as colisões (exemplo: letra que inicia palavras), ou seja, depende da função hash escolhida.

#define TAMANHO_TABELA 7

// Estrutura do nó
typedef struct No {
    int dado;
    struct No* proximo;
} No;

// Estrutura para a tabela hash
typedef struct {
    No* buckets[TAMANHO_TABELA];  // Array de ponteiros para listas
} TabelaHash;

// Função hash simples
int funcaoHash(int chave) {
    return chave % TAMANHO_TABELA;
}

Pensando em um agrupamento de números, essa função hash agrupa os números que deixam o mesmo resto na divisão pelo tamanho da tabela, nesse caso 7. Assim, na posição 1 do array só terão números que deixam resto 1 e assim por diante…

• Inicialização das linked lists (garantir que todas estão vazias).

void inicializarTabela(TabelaHash* tabela) {
    for (int i = 0; i < TAMANHO_TABELA; i++) {
        tabela->buckets[i] = NULL;
    }
}

• Inserção de elementos a partir do índice da função hash.

void inserirHash(TabelaHash* tabela, int valor) {
    int indice = funcaoHash(valor);
    
    No* novo = criarNo(valor);
    
    // Novo elemento aponta para o atual elemento inicial
    novo->proximo = tabela->buckets[indice];
    // Inserir no início da lista (bucket)
    tabela->buckets[indice] = novo;
}

Esses foram as principais estruturas de dados envolvendo ponteiros em C, posteriormente verei alguns algoritmos que fazem manipulações dessas estruturas, para ordenação, reversão e etc…