Указатели, узлы и связные списки

Зачем нужен список

Массив — простая и понятная структура, но у него два ограничения, которые мешают в задачах вроде лабораторной работы № 3.

Первое ограничение — непрерывный блок памяти. Статический массив вроде int a[100] требует заранее знать размер. Динамический массив, который растёт через malloc/realloc, этой проблемы полностью не снимает: ему всё равно нужен непрерывный участок памяти, а при увеличении может потребоваться перевыделить блок и скопировать данные. Часто в реальной жизни число записей заранее неизвестно и получается «на ходу». Резервировать «на всякий случай» массив побольше — и расточительно, и ненадёжно: вдруг в следующий раз записей окажется больше.

Второе — дорогая вставка и удаление в середину. Чтобы вставить элемент, все стоящие за ним приходится сдвигать вправо; при удалении — влево. Каждый сдвиг — это лишние пересылки данных, а при большом количестве элементов — заметная трата времени.

Связный список решает обе проблемы. Вместо одного непрерывного куска памяти он состоит из отдельных узлов, каждый из которых живёт в своём месте и «знает» адрес следующего. Чтобы вставить или удалить узел, достаточно поменять один-два адреса — сдвигать соседей не нужно. Память под узел выделяется ровно тогда, когда он появился, и освобождается, когда он больше не нужен.

Аналогия. Массив — как полка с пронумерованными ячейками: сразу видно, где лежит третий предмет. Список — как цепочка вагонеток: в каждой лежит груз, а крючок держит следующую. Чтобы добраться до третьей, нужно пройти от первой через вторую.

Узел как самоссылочная структура

Узел хранит полезные данные и адрес следующего узла. Для ЛР 3 данные — это структура Student:

typedef struct
{
    int id;         /* уникальный номер */
    int course;     /* курс, от 1 до 6 */
    double score;   /* оценка, от 0.0 до 5.0 */
} Student;

typedef struct Node
{
    Student data;       /* полезные данные */
    struct Node *next;  /* адрес следующего узла, NULL — конец списка */
} Node;

Структура Node содержит указатель struct Node *next — на такую же структуру. Это самоссылочная структура: она описывает тип, внутри которого есть указатель на него же. Без этого поля цепочку построить нельзя — узел должен «знать», где лежит следующий.

Обратите внимание на запись struct Node *next внутри typedef. До конца объявления имя Node ещё не введено, поэтому приходится писать полное имя struct Node.

Весь список задаётся одним указателем на первый узел — головой:

Node *head = NULL;   /* пустой список */

Пустой список — это head == NULL. Узлов нет, и читать из него нечего.

Динамическая память: malloc и free

Узел нельзя создать как локальную переменную функции и вернуть на неё указатель. Локальные переменные живут на стеке и исчезают, когда функция завершается, — возвращённый указатель станет «висячим»: он будет смотреть в память, которой функция уже не владеет.

/* НЕВЕРНО: node исчезнет, когда функция завершится */
Node *bad_make_node(Student s)
{
    Node node;            /* локальная переменная, живёт на стеке */
    node.data = s;
    node.next = NULL;
    return &node;         /* возвращаем адрес мёртвой переменной */
}

Узел живёт дольше, чем вызвавшая его функция, поэтому память под него выделяют динамически, из кучи, функцией malloc:

Node *make_node(Student s)
{
    Node *node = malloc(sizeof(*node));
    if (node == NULL)
    {
        return NULL;      /* память не выделилась */
    }

    node->data = s;
    node->next = NULL;
    return node;
}

Разберём детали.

• sizeof(*node) — размер узла, а не указателя. Запись sizeof(Node *) дала бы всего 8 байтов (размер адреса), и next или часть data оказались бы за границей блока. Форма sizeof(*node) хороша тем, что не зависит от типа: изменится Node — код останется верным.
• Проверка if (node == NULL) обязательна. Если памяти не хватило, malloc возвращает NULL, и любая запись node->data упадёт. В ЛР 3 при этом нужно вывести сообщение в stderr и завершиться с ненулевым кодом.
• node->data = s; node->next = NULL; — инициализация полей. Сразу задаём next = NULL, чтобы узел был законченным и безопасным: «висящий» неинициализированный next — источник трудноуловимых ошибок.

