C Academy · Lektion

Durchlaufen und Suchen

Die Liste durchlaufen

Durchlaufen und Suchen ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Die Liste durchlaufen

Traversal bedeutet, jeden Knoten in der richtigen Reihenfolge zu besuchen. Sie beginnen am Kopf und folgen den next-Zeigern, bis Sie NULL erreichen.

Fast jeder Algorithmus für Listen baut auf diesem einfachen Durchlauf auf.

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

Das Durchlaufmuster

Die übliche Schleife verwendet einen sich bewegenden Zeiger p: Initialisieren Sie ihn mit head, führen Sie die Schleife aus, solange p nicht NULL ist, und rücken Sie ihn mit p = p->next weiter.

Ändern Sie beim Durchlaufen niemals head selbst, da Sie sonst den Anfang der Liste verlieren.

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

Knoten zählen

Um die Länge zu bestimmen, durchlaufen Sie die Liste und erhöhen für jeden Knoten einen Zähler.

Dies ist eine O(n)-Operation, da die Anzahl nirgendwo gespeichert wird.

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

Werte summieren

Durchlaufen ermöglicht es Ihnen, Daten zu aggregieren. Hier addieren wir alle ganzzahligen Werte in der 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;
}

Nach einem Wert suchen

Um einen Wert zu finden, durchlaufen Sie die Liste und vergleichen jeden Knoten. Geben Sie den Knoten oder seine Position zurück, sobald Sie eine Übereinstimmung finden, oder signalisieren Sie einen Fehlschlag, wenn Sie das Ende erreichen.

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

Eine Position finden

Manchmal benötigen Sie den Index einer Übereinstimmung statt des Knotens. Führen Sie beim Durchlaufen einen Zähler mit und geben Sie ihn zurück, sobald der Wert gefunden wurde.

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

Auf den n-ten Knoten zugreifen

Verkettete Listen bieten keinen direkten Indexzugriff. Um die Position n zu erreichen, müssen Sie vom Kopf aus n Schritte gehen.

Deshalb ist der wahlfreie Zugriff O(n), während er bei einem Array O(1) benötigt.

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

Den letzten Knoten finden

Um das Ende zu erreichen, laufen Sie weiter, bis p->next gleich NULL ist. Dieser Knoten ist der letzte.

Beachten Sie eine leere Liste: In diesem Fall ist bereits head gleich 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;
}

Das Maximum finden

Indem Sie Suche und Aggregation kombinieren, können Sie den größten Wert finden, indem Sie während des Durchlaufs das bisher beste Ergebnis speichern.

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

Rekursives Durchlaufen

Listen können auch rekursiv durchlaufen werden: Verarbeiten Sie den aktuellen Knoten und rufen Sie anschließend die Funktion für next rekursiv auf.

Das ist elegant, benötigt jedoch Stack-Speicher proportional zur Länge der Liste. Für sehr lange Listen ist eine iterative Lösung daher sicherer.

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

Leere Listen abfangen

Jede Funktion zum Durchlaufen sollte eine leere Liste (head == NULL) ordnungsgemäß behandeln.

Die Standardschleife erledigt dies bereits: Die Bedingung p != NULL ist sofort falsch, daher wird der Schleifenrumpf nie ausgeführt.

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

Kurztest

Testen Sie Ihr Verständnis der Kosten beim Durchlaufen einer Liste.

Zusammenfassung

Sie haben gelernt, Listen zu durchlaufen und zu durchsuchen:

Das Durchlaufmuster: bei head beginnen, wiederholen, solange der Zeiger nicht NULL ist, und mit p = p->next weiterrücken.
Zählen, Summieren und das Finden des Maximums bauen alle auf dem Durchlaufen auf.
Bei der Suche wird jeder Knoten verglichen; der Indexzugriff ist O(n).
Das Durchlaufen kann rekursiv erfolgen, bei langen Listen ist eine iterative Lösung jedoch sicherer. Behandeln Sie immer auch den Fall einer leeren Liste.

Häufig gestellte Fragen

Ist die Lektion „Durchlaufen und Suchen“ kostenlos?

Ja — der vollständige Text von „Durchlaufen und Suchen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Durchlaufen und Suchen“?

Die Liste durchlaufen Du übst C Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um C Academy zu starten?

Keine Vorkenntnisse erforderlich. C Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.

Wie lange dauert die Lektion „Durchlaufen und Suchen“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser C Academy-Lektion Code schreiben und ausführen?

Ja. Jede C Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

← Zurück zu C Academy