Раздел 17 — Динамическая память и связные структуры

До сих пор размер каждого массива был известен при компиляции: int a[1000]. Это неудобно: сколько строк в файле или чисел во вводе, становится ясно только при работе программы. Массив «с запасом» тратит память впустую и всё равно может оказаться мал. У программы на C три области для данных:

Блок в куче не привязан к функции: его можно создать в одной функции, вернуть указатель и освободить в другой. Это и даёт свободу, и создаёт ответственность: у каждого блока должен быть владелец — код, который его освободит ровно один раз.

Функции объявлены в stdlib.h и работают с размером в байтах:

• malloc(size) — блок из size байтов, содержимое не определено. Размер массива — n * sizeof *p: если поменять тип p, размер поменяется сам.
• calloc(n, size) — блок под n элементов, заполненный нулями.
• realloc(p, size) — изменить размер блока; старое содержимое сохраняется, но блок может переехать по другому адресу.
• free(p) — вернуть блок. free(NULL) ничего не делает.

Если памяти нет, первые три возвращают NULL — его проверяют каждый раз.

int *squares = malloc((size_t)n * sizeof *squares);
if (squares == NULL) {
    fprintf(stderr, "out of memory\n");
    return 1;
}
…
/* realloc: результат — во временный указатель */
int *bigger = realloc(squares, 2 * (size_t)n * sizeof *squares);
if (bigger == NULL) {
    free(squares);                       /* старый блок цел — освободить его */
    …
}
squares = bigger;
…
free(squares);
squares = NULL;                          /* висячий указатель больше не опасен */

malloc 5 ints (20 bytes): last = 16
realloc to 10 ints: first = 0, last = 81
calloc digit counts of pi: 0 2 1 3 1 3 1 1 1 3
copy_string: Nevabit (8 bytes)
malloc(SIZE_MAX / 2) = NULL

• Запись p = realloc(p, …) — ошибка: при неудаче realloc вернёт NULL, старый блок останется, но указатель на него будет потерян — утечка.
• Функция может вернуть новую память: copy_string из примера (strdup в C11 нет) делает malloc(strlen(s) + 1) и копирует строку. В комментарии к такой функции пишут, кто освобождает результат.
• Запрос невозможного размера не роняет программу: malloc честно возвращает NULL. Программа без проверки упадёт позже, на первом обращении по нулевому указателю.

Пример целиком — examples/17/memory.c.

Компилятор следит за памятью стека, но не кучи. Ошибки с ней не видны сразу: программа часто выводит верный ответ, а падает потом или на другом компьютере. Программа examples/17/bugs.c делает четыре типичные ошибки:

AddressSanitizer (ASan) встроен в gcc и clang: программа собирается с проверками каждого обращения к памяти и при выходе сообщает об утечках. Отладочная сборка:

gcc -std=c11 -Wall -Wextra -g -fsanitize=address,undefined bugs.c -o bugs
./bugs dangling
==1435616==ERROR: AddressSanitizer: heap-use-after-free on address 0x504000000010 …
    #0 … in dangling bugs.c:28          ← где прочитали
    …
    #1 … in dangling bugs.c:27          ← где освободили
    …
    #1 … in dangling bugs.c:22          ← где выделили

Правила, которые снимают большую часть ошибок:

• после malloc/calloc/realloc — проверка на NULL; realloc — во временный указатель;
• у каждого блока один владелец; функции, которая возвращает новую память, в комментарии — «освобождает вызывающий»;
• после free(p) — p = NULL: повторный free(NULL) безопасен, а обращение по NULL сразу упадёт, а не прочитает мусор;
• каждая структура данных получает пару функций init / free, и free вызывается на каждом пути выхода, в том числе при ошибке;
• программа с динамической памятью считается готовой, когда ASan молчит на всех тестах.

Динамический массив хранит три поля: указатель на блок, сколько элементов занято (size) и под сколько выделено место (capacity). Пока место есть, добавление — просто запись в data[size++]. Когда место кончилось, блок увеличивается realloc-ом — вдвое:

typedef struct {
    int *data;
    size_t size;                             /* занято элементов */
    size_t capacity;                         /* выделено элементов */
} IntArray;

void array_init(IntArray *a)
{
    a->data = NULL;
    a->size = 0;
    a->capacity = 0;
}

