0Pricing
C Academy · Урок

Обход и поиск

Обходите список

«Обход и поиск» — бесплатный урок C Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.

Обход списка

Обход означает посещение каждого узла по порядку. Начните с головы и переходите по указателям next, пока не достигнете 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(10);
    head->next = make(20);
    for (struct Node *p = head; p != NULL; p = p->next)
        printf("%d ", p->value);
    printf("\n");
    return 0;
}

Шаблон обхода

Канонический цикл использует перемещающийся указатель p: инициализируйте его значением head, продолжайте цикл, пока p не равен NULL, и перемещайте указатель с помощью p = p->next.

Никогда не изменяйте саму head во время обхода, иначе потеряете начало списка.

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

Подсчёт узлов

Чтобы найти длину списка, обойдите его и увеличивайте счётчик для каждого узла.

Это операция O(n), поскольку количество узлов нигде не хранится.

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

Суммирование значений

Обход позволяет агрегировать данные. Здесь мы складываем все целочисленные значения списка.

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

Поиск значения

Чтобы найти значение, обойдите список и сравните каждый узел. При совпадении верните узел или его позицию, а если достигнете конца, сообщите о неудаче.

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

Поиск позиции

Иногда вместо узла нужно получить индекс совпадения. Ведите счётчик во время обхода и верните его, когда значение будет найдено.

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

Доступ к n-му узлу

В связных списках нет прямой индексации. Чтобы достичь позиции n, необходимо сделать n шагов от головы.

Поэтому произвольный доступ выполняется за O(n), тогда как для массива — за 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;
}

Поиск последнего узла

Чтобы получить хвост списка, проходите по нему, пока p->next не станет равным NULL. Этот узел и будет последним.

Будьте осторожны с пустым списком: в нём сама 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;
}

Поиск максимального значения

Объединив поиск и агрегирование, можно найти наибольшее значение, отслеживая текущий лучший результат во время обхода.

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

Рекурсивный обход

Списки также можно обходить рекурсивно: обработать текущий узел, а затем рекурсивно обработать next.

Это элегантный подход, но он использует стековую память, пропорциональную длине списка, поэтому для очень длинных списков безопаснее использовать итерацию.

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

Обработка пустых списков

Каждая функция обхода должна корректно обрабатывать пустой список (head == NULL).

Стандартный цикл уже делает это: условие p != NULL сразу ложно, поэтому тело цикла не выполняется.

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

Быстрая проверка

Проверьте своё понимание стоимости обхода списка.

Итоги

Вы научились выполнять обход и поиск в списках:

  • Шаблон обхода: начать с head, выполнять цикл, пока указатель не равен NULL, и перемещать его с помощью p = p->next.
  • Подсчёт, суммирование и поиск максимума строятся на обходе списка.
  • Поиск сравнивает каждый узел; доступ по индексу выполняется за O(n).
  • Обход может быть рекурсивным, но для длинных списков безопаснее использовать итерацию; всегда обрабатывайте пустой список.

Часто задаваемые вопросы

Урок «Обход и поиск» бесплатный?

Да — полный текст урока «Обход и поиск» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.

Чему я научусь в уроке «Обход и поиск»?

Обходите список Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C Academy?

Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Обход и поиск»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C Academy?

Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Односвязные списки
  2. Вставка и удаление
  3. Обход и поиск
  4. Двусвязные списки
← Назад к C Academy