Estruturas e estruturas de dados encadeadas em C

Uma estrutura agrupa valores relacionados em um registro. Seus membros têm nomes e podem ter tipos diferentes. Uma leitura de sensor, por exemplo, precisa de um identificador e de uma temperatura.

Defina e inicialize um registro

struct reading {
    int id;
    double temp_c;
};
struct reading r = {.temp_c = 21.5, .id = 7};
r.temp_c += 0.5;

A definição apresenta o tipo struct reading; reading é sua etiqueta. O ponto e vírgula final fica depois da chave de fechamento. Definir o tipo não aloca um objeto. A declaração de r cria um objeto, e . seleciona seus membros. Aqui a temperatura passa a 22,0 °C. Quando apenas uma etiqueta foi declarada, o nome do tipo inclui struct: reading r; precisa de um typedef separado.

Um inicializador como {7, 21.5} segue a ordem de declaração. Designadores como .id = 7 permitem nomear membros em outra ordem. Membros omitidos de um inicializador recebem valores zero, então {0} inicializa todo o registro. Uma declaração local struct reading r; sem inicializador deixa seus membros indeterminados até que recebam valores.

Um membro tem seu próprio tipo e endereço. Para ler uma temperatura com scanf, use scanf("%lf", &r.temp_c) e verifique se o valor de retorno é 1. O ponto tem precedência sobre &, então isso passa o endereço do membro double.

Copie e compare os valores

struct reading s = r;
s.temp_c = -4.0;
int same = r.id == s.id && r.temp_c == s.temp_c;

A atribuição copia todos os membros. Alterar s.temp_c deixa r.temp_c em 22,0. Arranjos fixos dentro de estruturas também são copiados: um membro char name[32] pertence ao registro. Isso funciona embora arranjos independentes em C não possam ser atribuídos com =. Membros ponteiro exigem cuidado extra, pois o ponteiro copiado continua apontando para o mesmo objeto.

C não define == para estruturas inteiras. Compare os membros que definem a igualdade para sua tarefa. memcmp compara os bytes diretamente, incluindo o preenchimento, e pode indicar uma diferença entre registros cujos valores de membros são iguais.

Entenda a disposição na memória

Os membros aparecem na ordem de declaração, sem preenchimento antes do primeiro membro. O compilador pode adicionar bytes não usados entre os membros e no fim para atender aos requisitos de alinhamento. Em uma plataforma comum de 64 bits com int de 4 bytes e alinhamento de 4 bytes, struct { char c; int i; char d; } ocupa 12 bytes. Seus membros começam nos deslocamentos 0, 4 e 8. Reordenar para int i; char c; char d; normalmente reduz o tamanho para 8 bytes. Use sizeof para o tamanho real e offsetof de <stddef.h> para um deslocamento.

Estruturas podem ser aninhadas. Com struct point { double x_m, y_m; }; e struct rect { struct point corner; double width_m, height_m; };, box.corner.x_m acessa a coordenada x do canto em metros. Uma estrutura não pode conter um membro completo de seu próprio tipo: isso exigiria um objeto infinitamente grande. Um ponteiro para seu próprio tipo tem tamanho fixo e torna possíveis os nós encadeados.

Uma declaração typedef dá outro nome a um tipo existente. Ela muda como você escreve o tipo, não como seus objetos se comportam. typedef double meters; torna meters outro nome para double.

Dê nome a uma estrutura e passe-a por valor

typedef struct {
    int id;
    double temp_c;
} reading;

reading make_reading(int id, double t) {
    reading r = {id, t};
    return r;
}
void warm_copy(reading r) {
    r.temp_c += 1.0;
}

Agora você pode declarar reading r = make_reading(7, 21.5);. Retornar uma estrutura retorna seu valor. Chamar warm_copy(r) fornece uma cópia à função, então a temperatura da função chamadora permanece em 21,5 °C. Uma cópia de um registro pequeno costuma ser a interface mais clara quando o objeto da função chamadora deve permanecer inalterado.

Um tipo autorreferencial precisa de sua etiqueta dentro da definição:

typedef struct node {
    int number;
    struct node *next;
} node;

O nome alternativo node fica disponível após a declaração. Dentro dessas chaves, struct node já nomeia o tipo incompleto e pode ser usado para um ponteiro. A etiqueta e o nome alternativo podem ter a mesma grafia porque etiquetas usam seu próprio espaço de nomes.

Acesse o objeto da função chamadora por um ponteiro

void warm(reading *p) {
    p->temp_c += 1.0;
}
reading r = {7, 21.5};
reading *p = &r;
p->temp_c -= 1.5;
warm(&r);

A subtração altera r.temp_c para 20,0; warm então o altera para 21,0. A função recebe uma cópia do endereço, e os dois ponteiros continuam acessando o mesmo registro. Use -> com um ponteiro e . com um objeto de estrutura. p->temp_c significa (*p).temp_c. Os parênteses são necessários porque o acesso a membro tem precedência maior que a desreferenciação: *p.temp_c tenta selecionar um membro de p antes de aplicar *.

Para ler sem copiar a estrutura, receba const reading *p. Uma atribuição a p->temp_c por meio desse ponteiro é rejeitada. A variável ponteiro ainda pode mudar, por exemplo, ao percorrer um arranjo. Já reading *const p torna fixo o próprio ponteiro. Para estruturas com membros ponteiro, um ponteiro para dados constantes não torna somente para leitura os dados apontados que foram alocados separadamente.

Atribua a alguém a responsabilidade por um registro no heap

Inclua <stdlib.h> para alocação e <stdbool.h> para este resultado de sucesso:

bool make_heap_reading(reading **out, int id, double t) {
    reading *p = malloc(sizeof *p);
    if (p == NULL) return false;
    *p = (reading){.id = id, .temp_c = t};
    *out = p;
    return true;
}