/* Добавить в конец; при нехватке места — увеличить ёмкость вдвое. Нет памяти — завершить программу */
void array_push(IntArray *a, int value)
{
    if (a->size == a->capacity) {
        size_t new_capacity = a->capacity == 0 ? 4 : a->capacity * 2;
        int *p = realloc(a->data, new_capacity * sizeof *p);
        if (p == NULL) {
            fprintf(stderr, "out of memory\n");
            array_free(a);
            exit(1);
        }
        a->data = p;
        a->capacity = new_capacity;
    }
    a->data[a->size++] = value;
}

void array_free(IntArray *a)
{
    free(a->data);
    array_init(a);
}

/* Чтение заранее неизвестного числа целых */
IntArray a;
array_init(&a);
int x;
while (scanf("%d", &x) == 1) {
    array_push(&a, x);
}

Функции получают указатель на структуру: они меняют её поля, а копия структуры (раздел 15) изменилась бы и пропала. realloc(NULL, n) работает как malloc(n) — поэтому первый рост не нужно выделять отдельно. Удаление из середины сдвигает хвост влево — memmove, за O(n).

Почему вдвое. realloc может переместить блок и скопировать всё занятое. Пример examples/17/dynarray.c считает перевыделения и элементы, которые при этом пришлось бы скопировать, при чтении чисел 1…n для трёх правил роста:

• При росте на постоянную величину копий ≈ n²/(2·шаг) — O(n²), как у сортировки вставками: шаг лишь делит время на константу.
• При росте вдвое копий всего меньше n: 4 + 8 + 16 + … + n/2 < n. Отдельное добавление иногда дорого (копируется всё), но в среднем на одно добавление приходится меньше одной копии — амортизированное O(1). Перевыделений — log₂ n.
• Цена — до половины ёмкости пустует (1 048 576 мест под 10⁶ чисел). Можно расти в 1,5 раза: памяти пустует меньше, копий немного больше. Ёмкость уменьшают, когда занято меньше четверти (не половины — иначе добавление и удаление на границе будут перевыделять каждый раз).

Массив держит элементы подряд. Связный список — цепочка отдельных блоков-узлов: в каждом значение и указатель на следующий узел. У последнего next == NULL; весь список — указатель на первый узел (голову), пустой список — NULL.

typedef struct Node {
    int value;
    struct Node *next;                     /* тип Node ещё не объявлен — пишем struct Node */
} Node;

/* В начало за O(1): голова меняется — передаём указатель на неё */
bool push_front(Node **head, int value)
{
    Node *n = malloc(sizeof *n);
    if (n == NULL) {
        return false;
    }
    n->value = value;
    n->next = *head;
    *head = n;
    return true;
}

/* Удалить первый узел со значением; указатель на ссылку убирает особый случай головы */
bool remove_value(Node **head, int value)
{
    Node **link = head;
    while (*link != NULL && (*link)->value != value) {
        link = &(*link)->next;
    }
    if (*link == NULL) {
        return false;
    }
    Node *victim = *link;
    *link = victim->next;                  /* обойти узел: перецепить ссылку */
    free(victim);
    return true;
}

/* Освободить все узлы: next запомнить до free */
void free_list(Node **head)
{
    Node *p = *head;
    while (p != NULL) {
        Node *next = p->next;
        free(p);
        p = next;
    }
    *head = NULL;
}

push_front:    30 -> 20 -> 10 -> NULL
push_back:     30 -> 20 -> 10 -> 5 -> 7 -> NULL
find 10: yes, find 99: no
remove 30 5 7: 20 -> 10 -> NULL
reverse:       2 -> 1 -> 10 -> 20 -> NULL
backward:      20 10 1 2
free_list:     NULL

• Указатель на указатель Node **. Функция, которая может изменить голову (вставка в начало, удаление первого узла), получает адрес переменной head. А указатель link на поле next (или на саму head) позволяет удалять и вставлять одним кодом и в начале, и в середине.
• Обход — for (p = head; p != NULL; p = p->next). Цикл free_list сохраняет next до free(p): после free поле читать нельзя — это висячий указатель.
• Разворот на месте — три указателя prev, cur, next: каждый узел перецепляется на предыдущий. Новых узлов нет, O(n).
• Рекурсия на списке естественна (хвост списка — тоже список), но глубина равна длине: print_backward для миллиона узлов переполнит стек (раздел 16).
• Добавление в конец требует пройти весь список — O(n). Если в конец добавляют часто, хранят ещё указатель на последний узел (tail): тогда O(1).

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

