C Academy · Lezione

Attraversamento e ricerca

Scorrere la lista

Lezione 3 di 413 passaggi

Attraversamento e ricerca è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.

Attraversare la lista

Attraversare una lista significa visitare ogni nodo in ordine. Si parte dalla testa e si seguono i puntatori next fino a raggiungere NULL.

Quasi ogni algoritmo sulle liste si basa su questo semplice attraversamento.

#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;
}

Lo schema dell'attraversamento

Il ciclo canonico utilizza un puntatore mobile p: lo inizializza a head, continua finché p non è NULL e lo fa avanzare con p = p->next.

Non modifichi mai direttamente head durante l'attraversamento, altrimenti perderà l'inizio della 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(1);
    head->next = make(2);
    struct Node *p = head;
    while (p) { printf("%d ", p->value); p = p->next; }
    printf("\n");
    return 0;
}

Contare i nodi

Per trovare la lunghezza, attraversi la lista e incrementi un contatore per ogni nodo.

Si tratta di un'operazione O(n), perché il conteggio non è memorizzato da nessuna parte.

#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;
}

Sommare i valori

L'attraversamento consente di aggregare i dati. In questo caso sommiamo tutti i valori interi della 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;
}

Cercare un valore

Per trovare un valore, attraversi la lista e confronti ogni nodo. Restituisca il nodo, o la sua posizione, quando trova una corrispondenza, oppure segnali il fallimento se raggiunge la fine.

#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;
}

Trovare una posizione

A volte è necessario ottenere l'indice della corrispondenza anziché il nodo. Mantenga un contatore durante l'attraversamento e lo restituisca quando trova il valore.

#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;
}

Accedere all'ennesimo nodo

Le liste concatenate non supportano l'indicizzazione diretta. Per raggiungere la posizione n, deve avanzare di n passi dalla testa.

Per questo l'accesso casuale è O(n), rispetto a O(1) per un array.

#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;
}

Trovare l'ultimo nodo

Per ottenere la coda, attraversi la lista finché p->next non è NULL. Quel nodo è l'ultimo.

Faccia attenzione alle liste vuote, in cui anche 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;
}

Trovare il valore massimo

Combinando ricerca e aggregazione, può trovare il valore più grande mantenendo il miglior valore corrente durante l'attraversamento.

#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;
}

Attraversamento ricorsivo

È possibile attraversare le liste anche ricorsivamente: elabori il nodo corrente, quindi richiami la funzione su next.

È elegante, ma utilizza spazio nello stack proporzionale alla lunghezza della lista; perciò l'iterazione è più sicura per liste molto lunghe.

#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;
}

Gestire le liste vuote

Ogni funzione di attraversamento dovrebbe gestire correttamente una lista vuota (head == NULL).

Il ciclo standard lo fa già: la condizione p != NULL è immediatamente falsa, quindi il corpo non viene mai eseguito.

#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 rapida

Verifichi la Sua comprensione del costo dell'attraversamento delle liste.

Rispondi nella lezione interattiva

Riepilogo

Ha imparato ad attraversare e cercare nelle liste:

Schema dell'attraversamento: parta da head, esegua il ciclo finché il valore non è NULL e avanzi con p = p->next.
Il conteggio, la somma e la ricerca del massimo si basano tutti sull'attraversamento.
La ricerca confronta ogni nodo; l'accesso tramite indice è O(n).
L'attraversamento può essere ricorsivo, ma l'iterazione è più sicura per le liste lunghe; gestisca sempre il caso della lista vuota.

Gratis per iniziare

Impara C con un tutor IA — gratis

Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.

Corsi: 39
Lezioni: 144

Inizia a imparare gratis Visualizza il corso completo

Domande Frequenti

La lezione «Attraversamento e ricerca» è gratuita?

Sì — il testo completo di «Attraversamento e ricerca» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.

Cosa imparerò in «Attraversamento e ricerca»?

Scorrere la lista Eserciti C Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare C Academy?

Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.

Quanto tempo richiede la lezione «Attraversamento e ricerca»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione C Academy?

Sì. Ogni lezione C Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

← Torna a C Academy