09 ноября 2021

Работа с динамической памятью

До сих пор в работе с памятью мы полагались на компилятор. Память, необходимая для переменных или массивов, выделается автоматически. При этом происходит работа с быстрой областью памяти - стеком.

Язык Си предоставляет инструменты для ручного управления памятью с помощью функуий malloc, realloc, free и некоторых других. Эти функции определенны в библиотеке stdlib.h.

Функция malloc принимает размер запрашиваемой памяти в байтах, выделает соответствующую память (непрерывный участок памяти), и возвращает указатель на начало выделенной области. Выделить память для массива из десяти элементов типа int можно следующим образом:

int* dynamic_array = malloc(10 * sizeof(int));

Память, полученная таким образом, выделается в более медленной области памяти, которую называют кучей (heap). Размер кучи значительно превосходит размер стека, поэтому динамическое выделение памяти используется для хранения данных, которые не могут поместиться на стеке. Обычно размер стека не превосходит 10 МБ.

Ключевая особенность работы с динамической памятью (в отличие от работы с автоматической памятью) состоит в том, что программист должен следить за освобождением памяти. Как только выделенная память перестала быть нужной, необходимо вызвать функцию free:

free(dynamic_array);

Такой способ работы с памятью позволяет управлять временем жизни объектов. Рассмотрим пример. Напишем фукнцию, которая создает массив и возвращает указатель на его начало. Реализация без динамической памяти работать не будет:

// Эта функция не работает!
int* make_array_wrongly() {
    int array[100];
    for (int i = 0; i < 100; ++i) array[i] = i;
    return array;
}

Автоматический массив array удалается со стека как только функция make_array закончила работу. В результате мы вернем указатель на память, которая уже не связана с массивом.

Динамическое выделение памяти позволяет преодолеть эту сложность:

int* make_array() {
    int* array = malloc(100 * sizeof(int));
    if (array == NULL) return NULL;
    for (int i = 0; i < 100; ++i) array[i] = i;
    return array;
}

Память для массива выделилась в куче и осталась в нашем распоряжени после завершения работы фукнции make_array. Надо только не забыть вызвать функцию free и освободить память, когда она перестанет быть нужной.

Фукнция realloc позволяет изменить размер выделенной памяти, не потеряв данные. Например:

int* array = malloc(5 * sizeof(int));
if (array == NULL) return;
for (int i = 0; i < 5; ++i) array[i] = i;
array = realloc(array, 10 * sizeof(int));
if (array == NULL) return;
for (int i = 5; i < 10; ++i) array[i] = i;
for (int i = 0; i < 10; ++i) {
    printf("%d%c", array[i], i == 9 ? '\n' : ' ');
}

Получаем:

0 1 2 3 4 5 6 7 8 9

Можно и уменьшить объем выделенной памяти. При этом сохранятся данные, которые помещаются в новой области памяти. Функция realloc выделяет новую область памяти, копирует в нее данные из предыдущей области, и возвращает указатель на начало новой области. Аргументами функции является указатель на уже выделенную область памяти и новый размер.

Выполнение функций malloc и realloc может закончиться неудачей (например, запрошен слишкой большой размер памяти). В этом случае будет возвращен указатель со значением NULL. Всегда проверяйте, что выделение памяти выполнено успешно.

Динамический стек

Реализуйем структуру данных стек, используя динамическое выдерение памяти. Стек - это последовательность элементов, организованных по принципу LIFO (last in - first out):

Автор: Higimo - собственная работа, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=24588556

Следующая структура будет описывать стек для хранения целых чисел:

typedef struct {
    int* data;
    size_t size;
    size_t capacity;
} Stack;

Поле data указывает на область памяти, занятую стеком, поле capacity хранит размер этой области памяти, а поле size хранит количество элементов на стеке. Значение capacity не может быть меньше значения size. Для эффективного выполнения всех операций со стеком предлагается следющий алгоритм динамического выделения памяти:

1. Инициализируем пустой стек, выделяя область памяти для хранения четырех переменных int с помощью функции malloc. Значения полей при этом - следующие: size = 0, capacity = 4;
2. При достижении условия size == capacity выделяем новую область памяти, в два раза большую прежней, с помощью функции realloc. Все значения, записанные в стек, должны сохраниться;
3. При достижении условия capacity > 4 && 4 * size < capacity выделяем новую область памяти, в два раза меньшую прежней, с помощью функции realloc. Все значения, записанные в стек, должны сохраниться;

Функция init_stack выделяет память и возвращает указатель пустой стек:

#define INIT_SIZE 4

Stack* init_stack() {
    Stack* st = (Stack*)malloc(sizeof(Stack));
    st->capacity = INIT_SIZE;
    st->data = (int*)malloc(st->capacity * sizeof(int));
    st->size = 0;
    return st;
}

Функция pop_stack удаляет элемент со стека st и возвращает его

int pop_stack(Stack* st) {
    if (st->size == 0) {
        puts("Pop from empty stack\n");
        return 0;
    }
    if (st->size > 4 && 4 * st->size == st->capacity) {
        st->capacity /= 2;
        st->data = (int*)realloc(st->data, st->capacity * sizeof(int));
    }
    return st->data[--st->size];
}

Функция top_stack возвращает верхний элемент стека, не удаляя его:

int top_stack(Stack *st) {
    return st->data[st->size - 1];
}

Функция put_stack добавляет элемент на стек

void put_stack(Stack *st, int value) {
    if (st->size == st->capacity) {
        st->capacity *= 2;
        st->data = (int*)realloc(st->data, st->capacity * sizeof(int));
        if (st->data == NULL) {
            puts("Can't allocate memory\n");
            exit(1);
        }
    }
    st->data[st->size++] = value;
}

Функция free_stack освобождает память, выделенную для стека.

void free_stack(Stack* st) {
    free(st->data);
    free(st);
}

Пример использования нашей структуры данных:

int main() {
    Stack* st = init_stack();
    for (int i = 0; i < 1000; ++i) {
        put_stack(st, i);
    }

    for (int i = 0; i < 1000; ++i) {
        int val = pop_stack(st);
        printf("%d\n", val);
    }

    free_stack(st);

    return 0;
}

Связный список

Реализуем структуру данных связный спикок.

Очередь на основе списка

Реализуем структуру данных очередь - это последовательность элементов, организованных по принципу LIFO (first in - first out).