Это не способы хранения, а правила доступа:

• Стек (LIFO — последним пришёл, первым ушёл): push кладёт наверх, pop снимает сверху. Стопка тарелок, кнопка «Назад» в браузере, отмена действий, стек вызовов функций.
• Очередь (FIFO — первым пришёл, первым ушёл): enqueue ставит в конец, dequeue берёт из начала. Очередь печати, обработка запросов по порядку, обход в ширину (раздел 24).

Стек удобно делать на динамическом массиве: вершина — data[size − 1], обе операции O(1). Очередь на массиве со сдвигом после каждого dequeue стоила бы O(n); вместо сдвига используют кольцевой буфер: начало head движется вперёд, а индексы берутся по модулю ёмкости.

typedef enum { OK, ERR_MEMORY, ERR_EMPTY, ERR_FULL } Status;

typedef struct {
    int *data;
    size_t head;                             /* индекс первого элемента */
    size_t count;
    size_t capacity;
} Queue;

Status enqueue(Queue *q, int value)
{
    if (q->count == q->capacity) {
        return ERR_FULL;
    }
    q->data[(q->head + q->count) % q->capacity] = value;   /* конец — за последним, по кругу */
    q->count++;
    return OK;
}

Status dequeue(Queue *q, int *value)
{
    if (q->count == 0) {
        return ERR_EMPTY;
    }
    *value = q->data[q->head];
    q->head = (q->head + 1) % q->capacity;
    q->count--;
    return OK;
}

queue of 4: in 1 in 2 in 3 in 4 FULL(5), out 1, out 2, in 6 7 (head = 2)
rest: 3 4 6 7

После двух dequeue начало сдвинулось на индекс 2, а 6 и 7 легли в освободившиеся ячейки 0 и 1 — по кругу. Очередь можно сделать и на списке: head для выдачи, tail для добавления, обе операции O(1), ограничения ёмкости нет.

Как оформлять функции. У pop и dequeue два результата: значение и признак успеха (пустая очередь — не значение). Принятый в C способ (раздел 15): функция возвращает код ошибки, значение кладёт по указателю. Перечисление Status делает коды читаемыми, и вызывающий решает, что делать при ошибке. exit внутри функции структуры данных — крайняя мера (как в array_push выше, где на нехватку памяти учебной программе нечего ответить): библиотечная функция не должна решать за программу, завершаться ли ей.

Проверка скобок. Открывающую скобку кладём в стек; закрывающая должна совпасть по виду со снятой сверху. Ошибка — если стек пуст при закрывающей, вид не совпал или в конце в стеке что-то осталось. Позиции считаются с 0:

a[i] = (b + c) * {d}   ok
f(a[i)]                error at 5          ← ')' закрывает '['
((x)                   error at 4          ← конец строки, '(' не закрыта
x)                     error at 1          ← закрывать нечего

Обратная польская запись (ОПН, постфиксная): знак операции ставится после операндов — 3 4 + 2 * вместо (3 + 4) * 2. Скобки и приоритеты не нужны, а вычисление — один проход со стеком: число кладётся в стек, операция снимает два верхних (сначала правый операнд, затем левый) и кладёт результат. В конце в стеке ровно одно число — ответ.

Status eval_rpn(const char *expr, long *result);    /* код ошибки + результат через указатель */

3 4 + 2 *            = 14
5 1 2 + 4 * + 3 -    = 14
2 3                  error: too many operands
1 +                  error: too few operands
4 0 /                error: division by zero
2 x *                error: bad token

Обычную (инфиксную) запись в ОПН переводит алгоритм сортировочной станции Дейкстры — тоже стеком, но для операций: число сразу уходит в выход, операция выталкивает из стека операции не ниже своего приоритета, скобка «(» кладётся в стек, «)» выталкивает всё до «(». Так работают калькуляторы и компиляторы. Код примеров — examples/17/stack_queue.c.