Динамическое выделение памяти

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

Если мы хотим динамически выделить память, то используют функции malloc или calloc, или realloc, которые находятся в библиотеках <stdlib.h> и <malloc.h>. Давайте по порядку.

malloc

Массив

Чтобы выделить память с помощью malloc, нам нужно указать только размер в байтах. Для выделения 20 элементов массива типа int , нам понадобиться 80 байт, так как один элемент типа int равен 4 байтам. Чтобы не считать сколько байт нам нужно выделить, используется
sizeof(тип данных), это значение будет равно одному элементу заданного типа. Например, sizeof(int) будет равен 4 байтам.
Примеры выделения памяти под 20 элементов массива типа int:

int* a = malloc(80) или int* a = malloc(20 * sizeof(int))

Лучше использовать второй способ, с ним вы не совершите ошибку.

Функция malloc возвращает указатель на выделенное пространство или NULL, Если не находит место под память. Нужно помнить об этом и на всякий случай проверять.

Выделить те же 20 элементов под структуру point с именем p можно так:

struct point *p = malloc(20 * sizeof(struct point));

Двумерный массив

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

Сначала нужно выделить память под массив указателей, далее для каждого элемента массива указателей выделить строку размера m.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<malloc.h>
 
int main() {
	int** a;
	int n, m, i, j;
	scanf_s("%i%i", &n, &m);
 
	a = malloc(n * sizeof(int*));
	for (i = 0; i < n; i++) {
		a[i] = malloc(m * sizeof(int));
	}
 
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			scanf_s("%i", &a[i][j]);
			a[i][j] += 100;
		}
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			printf("%i ", a[i][j]);
		}
		printf("\n");
	}
	return 0;
}

Для начала мы выделяем массив под указатели на строки. Посе чего, в цикле, для каждого элемента массива a выделяем память под m элементов, функция malloc вернет в элемент a[i] адрес строки i. Тем самым мы получаем массив указателей на строки. Теперь мы можем спокойно использовать эту память.
Для обращения к элементам можно использовать как a[i][j], так и *(*(a + i) + j).

Размеры каждой строки вы можете определять сами, что может быть полезно для некоторых задач.

calloc

Чтобы выделить память с помощью calloc нам нужны два аргумента: количество элементов и размер одного элемента. В отличии от malloc, который просто выделяет память, calloc инициализирует все элементы массива нулями.
Пример выделения памяти под 20 элементов массива типа int:

int* a = calloc(20, sizeof(int))

realloc

С помощью realloc вы можете уменьшить размер массива или дополнительно выделить память под несколько элементов, если до этого массив был динамически выделен с помощью функций malloc или calloc, или realloc. Чтобы выделить дополнительную память с помощью realloc, нужен, во-первых, указатель на прошлый массив, который был выделен динамически. Во-вторых, указать новый размер массива, он может быть и меньше, тогда все элементы, которые выходят за границу справа, будут удалены.

Массив

Вот так выглядит выделение дополнительных двух элементов массива:

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
 
int main() {
	int* array = malloc(1 * sizeof(int));
	array[0] = 3;
	array = realloc(array, 3 * sizeof(int));
	array[1] = 4;
	array[2] = 5;
	return 0;
}

Двумерный массив

Выделение дополнительных 5 столбцов матрицы:

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
 
int main() {
	int** a;
	int n, m, i, j;
	scanf_s("%i%i", &n, &m);
 
	a = malloc(n * sizeof(int*));
	for (i = 0; i < n; i++) {
		a[i] = malloc(m * sizeof(int));
	}
 
	for (i = 0; i < n; i++) { 
		a[i] = realloc(a[i], (m + 5) * sizeof(int));
	}
	return 0;
}

Теперь матрица размера n * (m + 5).

Конечно, для каждой строки вы можете добавить разное количество элементов, что может быть полезно для некоторых задач.

Выделение дополнительных 2 строк матрицы:

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
 
int main() {
	int** a;
	int n, m, i, j;
	scanf_s("%i%i", &n, &m);
 
	a = malloc(n * sizeof(int*));
	for (i = 0; i < n; i++) {
		a[i] = malloc(m * sizeof(int));
	}
 
	int l = n + 2;  // l - новое кол-во строк
	a = realloc(a, (l) * sizeof(int*));
	for (i = n; i < l; i++) {
		a[i] = malloc(m * sizeof(int));
	}
	return 0;
}

Теперь можем использовать элементы a[n][i] и a[n + 1][i]. Матрица имеет размер (n + 2) * m.

Выделять динамически память может быть очень полезным для решения задач. Например, в задачах про графы, где мы точно не знаем сколько путей из каждой вершины. Вы можете изучить алгоритмы DFS и BFS, где так же используется динамическое выделение памяти.

Освобождение памяти

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

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
 
int main() {
	int* array = malloc(10 * sizeof(int));
	for (int i = 0; i < 10; i++) {
		array[i] = i + 1;
	}
	for (int i = 0; i < 10; i++) {
		printf("%i ", array[i]);
	}
	free(array);
	return 0;
}

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

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
 
int main() {
	int** a;
	int n, m, i, j;
	scanf_s("%i%i", &n, &m);
 
	a = malloc(n * sizeof(int*));
	for (i = 0; i < n; i++) {
		a[i] = malloc(m * sizeof(int));
	}
 
	for (i = 0; i < n; i++) {
		free(a[i]); 
	}
	free(a);
	return 0;
}