A função escreve em *out somente após a alocação ser bem-sucedida. A função chamadora pode declarar reading *item = NULL;, chamar make_heap_reading(&item, 8, -2.0), tratar um resultado falso e depois chamar free(item). sizeof *p mede o tipo apontado mesmo antes de p apontar para um registro inicializado; essa expressão não lê o registro.

Um ponteiro para uma estrutura local automática fica pendente quando a função retorna. Retorne o valor da estrutura ou uma alocação no heap com responsabilidade de liberação bem definida. Retornar &r de uma função cuja variável local é r não pode estender seu tempo de vida.

Um arranjo de estruturas mantém registros lado a lado. Use um índice para selecionar um registro e depois um ponto para selecionar um membro. Isso faz com que percursos, buscas e ordenações funcionem de forma semelhante ao que ocorre com um arranjo de números.

Percorra registros com uma contagem explícita

reading readings[4] = {
    {1, 21.5}, {2, -3.0}, {3, 18.25}, {4, 30.0}
};
size_t n = sizeof readings / sizeof readings[0];
size_t best = 0;
for (size_t i = 1; i < n; ++i) {
    if (readings[i].temp_c > readings[best].temp_c)
        best = i;
}

Aqui, reading é o nome alternativo da estrutura com identificador e temperatura. O melhor índice passa de 0 para 3, então o registro com a maior temperatura tem id 4 e temperatura de 30,0 °C. Começar com um elemento real também funciona quando todas as temperaturas são negativas; começar com um suposto máximo de zero pode falhar. Esse percurso exige pelo menos um elemento. Uma busca reutilizável deve informar que o arranjo está vazio antes de ler o elemento 0.

A contagem com sizeof funciona onde readings é um arranjo. Em um parâmetro de função, uma declaração de arranjo se torna um ponteiro, então passe n separadamente. (items + i)->temp_c e items[i].temp_c acessam o mesmo membro.

Forneça uma função de comparação para qsort

Inclua <stdlib.h>. Para valores finitos de temperatura, esta função de comparação retorna um sinal sem converter uma pequena diferença de temperatura em inteiro:

int cmp_temp(const void *a, const void *b) {
    const reading *x = a;
    const reading *y = b;
    return (x->temp_c > y->temp_c)
         - (x->temp_c < y->temp_c);
}
/* With the array above: */
qsort(readings, n, sizeof readings[0], cmp_temp);

A função de comparação recebe endereços de elementos. Negativo significa que o primeiro vem antes, zero significa equivalência e positivo significa que vem depois. A ordem dos ids após a ordenação é 2, 3, 1, 4. Retornar a diferença double diretamente trunca uma diferença como −0,25 para zero. Subtrair chaves inteiras pode causar estouro. Comparar primeiro evita esses erros. qsort não preserva a ordem original dos elementos equivalentes.

Amplie um arranjo sem perder seu armazenamento

Mantenha separadamente a quantidade de elementos em uso e a capacidade. Para um arranjo alocado com cap positivo, use um ponteiro temporário ao dobrar a capacidade. Inclua <stdint.h> para SIZE_MAX:

if (cap > SIZE_MAX / 2 / sizeof *items) return false;
size_t new_cap = 2 * cap;
reading *tmp = realloc(items, new_cap * sizeof *items);
if (tmp == NULL) return false;
items = tmp;
cap = new_cap;

Essas instruções pertencem a uma função que retorna bool; items é seu ponteiro para o arranjo e cap é sua capacidade positiva. Em caso de falha, a alocação antiga permanece disponível. Em caso de sucesso, a alocação pode mudar de lugar, então ponteiros antigos para seus elementos precisam ser substituídos. Uma capacidade inicial zero exige sua própria alocação inicial.

Determine a responsabilidade de uma cópia

Com typedef struct { char *name; int age; } person;, person b = a; copia o endereço em name. Os dois registros acessam a mesma cadeia de caracteres. Liberar as duas cópias como responsáveis pela memória liberaria a mesma alocação duas vezes. Para uma cópia independente, aloquel strlen(a.name) + 1 bytes, verifique se a alocação teve sucesso e use strcpy de <string.h>. Um membro fixo char name[32] é copiado com a estrutura. strdup faz a alocação e a cópia, mas pertence a POSIX e C23, não à biblioteca padrão C17.

Uma enumeração dá nomes compreensíveis a opções inteiras. Nomes como HIGH tornam visível o propósito de uma condição sem exigir que a pessoa lembre o que o número 10 representa.

Acompanhe a numeração

enum weekday { MON, TUE, WED, THU, FRI, SAT, SUN };
enum level { LOW = 1, MEDIUM, HIGH = 10, CRITICAL };
enum level alert = HIGH;

Um primeiro valor omitido é zero. Valores omitidos posteriores aumentam o valor anterior em um. Assim, MON é 0 e SUN é 6; os níveis são 1, 2, 10 e 11. Um valor explícito reinicia a contagem naquele ponto. Constantes diferentes podem compartilhar um valor, mas valores idênticos não podem aparecer como rótulos case separados no mesmo switch.

Um nome alternativo pode encurtar uma declaração: typedef enum { RED, YELLOW, GREEN } light; permite light signal = RED;. Constantes de enumeração compartilham o espaço de nomes dos identificadores comuns em seu escopo. Duas enumerações diferentes não podem ambas declarar RED no mesmo escopo. Prefixos como em LIGHT_RED e PAINT_RED mantêm os nomes distintos.

Trate cada opção

const char *level_name(enum level value) {
    switch (value) {
        case LOW: return "low";
        case MEDIUM: return "medium";
        case HIGH: return "high";
        case CRITICAL: return "critical";
    }
    return "unknown";
}

Cada return encerra seu caso. Se um caso realizar uma ação e depois precisar parar, inclua um break; chegar ao próximo rótulo faz a execução continuar nele. Com GCC, -Wall ativa avisos para casos de enumeração ausentes quando não há default; o Clang também diagnostica essas omissões por padrão. Um aviso pode revelar um caso ausente quando você adicionar uma constante posteriormente.

Valide a entrada como um conjunto de opções

