0Pricing
C Academy · Leçon

Parcours et recherche

Parcourez la liste

Parcours et recherche est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.

Parcourir la liste

Le parcours consiste à visiter chaque nœud dans l’ordre. Commencez à la tête et suivez les pointeurs next jusqu’à atteindre NULL.

Presque tous les algorithmes appliqués aux listes reposent sur ce parcours simple.

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

Le schéma de parcours

La boucle classique utilise un pointeur mobile p : initialisez-le avec head, continuez tant que p n’est pas égal à NULL, puis avancez avec p = p->next.

Ne modifiez jamais head lui-même pendant le parcours, sinon vous perdez le début de la liste.

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

Compter les nœuds

Pour déterminer la longueur, parcourez la liste et incrémentez un compteur pour chaque nœud.

Il s’agit d’une opération en O(n), car le nombre d’éléments n’est stocké nulle part.

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

Additionner les valeurs

Le parcours vous permet d’agréger des données. Ici, nous additionnons toutes les valeurs entières de la liste.

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

Rechercher une valeur

Pour trouver une valeur, parcourez la liste et comparez chaque nœud. Renvoyez le nœud (ou sa position) lorsque vous trouvez une correspondance, ou signalez l’échec si vous atteignez la fin.

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

Trouver une position

Vous pouvez parfois vouloir l’index d’une correspondance plutôt que le nœud. Conservez un compteur pendant le parcours et renvoyez-le lorsque la valeur est trouvée.

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

Accéder au n-ième nœud

Les listes chaînées ne permettent pas l’indexation directe. Pour atteindre la position n, vous devez avancer n fois depuis la tête.

C’est pourquoi l’accès aléatoire est en O(n), contre O(1) pour un tableau.

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

Trouver le dernier nœud

Pour obtenir la queue, parcourez la liste jusqu’à ce que p->next soit égal à NULL. Ce nœud est le dernier.

Soyez prudent avec une liste vide, dans laquelle head lui-même vaut 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;
}

Trouver le maximum

En combinant recherche et agrégation, vous pouvez trouver la plus grande valeur en conservant la meilleure valeur rencontrée pendant le parcours.

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

Parcours récursif

Les listes peuvent également être parcourues de manière récursive : traitez le nœud courant, puis appelez récursivement la fonction sur next.

Cette approche est élégante, mais utilise une mémoire de pile proportionnelle à la longueur de la liste : l’itération est donc plus sûre pour les listes très longues.

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

Gérer les listes vides

Toute fonction de parcours doit gérer correctement une liste vide (head == NULL).

La boucle standard le fait déjà : la condition p != NULL est immédiatement fausse, et le corps n’est donc jamais exécuté.

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

Vérification rapide

Vérifiez votre compréhension du coût du parcours d’une liste.

Récapitulatif

Vous avez appris à parcourir les listes et à y effectuer des recherches :

  • Schéma de parcours : commencez à head, bouclez tant que la valeur n’est pas NULL, puis avancez avec p = p->next.
  • Le comptage, la somme et la recherche du maximum reposent tous sur le parcours.
  • La recherche compare chaque nœud ; l’accès par index est en O(n).
  • Le parcours peut être récursif, mais l’itération est plus sûre pour les longues listes ; gérez toujours le cas d’une liste vide.

Questions Fréquemment Posées

La leçon « Parcours et recherche » est-elle gratuite ?

Oui — le texte complet de « Parcours et recherche » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Parcours et recherche » ?

Parcourez la liste Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer C Academy ?

Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.

Combien de temps prend la leçon « Parcours et recherche » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon C Academy ?

Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Listes simplement chaînées
  2. Insertion et suppression
  3. Parcours et recherche
  4. Listes doublement chaînées
← Retour à C Academy