Память, выделенная malloc, принадлежит программе до явного free. Владелец блока — тот, кто будет его освобождать. В ЛР 3 владельцем узлов списка обычно становится main: именно он в конце вызывает функцию освобождения. Забытый free — это утечка памяти: блок выделен, но указатель на него потерян, и вернуть его уже нельзя.

Обход списка

Чтобы обработать все узлы, нужно пройти по цепочке указателей next:

for (Node *p = head; p != NULL; p = p->next)
{
    printf("%d %d %.2f\n", p->data.id, p->data.course, p->data.score);
}

Условие остановки — p != NULL, переход — p = p->next. Указатель p по очереди смотрит на первый, второй, … и, наконец, становится NULL — цикл завершается.

Частая ошибка — написать p->next != NULL как условие цикла. Тогда тело выполняется, пока следующий узел существует, и последний узел остаётся необработанным: когда p дойдёт до него, p->next уже NULL, и цикл остановится, не зайдя в тело. Для задач, где нужно обработать каждый узел (печать, подсчёт, поиск), условие всегда p != NULL.

Важно не двигать сам head. Если в обходе написать head = head->next, голова уедет и список будет потерян. Для обхода заводят отдельный указатель-курсор p, а head остаётся нетронутым. То же правило работает и внутри функций: меняя список, не теряйте исходную голову без необходимости.

Как передавать голову в функцию

Функция может изменить голову списка (например, добавить узел в начало или удалить первый). Но параметры в C передаются по значению: функция получает копию аргумента. Поэтому простой параметр Node *head менять снаружи бесполезно — изменения затронут только копию.

Есть два равноправных способа. Выберите один и придерживайтесь его во всей программе.

Способ 1 — вернуть новый head. Функция возвращает новую голову, а вызывающий код присваивает её обратно:

Node *push_front(Node *head, Student s)
{
    Node *node = make_node(s);
    if (node == NULL)
    {
        return head;      /* не выделилось — список не изменился */
    }

    node->next = head;    /* прицепляем старый список к новому узлу */
    return node;          /* новый узел стал головой */
}

Вызов: head = push_front(head, s);.

Способ 2 — указатель на голову Node **. Функция получает адрес переменной head и может менять её напрямую:

void push_front(Node **head, Student s)
{
    Node *node = make_node(s);
    if (node == NULL)
    {
        return;
    }

    node->next = *head;
    *head = node;
}

Вызов: push_front(&head, s);.

Здесь Node ** — это «указатель на указатель». Функция разыменовывает его и получает саму переменную head, которую и меняет. Это тот же приём, что и swap(&x, &y) для обмена значений.

Дальше в статьях по односвязному и двусвязному списку мы будем использовать способ 1 (возврат нового head): он нагляднее читается, а при ошибке легко «оставить всё как было». Главное — не смешивать два стиля в одном проекте, иначе легко запутаться в сигнатурах.

Полный мини-пример

Соберём всё вместе: создание узла, добавление в начало, печать и освобождение списка из структур Student.

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int id;
    int course;
    double score;
} Student;

typedef struct Node
{
    Student data;
    struct Node *next;
} Node;

/* Прототипы — до main */
Node *make_node(Student s);
Node *push_front(Node *head, Student s);
void print_list(const Node *head);
void free_list(Node *head);

int main(void)
{
    Student s1 = { 1, 1, 4.80 };
    Student s2 = { 2, 2, 3.20 };
    Student s3 = { 3, 3, 4.00 };

    Node *head = NULL;
    head = push_front(head, s3);
    head = push_front(head, s2);
    head = push_front(head, s1);

    print_list(head);   /* 1 1 4.80 / 2 2 3.20 / 3 3 4.00 */

    free_list(head);
    head = NULL;        /* после free голову обнуляют */
    return 0;
}