O tipo de enumeração não obriga o valor a pertencer ao conjunto nomeado. C17 permite atribuição a partir de um inteiro, então enum level x = 42; pode compilar. Uma verificação de que o número está entre 1 e 11 ainda admite valores sem nome, como 6. Teste os valores realmente permitidos:

#include <stdbool.h>
bool valid_level(int value) {
    return value == LOW || value == MEDIUM
        || value == HIGH || value == CRITICAL;
}

Somente após essa verificação a entrada deve se tornar um nível. Para os dias consecutivos da semana, uma verificação de faixa de MON a SUN é suficiente. Em uma enumeração comum de C17, as constantes enumeradoras têm tipo int. C23 também permite especificar um tipo subjacente, como em enum color : unsigned char; essa sintaxe não pertence a C17.

Imprima nomes e use contagens

printf("%d\n", SUN) imprime “6”, não “SUN”. Para valores consecutivos que começam em zero, um arranjo de nomes fornece o texto: const char *day_names[] = {"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};. Após validar um índice, day_names[SUN] é “Sun”. Usar um valor de nível como HIGH para indexar esse arranjo exigiria outro mapeamento, pois os valores de nível têm lacunas.

Adicionar DAY_COUNT imediatamente após SUN lhe dá o valor 7, útil como limite de laço ou tamanho de arranjo. Ele conta os dias, mas não é um dia válido. Nomes de enumeração seguem as regras de escopo de C e podem ser exibidos por depuradores; já #define faz substituição de texto pelo pré-processador.

Uma união dá a vários membros o mesmo armazenamento. Ela é adequada a um valor que pode ser de um entre vários tipos. Uma estrutura dá a cada membro seu próprio armazenamento e é adequada a um registro que precisa de todos esses valores juntos.

Armazene uma alternativa

union value {
    int i;
    double d;
    char c;
};
union value v = {.d = 2.5};

Todos os membros começam no mesmo endereço. A união deve comportar seu maior membro e atender às necessidades de alinhamento; com um double de 8 bytes em plataformas comuns, essa união ocupa 8 bytes. Um inicializador simples {42} inicializa seu primeiro membro, i; .d = 2.5 escolhe d explicitamente.

Escrever v.i = 42 após o inicializador substitui a alternativa armazenada. Ler v.d depois disso não converte 42 em um double: interpreta os bytes armazenados usando outra representação. Essa representação pode ser inválida. Leia o membro correspondente ao valor que você armazenou.

Registre qual membro é válido

Combine a união com uma enumeração. A enumeração é a etiqueta, e a união contém os dados associados:

enum kind { K_INT, K_DOUBLE, K_CHAR };
struct tagged {
    enum kind kind;
    union value as;
};
struct tagged make_double(double d) {
    return (struct tagged){.kind = K_DOUBLE, .as = {.d = d}};
}

Uma função auxiliar define as duas partes juntas. O código que escreve mantém os dois campos sincronizados. Se o código escrever em t.as.i, mas deixar t.kind como K_DOUBLE, uma leitura posterior escolherá a representação errada.

#include <stdio.h>
void print_cell(struct tagged t) {
    switch (t.kind) {
        case K_INT: printf("%d", t.as.i); break;
        case K_DOUBLE: printf("%.1f", t.as.d); break;
        case K_CHAR: printf("%c", t.as.c); break;
    }
}

Chamar essa função para células contendo 42, 2,5 e 'x', com espaços impressos entre as chamadas, produz “42 2.5 x”. Cada caso escolhe tanto o membro quanto o formato correspondente. Um token de calculadora pode, de forma semelhante, conter um número ou um operador.

Em plataformas comuns de 64 bits, uma enumeração de 4 bytes, preenchimento e essa união de 8 bytes fazem struct tagged ocupar 16 bytes. Uma estrutura que armazena a enumeração e as três alternativas separadamente costuma ocupar 24 bytes. Esses são exemplos de disposição; consulte os tipos reais com sizeof.

Agrupe pequenos indicadores em campos de bits

struct flags {
    unsigned int ready : 1;
    unsigned int mode : 3;
};

A largura vem depois dos dois-pontos. Um campo sem sinal de 1 bit contém 0 ou 1; um campo de 3 bits contém valores de 0 a 7. Armazenar 9 em mode mantém os três bits menos significativos e armazena 1. Isso perde informação, então valide um modo antes de armazená-lo quando valores maiores indicarem erro.

Um campo de bits não tem uma posição endereçável separadamente, então &flags.mode é inválido para uma variável chamada flags. Sua ordem de alocação e seu empacotamento dependem da implementação. Não use uma declaração de campo de bits como garantia portável de uma disposição exata em arquivo ou dispositivo. Uma largura declarada especifica a faixa de valores do campo, não a disposição de cada byte ao seu redor.

Uma lista simplesmente encadeada armazena cada item em um nó alocado separadamente. Cada nó contém seu valor e o endereço do próximo nó. O ponteiro para o início da lista aponta para o primeiro nó; NULL marca tanto uma lista vazia quanto o fim de uma cadeia.

Defina a ligação e insira no início

#include <stdbool.h>
#include <stdlib.h>
typedef struct node {
    int number;
    struct node *next;
} node;

bool prepend(node **head, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->number = value;
    n->next = *head;
    *head = n;
    return true;
}

Comece com node *list = NULL;. Chame prepend(&list, value) e trate um resultado falso. A função recebe o endereço do ponteiro para o início da lista da função chamadora. Portanto, *head designa o ponteiro que deve mudar. Receber apenas node *head e atribuir um valor a esse ponteiro local deixaria inalterado o ponteiro da função chamadora.

A ordem das atribuições finais preserva a lista antiga. Primeiro conecte o novo nó ao início antigo; depois substitua o ponteiro para o início. Inverter essas instruções faz n->next apontar para o próprio n e perde a cadeia antiga. Para as chegadas 1, 2 e 3, inserções sucessivas no início produzem 1, depois 2 → 1 e depois 3 → 2 → 1 → NULL. A inserção no início inverte a ordem de chegada.

Percorra sem mover o ponteiro que mantém a lista acessível

#include <stdio.h>
void print_list(const node *head) {
    for (const node *p = head; p != NULL; p = p->next)
        printf("%d ", p->number);
}

O ponteiro de percurso p se move enquanto head permanece disponível. O exemplo imprime “3 2 1 ” com um espaço ao final. Para uma lista vazia, o corpo do laço é executado zero vezes. Não há índice de arranjo: cada passo lê uma ligação para encontrar o próximo nó. As alocações podem estar espalhadas pela memória, e inserir um nó não move os nós existentes.

Adicione no fim

bool append(node **head, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    *n = (node){.number = value, .next = NULL};
    node **link = head;
    while (*link != NULL) link = &(*link)->next;
    *link = n;
    return true;
}

link começa no ponteiro para o início da lista da função chamadora. Depois passa ao endereço de cada membro next até designar a ligação nula final. Fazer a atribuição ali também funciona para uma lista vazia. Sem um ponteiro para o fim da lista armazenado, cada inserção no fim precisa primeiro seguir a cadeia existente até o final. Uma função também pode retornar um novo ponteiro para o início, desde que a função chamadora o armazene e trate falhas de alocação sem perder a lista antiga.

Libere os nós em uma ordem segura

void clear_list(node **head) {
    while (*head != NULL) {
        node *old = *head;
        *head = old->next;
        free(old);
    }
}

Leia o sucessor enquanto old ainda existe, mova o ponteiro para o início e então libere o nó antigo. Após o laço, o ponteiro para o início da função chamadora é NULL. Ler old->next após liberar old é uso após a liberação, mesmo que a memória pareça inalterada. Uma ferramenta de verificação de memória pode ajudar a revelar leituras inválidas e alocações esquecidas; a liberação também deve ocorrer após a falha de uma operação posterior.

Buscar em uma lista significa seguir uma ligação por vez. A inserção e a remoção precisam de algo mais: o endereço da ligação que deve mudar. Essa ligação pode ser o ponteiro para o início da lista ou um membro next em um nó anterior.

Busque por valor

Usando o tipo node com membros number e next:

node *find(node *head, int value) {
    for (node *p = head; p != NULL; p = p->next)
        if (p->number == value) return p;
    return NULL;
}

Uma correspondência retorna o endereço do próprio nó. Um valor ausente retorna NULL. Chegar ao 1.000º nó exige seguir 999 ligações a partir do início, mesmo quando você conhece sua posição de antemão.

Mantenha um ponteiro para a ligação que mudará

Um node ** pode apontar para o ponteiro para o início da lista ou para o campo next de um nó. Chame-o de link: *link é o nó atualmente alcançado por essa ligação. Avançar com link = &(*link)->next muda a ligação examinada; isso não altera a lista.

bool insert_sorted(node **head, int value) {
    node **link = head;
    while (*link != NULL && (*link)->number < value)
        link = &(*link)->next;
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->number = value;
    n->next = *link;
    *link = n;
    return true;
}

Inclua <stdbool.h> e <stdlib.h>. A lista de entrada já deve estar em ordem crescente. Pare antes do primeiro valor que não seja menor que o novo, assim os valores duplicados entram antes dos valores iguais. O lado esquerdo de && verifica se há NULL antes de o lado direito desreferenciar o nó. Inverter esses testes desreferenciaria um ponteiro nulo no fim.

Para as inserções 5, 2, 8 e 4, a lista final é 2 → 4 → 5 → 8. Ao inserir 4 em 2 → 5 → 8, link passa do ponteiro para o início da lista para 2.next. O novo nó aponta para 5, e 2.next é redirecionado para o novo nó. Se o novo item for o menor, link ainda designa o ponteiro para o início da lista. No fim, ele designa a ligação nula final.

Desencadeie antes de liberar

bool remove_first(node **head, int value) {
    node **link = head;
    while (*link != NULL && (*link)->number != value)
        link = &(*link)->next;
    if (*link == NULL) return false;
    node *old = *link;
    *link = old->next;
    free(old);
    return true;
}

O laço encontra a ligação de entrada. Salvar seu destino em old mantém o nó disponível enquanto *link é alterado para apontar para o sucessor. Só então o nó removido é liberado. Remover 5 de 2 → 4 → 5 → 8 produz 2 → 4 → 8. Remover 2 em seguida altera o início da lista e deixa 4 → 8. Se o valor estiver ausente, a função retorna falso sem alterar a lista.

Uma versão com dois ponteiros mantém prev e cur. Quando prev é nulo, a correspondência está no início e o ponteiro para o início deve mudar; caso contrário, atualize prev->next. Esquecer o caso do início deixa um ponteiro para memória liberada. A versão com o endereço da ligação trata ambos com a mesma atribuição.

Verifique a entrada vazia, uma lista com um nó, correspondências no primeiro e no último nó e um valor ausente. Para cada alteração, identifique a ligação de entrada, o nó afetado e seu sucessor antes de escrever uma atribuição. Nenhum nó restante deve ficar inacessível, e nenhuma ligação deve apontar para um nó liberado.

A pergunta útil é quais operações seu programa realiza. Arranjos e listas podem conter os mesmos valores, mas acessam e movem esses valores de formas diferentes.

Compare as operações

Uma lista não elimina o trabalho de encontrar uma posição. Inserir após um nó para o qual você já tem um ponteiro é direto, mas a remoção também exige o predecessor ou a ligação que aponta para o nó. Com apenas o endereço do nó, uma lista simplesmente encadeada geralmente precisa ser percorrida desde o início para encontrar essa ligação de entrada.

O armazenamento também importa. Em uma plataforma típica de 64 bits, um nó com um int de 4 bytes e um ponteiro de 8 bytes ocupa 16 bytes após o preenchimento. Para 1.000 inteiros, os nós usam 16.000 bytes mais os dados de controle das alocações; um arranjo contíguo de inteiros usa 4.000 bytes. Percorrer o arranjo costuma ser mais rápido porque valores próximos são armazenados juntos.

Mantenha os metadados da lista juntos

typedef struct {
    node *head;
    node *tail;
    size_t count;
} list_t;

Inicialize uma estrutura que envolve a lista com list_t list = {0};. As condições do estado vazio são head == NULL, tail == NULL e count == 0. Cada inserção ou remoção bem-sucedida deve atualizar a contagem e as ligações. Uma falha de alocação não altera nenhuma delas.

Com um ponteiro para o fim da lista, a inserção no fim após uma alocação verificada usa estas atribuições:

n->next = NULL;
if (list.tail == NULL) list.head = n;
else list.tail->next = n;
list.tail = n;
++list.count;

Aqui, n é um nó inicializado. Para o primeiro nó, os ponteiros para o início e o fim se tornam iguais. Remover o último nó exige recuar o ponteiro para o fim; em uma lista simplesmente encadeada, isso exige o predecessor. Remover o único nó define as duas extremidades como NULL e a contagem como zero.

Faça ligações nos dois sentidos

typedef struct dnode {
    int value;
    struct dnode *prev, *next;
} dnode;
typedef struct {
    dnode *head, *tail;
} dlist;

void unlink_node(dlist *list, dnode *d) {
    if (d->prev != NULL) d->prev->next = d->next;
    else list->head = d->next;
    if (d->next != NULL) d->next->prev = d->prev;
    else list->tail = d->prev;
    free(d);
}

Essa função recebe um nó ainda existente que pertence à lista. As ligações dos dois vizinhos são corrigidas antes de ele ser liberado. Nos casos de extremidade, altera-se o ponteiro para o início ou para o fim em vez de um vizinho ausente. Uma lista duplamente encadeada pode ser percorrida de trás para a frente e permite remover um nó conhecido sem buscar seu predecessor, ao custo de mais um ponteiro por nó e mais ligações para manter.

Libere os dados sob responsabilidade do nó antes do próprio nó

Um word_node pode ser responsável tanto pela alocação do nó quanto pela alocação de uma cadeia de caracteres acessada por word. Salve next, chame free(n->word), depois free(n) e avance para o sucessor salvo. Liberar apenas o nó causa um vazamento da cadeia. Ler n->word após liberar o nó é inválido. A responsabilidade pela liberação indica qual código deve liberar cada alocação, mesmo quando vários ponteiros podem acessá-la.

Uma pilha remove primeiro o item adicionado mais recentemente: último a entrar, primeiro a sair (LIFO). Suas operações definem um tipo abstrato de dados independentemente de os valores serem armazenados em um arranjo ou em nós encadeados. push adiciona no topo, pop remove o topo e peek lê o topo sem removê-lo.

Use um arranjo e uma contagem

#include <stdbool.h>
#define STACK_CAP 100
typedef struct {
    int items[STACK_CAP];
    int top;
} stack;

bool push(stack *s, int value) {
    if (s->top == STACK_CAP) return false;
    s->items[s->top++] = value;
    return true;
}
bool pop(stack *s, int *out) {
    if (s->top == 0) return false;
    *out = s->items[--s->top];
    return true;
}

Inicialize com stack s = {0};. Aqui, top é o número de itens armazenados, então o índice ocupado no topo é top - 1. Uma inserção bem-sucedida escreve na próxima posição livre e aumenta a contagem. Uma remoção bem-sucedida primeiro diminui a contagem e depois lê esse índice. A função chamadora fornece um ponteiro out válido e verifica o resultado antes de usar seu valor.

Empilhar 4, 7 e 1 e depois remover duas vezes retorna 1 e 7, deixando 4. Sem uma verificação de capacidade, uma inserção na pilha cheia escreve em items[STACK_CAP] após o fim. Sem a verificação de pilha vazia, o top com sinal passa de 0 para −1 e a remoção lê items[-1]. Ambos os acessos têm comportamento indefinido.

Use o início de uma lista como topo

Uma pilha encadeada insere no topo adicionando uma alocação verificada ao início da lista. A remoção retira o primeiro nó:

bool pop_linked(node **top, int *out) {
    if (*top == NULL) return false;
    node *old = *top;
    *out = old->number;
    *top = old->next;
    free(old);
    return true;
}

node tem um number inteiro e um ponteiro next. Uma pilha encadeada não tem a capacidade fixa de um arranjo, mas uma inserção pode falhar quando a alocação falha. Ela ainda precisa de verificações de estado vazio e da liberação dos nós restantes ao final.

Verifique pares de delimitadores aninhados

Percorra a entrada da esquerda para a direita. Empilhe cada parêntese, colchete ou chave de abertura. Para cada delimitador de fechamento, retire um da pilha e verifique se os tipos correspondem. Um fechamento sem abertura falha imediatamente. Termine verificando se a pilha está vazia: aberturas restantes também indicam uma falta de correspondência.

O texto “( [ ] { } )” está balanceado. Em “( ]”, o fechamento não corresponde à abertura retirada. Em “( ( )”, uma abertura permanece após o percurso. Uma simples contagem de aberturas e fechamentos não detectaria um aninhamento incorreto como “( [ ) ]”.

Avalie expressões pós-fixadas

Empilhe os números conforme chegam. Para um operador binário, retire primeiro o operando da direita, depois o da esquerda, calcule left operator right e empilhe o resultado. Para “3 4 + 2 *”, + combina 3 e 4 em 7, depois * combina 7 e 2 em 14. Para “9 4 -”, retire 4 como operando da direita e 9 como o da esquerda, produzindo 5. Invertê-los produz −5. Rejeite uma quantidade insuficiente de operandos e exija um único resultado final; a divisão também precisa de um operando da direita diferente de zero.

Chamadas de função usam tempos de vida organizados como uma pilha: uma função chamada retorna antes que sua função chamadora continue. Cada chamada ativa precisa de um registro de ativação, então uma recursão muito profunda pode esgotar a pilha de chamadas mesmo quando as alocações no heap são bem-sucedidas.

Uma fila remove primeiro o item mais antigo: primeiro a entrar, primeiro a sair (FIFO). Enfileirar adiciona ao fim; desenfileirar remove do início. Após enfileirar A, B e C, as duas próximas remoções retornam A e B. Isso é adequado a trabalhos que devem ser tratados na ordem de chegada.

Mantenha as duas extremidades de uma fila encadeada

Usando nós com membros number e next e incluindo <stdbool.h> e <stdlib.h>:

typedef struct { node *head, *tail; } queue;

bool enqueue(queue *q, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    *n = (node){.number = value, .next = NULL};
    if (q->tail == NULL) q->head = n;
    else q->tail->next = n;
    q->tail = n;
    return true;
}
bool dequeue(queue *q, int *out) {
    if (q->head == NULL) return false;
    node *old = q->head;
    *out = old->number;
    q->head = old->next;
    if (q->head == NULL) q->tail = NULL;
    free(old);
    return true;
}

Inicialize com queue q = {0};. A inserção define a ligação do antigo último nó antes de mover o ponteiro para o fim. Para o primeiro nó, também define o ponteiro para o início. A remoção avança o ponteiro para o início. Quando isso remove o único nó, o ponteiro para o fim também deve se tornar NULL. Caso contrário, a próxima inserção escreve por meio de um ponteiro pendente para o fim. Nenhuma das operações precisa percorrer a lista.

Reutilize um arranjo fixo como anel

Uma fila em arranjo simples que sempre remove o índice 0 precisa deslocar seus valores restantes. Um buffer circular mantém um índice para o início e uma contagem de itens:

#define CAP 4
typedef struct {
    char items[CAP];
    unsigned head, count;
} ring;

bool ring_put(ring *q, char value) {
    if (q->count == CAP) return false;
    q->items[(q->head + q->count) % CAP] = value;
    ++q->count;
    return true;
}
bool ring_get(ring *q, char *out) {
    if (q->count == 0) return false;
    *out = q->items[q->head];
    q->head = (q->head + 1) % CAP;
    --q->count;
    return true;
}

Inicialize um anel com {0}. head sempre identifica o primeiro item quando a fila não está vazia. O próximo índice de inserção é o início mais o número de itens, com retorno ao começo por meio de % CAP. Leia o primeiro item antes de mover head. A contagem distingue o estado vazio do cheio sem abrir mão de uma posição.

Rastreie o retorno ao início

Enfileire A, B e C nas posições 0, 1 e 2. Desenfileire A: head passa a 1 e count passa a 2. D entra na posição 3; E entra na posição 0. O arranjo físico agora contém E, B, C, D, mas a ordem lógica de remoção é B, C, D, E. O anel está cheio porque count é 4, embora o início esteja no índice 1.

Outro projeto mantém o índice head e o índice tail da próxima posição livre sem uma contagem. Nesse projeto, índices iguais poderiam significar vazio ou cheio, então uma regra comum deixa uma posição sem uso. Vazio é head == tail; cheio é (tail + 1) % CAP == head. Não misture essa regra com as regras de capacidade da versão baseada em contagem. Filas também permitem visitas a árvores nível por nível, mantendo os nós que aguardam sua vez.

Uma árvore binária dá a cada nó no máximo dois filhos, chamados esquerdo e direito. A raiz é o nó no topo. Uma folha não tem filhos, e um nó junto com todos os seus descendentes é uma subárvore. Um filho ausente e uma árvore vazia são representados por NULL.

Represente os ramos

typedef struct tnode {
    int key;
    struct tnode *left;
    struct tnode *right;
} tnode;

Cada ponteiro para filho leva à raiz de outra árvore. A mesma definição, portanto, descreve uma folha, uma grande árvore ramificada ou uma longa cadeia. A altura conta as arestas no caminho mais longo da raiz até uma folha: uma raiz sozinha tem altura 0. Use −1 para uma árvore vazia, de modo que as duas subárvores vazias de uma folha levem naturalmente à altura 0. Contar níveis daria um a mais.

Aplique a regra a subárvores inteiras

Uma árvore binária de busca, ou BST, ordena as chaves. Para cada nó, todas as chaves em sua subárvore esquerda são menores e todas as chaves em sua subárvore direita são maiores. Armazene cada chave uma vez. Essa condição inclui descendentes distantes. Uma raiz 50 com filho esquerdo 30 e um filho direito 60 abaixo desse 30 é inválida: 60 ainda está na subárvore esquerda de 50.

Insira 50, 30, 70, 20, 40, 60 e 80 em uma BST vazia. A raiz é 50; 30 e 70 são seus filhos. Os filhos de 30 são 20 e 40, e os de 70 são 60 e 80. Cada escolha de ramo preserva os limites herdados dos ancestrais.

Escolha um ramo a cada passo

#include <stddef.h>
tnode *search(tnode *t, int key) {
    while (t != NULL) {
        if (key == t->key) return t;
        if (key < t->key) t = t->left;
        else t = t->right;
    }
    return NULL;
}

Buscar 60 no exemplo visita 50, vai à direita até 70 e depois à esquerda até 60: três nós. Buscar 65 segue o mesmo caminho e depois tenta o filho direito de 60. Esse filho é NULL, então 65 está ausente. Você não precisa examinar a subárvore esquerda de 50 porque todas as chaves nela são menores que 50.

A forma recursiva trata primeiro t == NULL e uma chave correspondente, depois busca no filho escolhido. O teste de subárvore vazia é o caso-base. Sem ele, uma busca malsucedida acaba desreferenciando um ponteiro nulo. A versão com laço para no mesmo limite sem adicionar chamadas recursivas.

Use o formato para entender o trabalho

Uma árvore perfeitamente balanceada com 20 níveis contém 1.048.575 chaves, e uma busca visita no máximo 20 nós. Inserir as chaves já ordenadas 10, 20, 30, 40, 50, por outro lado, cria uma cadeia à direita. Sua altura é 4, e encontrar 50 visita todos os cinco nós. A regra de ordenação de uma BST, por si só, não mantém a árvore baixa. Árvores autobalanceadas, como árvores AVL, reorganizam os ramos para controlar a altura.

Para encontrar um mínimo, siga os filhos à esquerda até que a próxima ligação à esquerda seja NULL. Para encontrar um máximo, siga os filhos à direita. No exemplo com sete nós, essas chaves são 20 e 80. As mesmas escolhas de direção funcionam na raiz de qualquer subárvore porque a regra de ordenação também se aplica ali.

Funções de árvore trabalham em uma subárvore e conectam seu resultado ao pai. Mantenha explícito o caso de subárvore vazia e diferencie operações que alteram ligações de operações que apenas visitam nós.

Insira por meio da ligação da subárvore

Com tnode contendo key, left e right, inclua <stdbool.h> e <stdlib.h>:

bool insert(tnode **link, int key) {
    if (*link == NULL) {
        tnode *n = malloc(sizeof *n);
        if (n == NULL) return false;
        *n = (tnode){.key = key, .left = NULL, .right = NULL};
        *link = n;
        return true;
    }
    if (key < (*link)->key) return insert(&(*link)->left, key);
    if (key > (*link)->key) return insert(&(*link)->right, key);
    return true;
}

Chame com insert(&root, key) e verifique o resultado. Uma chave existente deixa a árvore inalterada e conta como sucesso. O endereço da ligação permite que a inserção atualize a raiz da função chamadora ou um ponteiro para filho. Em uma interface que retorna a raiz, armazene cada resultado: t->left = insert(t->left, key) e root = insert(root, key). Ignorar uma alocação retornada quando a subárvore original estava vazia deixa esse nó sem ligação e causa um vazamento.

Escolha quando visitar a raiz

Para as inserções 50, 30, 70, 20, 40, 60, 80, a saída em ordem é “20 30 40 50 60 70 80”. Em pré-ordem produz “50 30 20 40 70 60 80”; em pós-ordem produz “20 40 30 60 80 70 50”.

void free_tree(tnode *t) {
    if (t == NULL) return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);
}

Após free_tree(root), o código responsável deve definir root = NULL. A função libera primeiro os filhos para poder ler seus endereços a partir do pai ainda existente. O tamanho é zero para uma subárvore vazia, caso contrário é um mais os tamanhos dos dois filhos. A altura é −1 para uma subárvore vazia, caso contrário é um mais a maior altura dos filhos. O exemplo tem tamanho 7 e altura 2.

Remova sem quebrar a ordem

Uma folha se torna NULL. Um nó com um filho é substituído por esse filho. Para dois filhos, copie a menor chave da subárvore direita para o nó e depois remova esse sucessor de sua posição original:

tnode *erase(tnode *t, int key) {
    if (t == NULL) return NULL;
    if (key < t->key) t->left = erase(t->left, key);
    else if (key > t->key) t->right = erase(t->right, key);
    else {
        if (t->left == NULL || t->right == NULL) {
            tnode *child = t->left != NULL ? t->left : t->right;
            free(t);
            return child;
        }
        tnode *s = t->right;
        while (s->left != NULL) s = s->left;
        t->key = s->key;
        t->right = erase(t->right, s->key);
    }
    return t;
}

Chame como root = erase(root, key). Remover 50 do exemplo coloca 60 na raiz e remove o antigo nó 60. A saída em ordem passa a ser “20 30 40 60 70 80”; em pré-ordem passa a ser “60 30 20 40 70 80”. Um sucessor pode ter um filho direito, então sua remoção deve reconectar esse filho.

Para chaves que são palavras, use o sinal de strcmp, não a igualdade de ponteiros, e dê a cada palavra sob responsabilidade da árvore sua própria alocação. Libere a palavra antes de seu nó. A remoção de registros assim com dois filhos também precisa de um plano de responsabilidade pela palavra movida e por qualquer valor associado; copiar um ponteiro responsável pela memória e depois liberar a palavra do nó original deixaria uma chave pendente.

Uma tabela de espalhamento escolhe uma posição inicial a partir de uma chave. Uma função de espalhamento produz um número; reduzir esse número módulo uma quantidade positiva de baldes fornece um índice. O encadeamento separado mantém uma lista encadeada em cada balde, então a busca percorre a cadeia selecionada.

Separe o cálculo do espalhamento da igualdade

Uma função de espalhamento útil é determinística, rápida de calcular e distribui as chaves esperadas entre os baldes. Chaves iguais devem produzir valores de espalhamento iguais. Chaves diferentes ainda podem compartilhar um índice: isso é uma colisão, e toda tabela deve tratá-la. Com mais chaves possíveis que baldes, algumas colisões são inevitáveis.

Para palavras iniciadas por letras em um sistema compatível com ASCII, toupper((unsigned char)word[0]) - 'A' atribui 26 baldes de letras; “Luigi” começa no balde 11. Muitas palavras em inglês começam com “s” e poucas com “x”, então essa regra pode deixar cadeias muito desiguais. A conversão explícita é necessária porque as funções de <ctype.h> exigem um valor de caractere sem sinal ou EOF. Valide a letra inicial e a suposição sobre o conjunto de caracteres antes de usar essa regra de indexação.

Uma função de espalhamento por soma de caracteres também tem pontos fracos. Usando códigos ASCII e dez baldes, “cat” soma 99 + 97 + 116 = 312 e chega ao balde 2; “dog” soma 314 e chega ao balde 4. “act” também soma 312. A adição perde a ordem das letras, então todo rearranjo causa colisão.

Incorpore a ordem dos caracteres ao espalhamento

unsigned long hash_word(const char *word) {
    unsigned long h = 5381;
    const unsigned char *p = (const unsigned char *)word;
    while (*p != '\0') {
        h = h * 33 + *p;
        ++p;
    }
    return h;
}

Esse padrão djb2 usa aritmética sem sinal, cujo estouro sofre redução modular de forma definida. Um estouro com sinal teria comportamento indefinido. Para as cadeias ASCII “cat” e “act”, os valores são 193488125 e 193486013. Reduza com hash_word(word) % N, em que N é a quantidade positiva de baldes. A ordem das letras altera esses valores de espalhamento, embora reduzi-los ainda possa produzir uma colisão.

Se uma tabela trata “Cat” e “cat” como iguais, tanto o cálculo do espalhamento quanto a comparação devem usar a mesma regra para maiúsculas e minúsculas. Ignorar essa diferença apenas durante a comparação pode enviar chaves iguais a baldes diferentes, onde a busca não as comparará. Um resto negativo de um cálculo com sinal também não é adequado como índice de arranjo.

Escolha uma estratégia para colisões

O encadeamento separado armazena todas as colisões na lista encadeada de um balde. A busca compara chaves até encontrar uma correspondência ou chegar ao fim. O endereçamento aberto armazena as entradas no próprio arranjo. Com sondagem linear, uma colisão leva à tentativa da posição seguinte, com retorno ao início no fim. A busca segue a mesma sequência de sondagem, então pode examinar várias posições do arranjo.

Reconstrua os índices quando a tabela crescer

O fator de carga é o número de chaves armazenadas dividido pela quantidade de baldes. Doze chaves em oito baldes resultam em uma média de 1,5 entrada por balde. Dezesseis baldes reduzem essa média para 0,75. Essa média não garante que toda cadeia seja curta; uma função de espalhamento ruim pode colocar todas as chaves juntas.

Um índice de balde depende da quantidade de baldes. Após alocar e inicializar um arranjo maior de baldes, recalcule o índice de cada chave armazenada para a nova quantidade e reconecte-a ali. Copiar os ponteiros antigos para o início das listas nos novos baldes de mesmo número deixa chaves em posições nas quais a nova busca não procurará. Uma tabela com encadeamento pode conter mais entradas que baldes; o endereçamento aberto precisa de posições livres para novas entradas e sondagens confiáveis.

Uma tabela com encadeamento combina um arranjo, ligações de lista, comparação de cadeias de caracteres e responsabilidade pela liberação. Cada entrada é responsável por sua chave copiada. O arranjo de baldes é responsável pelas cadeias, e cada cadeia termina em NULL.

Inicialize os baldes e busque texto

#include <stdbool.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#define N 26
typedef struct entry {
    char *key;
    int count;
    struct entry *next;
} entry;
static entry *table[N];

O armazenamento estático começa com ponteiros nulos em todos os baldes. Um arranjo local, por sua vez, precisa de um inicializador como entry *table[N] = {NULL};. Use a função sem sinal hash_word, que começa em 5381 e incorpora cada byte com o multiplicador 33.

entry *find_word(const char *key) {
    size_t i = hash_word(key) % N;
    for (entry *e = table[i]; e != NULL; e = e->next)
        if (strcmp(e->key, key) == 0) return e;
    return NULL;
}

strcmp testa o texto. e->key == key testaria se os ponteiros designam a mesma posição. Dois buffers separados podem conter palavras iguais, então a igualdade de ponteiros não faz uma busca por palavra.

Conte uma chave existente ou insira uma nova

bool add_word(const char *key) {
    entry *e = find_word(key);
    if (e != NULL) {
        if (e->count == INT_MAX) return false;
        ++e->count;
        return true;
    }
    e = malloc(sizeof *e);
    if (e == NULL) return false;
    e->key = malloc(strlen(key) + 1);
    if (e->key == NULL) {
        free(e);
        return false;
    }
    strcpy(e->key, key);
    e->count = 1;
    size_t i = hash_word(key) % N;
    e->next = table[i];
    table[i] = e;
    return true;
}

A função chamadora fornece uma cadeia de caracteres terminada em nulo. A verificação de INT_MAX informa uma falha antes que uma contagem cause estouro em seu armazenamento int. O byte extra na alocação da cadeia contém '\0'. Se a segunda alocação falhar, libere a entrada ainda não vinculada. O ponteiro para o início da lista do balde muda somente depois que as duas alocações e a inicialização são bem-sucedidas.

Salvar e->key = key manteria o armazenamento da função chamadora. Se a entrada reutilizar repetidamente um buffer, todos os ponteiros salvos poderão mostrar a palavra mais recente. Copiar o texto dá a cada entrada um tempo de vida independente desse buffer. strdup fornece essa operação em POSIX e C23; alocação explícita e strcpy funcionam em C17.

Em um exemplo com dez baldes e soma de caracteres, inserir “cat”, “dog”, “act” deixa “act” → “cat” no balde 2 e “dog” no balde 4. Buscar “tac” percorre o balde 2, compara as duas palavras e chega a NULL. Um balde correspondente é apenas uma posição candidata, não uma prova de que há uma chave igual.

Libere dados associados, nós e ponteiros para o início dos baldes

void clear_table(void) {
    for (size_t i = 0; i < N; ++i) {
        entry *e = table[i];
        while (e != NULL) {
            entry *next = e->next;
            free(e->key);
            free(e);
            e = next;
        }
        table[i] = NULL;
    }
}

Salvar next e liberar a chave acontecem enquanto a entrada ainda existe. Redefinir cada balde permite sua reutilização. Ferramentas de verificação de memória ajudam a verificar os caminhos executados; caminhos de falha de alocação também precisam liberar recursos. A ordem de espalhamento não é uma ordem classificada. Para imprimir em ordem alfabética, reúna as chaves para ordenação ou armazene-as em uma BST.

No endereçamento aberto, a remoção precisa de um marcador de remoção para que a busca continue através de uma posição removida até chaves posteriores que colidiram. Uma posição realmente nunca usada pode encerrar uma busca malsucedida. As sequências de sondagem devem ter limite, e a tabela deve crescer antes que todas as posições estejam ocupadas.