C Academy · Lekcja

Przechodzenie i wyszukiwanie

Przechodzenie po liście

Przechodzenie i wyszukiwanie to bezpłatna lekcja C Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.

Przechodzenie przez listę

Przechodzenie oznacza odwiedzanie każdego węzła w określonej kolejności. Należy rozpocząć od głowy i podążać za wskaźnikami next, aż do osiągnięcia wartości NULL.

Niemal każdy algorytm operujący na liście opiera się na tym prostym przejściu.

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

Schemat przechodzenia

Standardowa pętla korzysta z przesuwanego wskaźnika p: należy zainicjalizować go wartością head, kontynuować, dopóki p nie jest równe NULL, i przesuwać go za pomocą p = p->next.

Podczas przechodzenia nie należy modyfikować samego head, ponieważ spowoduje to utratę początku listy.

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

Zliczanie węzłów

Aby znaleźć długość listy, należy przejść przez wszystkie węzły i zwiększać licznik dla każdego z nich.

Jest to operacja O(n), ponieważ liczba elementów nie jest przechowywana w żadnym miejscu.

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

Sumowanie wartości

Przechodzenie pozwala agregować dane. W tym przypadku sumowane są wszystkie wartości całkowite w liście.

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

Wyszukiwanie wartości

Aby znaleźć określoną wartość, należy przejść przez listę i porównać każdy węzeł. Po znalezieniu dopasowania należy zwrócić węzeł lub jego pozycję, a po dotarciu do końca zasygnalizować niepowodzenie.

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

Znajdowanie pozycji

Czasami potrzebny jest indeks dopasowania, a nie sam węzeł. Podczas przechodzenia należy prowadzić licznik i zwrócić go po znalezieniu wartości.

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

Dostęp do n-tego węzła

Listy wiązane nie obsługują bezpośredniego indeksowania. Aby dotrzeć do pozycji n, trzeba wykonać n kroków od głowy.

Dlatego dostęp swobodny ma złożoność O(n), podczas gdy w tablicy wynosi O(1).

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

Znajdowanie ostatniego węzła

Aby znaleźć ogon, należy przechodzić przez listę, dopóki p->next nie będzie równe NULL. Ten węzeł jest ostatnim elementem.

Należy uważać na pustą listę, w której samo head ma wartość 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;
}

Znajdowanie maksimum

Łącząc wyszukiwanie i agregowanie, można znaleźć największą wartość, śledząc dotychczas najlepszy wynik podczas przechodzenia przez listę.

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

Rekurencyjne przechodzenie

Listę można również przechodzić rekurencyjnie: przetworzyć bieżący węzeł, a następnie wywołać rekurencję dla next.

To eleganckie rozwiązanie wykorzystuje jednak miejsce na stosie proporcjonalne do długości listy, dlatego w przypadku bardzo długich list bezpieczniejsza jest iteracja.

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

Obsługa pustych list

Każda funkcja przechodząca przez listę powinna poprawnie obsługiwać pustą listę (head == NULL).

Standardowa pętla już to zapewnia: warunek p != NULL od razu jest fałszywy, więc treść pętli nie zostaje wykonana.

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

Szybki sprawdzian

Sprawdź swoją wiedzę na temat kosztu przechodzenia przez listę.

Podsumowanie

Nauczył(a) się Pan/Pani przechodzić przez listy i przeszukiwać je:

Schemat przechodzenia: rozpoczęcie od head, wykonywanie pętli, dopóki wartość nie jest równa NULL, oraz przesuwanie za pomocą p = p->next.
Zliczanie, sumowanie i znajdowanie maksimum opierają się na przechodzeniu przez listę.
Wyszukiwanie porównuje każdy węzeł; dostęp za pomocą indeksu ma złożoność O(n).
Przechodzenie może być rekurencyjne, ale w przypadku długich list bezpieczniejsza jest iteracja; zawsze należy obsługiwać pustą listę.

Często zadawane pytania

Czy lekcja „Przechodzenie i wyszukiwanie” jest bezpłatna?

Tak — pełny tekst „Przechodzenie i wyszukiwanie” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Przechodzenie i wyszukiwanie”?

Przechodzenie po liście Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć C Academy?

Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Przechodzenie i wyszukiwanie”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?

Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do C Academy