Node *make_node(Student s)
{
    Node *node = malloc(sizeof(*node));
    if (node == NULL)
    {
        return NULL;
    }

    node->data = s;
    node->next = NULL;
    return node;
}

Node *push_front(Node *head, Student s)
{
    Node *node = make_node(s);
    if (node == NULL)
    {
        return head;
    }

    node->next = head;
    return node;
}

void print_list(const Node *head)
{
    for (const Node *p = head; p != NULL; p = p->next)
    {
        printf("%d %d %.2f\n", p->data.id, p->data.course, p->data.score);
    }
}

void free_list(Node *head)
{
    while (head != NULL)
    {
        Node *next = head->next;   /* СНАЧАЛА запоминаем следующий узел */
        free(head);
        head = next;
    }
}

Разберём ключевые места.

• Добавление в начало работает за две строки: node->next = head прицепляет старый список к новому узлу, а return node делает новый узел головой. Порядок важен: сначала цепляем, потом переставляем голову. Наоборот нельзя — старая голова будет потеряна.
• Печать принимает const Node *: функция только читает, ничего не меняет. const — защита от случайной записи.
• В free_list сначала сохраняют next = head->next, и только потом free(head). Если освободить узел раньше, чем запомнить следующий, читать head->next будет уже нельзя — классическая ошибка. После освобождения вызывающий код обнуляет свою голову.

Как это связано с ЛР 3

В ЛР 3 программа читает из input.txt число N, затем N строк вида id course score, строит из них односвязный список Student, выполняет преобразование по варианту и пишет результат в output.txt. Каркас этой логики выглядит так (не полное решение — только скелет, показывающий место списка):

Node *input_list(FILE *in);              /* читает N и строит список; NULL — пустой список или ошибка */
void print_list(FILE *out, const Node *head);
Node *transform(Node *head);             /* реализует задание варианта */
void free_list(Node *head);

int main(void)
{
    FILE *in = fopen("input.txt", "r");
    if (in == NULL)
    {
        /* сообщение в stderr и завершение с ненулевым кодом */
        return 1;
    }

    Node *head = input_list(in);         /* сама читает N и строит список */
    if (fclose(in) != 0)
    {
        free_list(head);
        return 1;
    }

    head = transform(head);

    FILE *out = fopen("output.txt", "w");
    if (out == NULL)
    {
        free_list(head);
        return 1;
    }

    print_list(out, head);
    if (fclose(out) != 0)
    {
        free_list(head);
        return 1;
    }

    free_list(head);
    return 0;
}

Главное в этом каркасе — порядок действий: прочитать, построить список через malloc в цикле, преобразовать, вывести, освободить. Каждый узел выделяется отдельным malloc, поэтому массив на весь набор не нужен и не разрешён. Функция преобразования возвращает новую голову, а освобождение происходит ровно один раз, в конце.

Проверка ошибок ввода и выделения памяти живёт внутри input_list: она сама читает N, проверяет каждый fscanf и каждый malloc, а при сбое сообщает в stderr и завершает работу (или возвращает признак ошибки). Здесь она для краткости не раскрыта. Отдельно учитывайте граничный случай N = 0: пустой список — это законный результат, и head == NULL в таком случае не является ошибкой.

Обратите внимание: ввод/вывод в ЛР 3 идёт через файлы (fopen, fscanf, fprintf), а не через консоль, и все результаты — только числа. Проверки fopen, fscanf и malloc обязательны. Это правило лабы — в статьях мы его не меняем.

Частые ошибки

Документация

• Структуры
• Указатели
• Доступ к членам структуры
• malloc
• free

Что запомнить

1. Список — цепочка узлов; каждый узел хранит данные и адрес следующего.
2. Узел — самоссылочная структура: поле next указывает на такой же узел.
3. Память под узел выделяют malloc, а не локальной переменной; результат проверяют на NULL.
4. sizeof(*node) — размер узла, а не указателя.
5. Обход: for (Node *p = head; p != NULL; p = p->next); head при обходе не двигают.
6. Голову меняют либо возвратом нового head, либо через Node ** — выберите один стиль.
7. Перед free узла сохраните его next; в конце обнулите голову.