0Pricing
C Academy · Aula

Percurso e busca

Percorra a lista.

Percurso e busca é uma aula grátis de C Academy no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de C Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de C Academy inclui 4 aulas no total.

Percorrendo a lista

Percorrer significa visitar cada nó em ordem. Você começa na cabeça e segue os ponteiros next até chegar a NULL.

Quase todo algoritmo para listas se baseia nesse percurso simples.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(10);
    head->next = make(20);
    for (struct Node *p = head; p != NULL; p = p->next)
        printf("%d ", p->value);
    printf("\n");
    return 0;
}

O padrão de percurso

O laço padrão usa um ponteiro móvel p: inicialize-o com head, continue enquanto p não for NULL e avance com p = p->next.

Nunca modifique a própria head enquanto percorre a lista, pois você perderá o início dela.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    struct Node *p = head;
    while (p) { printf("%d ", p->value); p = p->next; }
    printf("\n");
    return 0;
}

Contando nós

Para descobrir o comprimento, percorra a lista e incremente um contador para cada nó.

Essa é uma operação O(n), pois a quantidade de nós não é armazenada em nenhum lugar.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int length(struct Node *head) {
    int n = 0;
    for (struct Node *p = head; p; p = p->next) n++;
    return n;
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    printf("length = %d\n", length(head));
    return 0;
}

Somando valores

Percorrer a lista permite agregar dados. Aqui, somamos todos os valores inteiros da lista.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(5);
    head->next = make(10);
    int sum = 0;
    for (struct Node *p = head; p; p = p->next) sum += p->value;
    printf("sum = %d\n", sum);
    return 0;
}

Procurando um valor

Para encontrar um valor, percorra a lista e compare cada nó. Retorne o nó (ou a posição dele) quando encontrar uma correspondência ou sinalize a falha ao chegar ao final.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

struct Node *find(struct Node *head, int v) {
    for (struct Node *p = head; p; p = p->next)
        if (p->value == v) return p;
    return NULL;
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    printf("found 2: %d\n", find(head, 2) != NULL);
    printf("found 9: %d\n", find(head, 9) != NULL);
    return 0;
}

Encontrando uma posição

Às vezes, você deseja o índice de uma correspondência em vez do nó. Mantenha um contador durante o percurso e retorne-o quando o valor for encontrado.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int index_of(struct Node *head, int v) {
    int i = 0;
    for (struct Node *p = head; p; p = p->next, i++)
        if (p->value == v) return i;
    return -1;
}

int main(void) {
    struct Node *head = make(7);
    head->next = make(8);
    printf("%d\n", index_of(head, 8));
    return 0;
}

Acessando o n-ésimo nó

Listas encadeadas não têm indexação direta. Para alcançar a posição n, você precisa avançar n vezes a partir da cabeça.

Por isso, o acesso aleatório custa O(n), em comparação com O(1) em um vetor.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

struct Node *at(struct Node *head, int n) {
    struct Node *p = head;
    for (int i = 0; i < n && p; i++) p = p->next;
    return p;
}

int main(void) {
    struct Node *head = make(10);
    head->next = make(20);
    head->next->next = make(30);
    printf("%d\n", at(head, 2)->value);
    return 0;
}

Encontrando o último nó

Para obter a cauda, percorra a lista até que p->next seja NULL. Esse nó é o último.

Tenha cuidado com uma lista vazia, na qual a própria head é NULL.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    head->next->next = make(3);
    struct Node *p = head;
    while (p->next) p = p->next;
    printf("last = %d\n", p->value);
    return 0;
}

Encontrando o maior valor

Combinando busca e agregação, você pode encontrar o maior valor mantendo o melhor resultado encontrado durante o percurso.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(3);
    head->next = make(9);
    head->next->next = make(5);
    int best = head->value;
    for (struct Node *p = head->next; p; p = p->next)
        if (p->value > best) best = p->value;
    printf("max = %d\n", best);
    return 0;
}

Percurso recursivo

As listas também podem ser percorridas recursivamente: processe o nó atual e depois faça a chamada recursiva para next.

Essa abordagem é elegante, mas usa espaço na pilha proporcional ao comprimento da lista; por isso, a iteração é mais segura para listas muito longas.

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

struct Node { int value; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->next=NULL;return n;}

void print_rec(struct Node *p) {
    if (!p) { printf("\n"); return; }
    printf("%d ", p->value);
    print_rec(p->next);
}

int main(void) {
    struct Node *head = make(1);
    head->next = make(2);
    print_rec(head);
    return 0;
}

Tratar listas vazias

Toda função de percurso deve tratar uma lista vazia (head == NULL) adequadamente.

O laço padrão já faz isso: a condição p != NULL é falsa imediatamente, portanto o corpo nunca é executado.

#include <stdio.h>

struct Node { int value; struct Node *next; };

int length(struct Node *head) {
    int n = 0;
    for (struct Node *p = head; p; p = p->next) n++;
    return n;
}

int main(void) {
    struct Node *head = NULL;
    printf("empty length = %d\n", length(head));
    return 0;
}

Verificação rápida

Teste sua compreensão do custo do percurso de listas.

Recapitulação

Você aprendeu a percorrer e pesquisar listas:

  • O padrão de percurso: comece em head, repita enquanto não for NULL e avance com p = p->next.
  • Contar, somar e encontrar o maior valor são operações baseadas no percurso.
  • A busca compara cada nó; o acesso por índice custa O(n).
  • O percurso pode ser recursivo, mas a iteração é mais segura para listas longas; sempre trate o caso de lista vazia.

Perguntas Frequentes

A aula “Percurso e busca” é grátis?

Sim — o texto completo de “Percurso e busca” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de C Academy, atualize para CoddyKit PRO. O curso de C Academy inclui 4 aulas no total.

O que vou aprender em “Percurso e busca”?

Percorra a lista. Você pratica C Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar C Academy?

Nenhuma experiência prévia é necessária. C Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.

Quanto tempo leva a aula “Percurso e busca”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de C Academy?

Sim. Cada aula de C Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Listas simplesmente encadeadas
  2. Inserção e exclusão
  3. Percurso e busca
  4. Listas duplamente encadeadas
← Voltar para C Academy