C. Массивы

Время чтения: 10 минут

Массив (array) – это непрерывная последовательность байт, хранящих множество значений определённого типа.

Проще – переменная хранит какое-то значение, а массив хранит множество переменных.

В прошлой статье мы со всех сторон рассмотрели указатели – тут то они нам и пригодятся!

Массив объявляется так:

int arr[3];

Здесь:

• int – это тип значений, которые хранятся в массиве
• arr – указатель на первый элемент массива
• [3] – размер массива

Прежде чем мы начнём заполнять значения, давай посмотрим как переменная и массив хранятся в памяти:

То есть, по сути, массив это просто набор переменных, которые расположены рядом в памяти.

Как ты помнишь из статьи про указатели, к ним можно прибавлять числа, чтобы сдвигать их туда-сюда в памяти.

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

Заполняем массив

Давай попробуем что-то записать в этот массив и вывести его значения:

int arr[3];
for(int i = 0; i < 3; i++)
{
	// Заполняем массив: в нулевой элемент записываем 1, в первый двойку, во второй тройку.
	*(arr+i) = i+1;
}
for(int i = 0; i < 3; i++)
{
	printf("Element %d: %d\n", i, *(arr+i));
}
/* Вывод:
Element 0: 1
Element 1: 2
Element 2: 3 */

Опа, смотри как циклы классно сочетаются с указателями – они просто созданы друг для друга!

Индексы

Чтобы с массивами было проще работать, в язык введены индексы – ои позволяют сократить запись обращения к элементу массива:

int arr[3];
// Записыаем 3 в последний элемент массива
*(arr+2) = 3;
// Делаем то же самое
arr[2] = 3;

Тут никаких хитростей нет – нужно просто помнить 3 правила:

• Указывай только индексы в пределах первого и последнего элемента массива
• Индекс первого элемента массива это 0 (нулевое смещение указателя)
• Индекс последнего элемента массива это N-1 (N это размер массива)

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

Пример использования массивов

Задача “Месячная температура”

• Считать размер массива и заполнить его целочисленными значениями
• Посчитать среднее арифметическое элементов массива (средняя температура)
• Вывести максимальный и минимальный элементы массива (максимальная и минимальная температура)

// 31 потому что это максимально возможное количество дней в месяце
int temperature[31];
int days;
scanf("%d", &days);
if(days < 1 || days > 31)
{
	printf("Incorrect days amount!\n");
	return 0;
}
for(int i = 0; i < days; i++)
{
	// Сообщаем для какого дня вводим значение (+1 чтобы дни начинались с 1)
	printf("Day %d temperature: ", i+1);
	// Ничего не разыменовываем, потому что в scanf нам нужно указывать адрес
	scanf("%d", temperature+i);
	// Ещё это можно записать так (этот вариант даже предпочтительнее):
	// scanf("%d", &temperature[i]);
}
double average = 0;
int min, max;
// Заполняем первым значением из массива, чтобы потом уже с ним сравнивать
min = max = temperature[0];
for(int i = 0; i < days; i++)
{
	// Временная переменная, чтобы сократить запись в следующих операциях
	int temp = temperature[i];
	// Ищем минимальное и максимальное значение
	min = min > temp ? temp : min;
	max = max < temp ? temp : max;
	// Суммируем среднюю температуру...
	average += temp;
}
// ... чтобы поделить её на количество дней
average /= days;
printf("Average temperature: %.1lf\nMin temperature: %d\nMax temperature: %d\n",
	average, min, max);

Многомерные массивы

До этого я показывал работу только с одномерным массивом, но вообще они бывают двух-, трёх-, четырёх- и сколькохочешь-мерными.

А зачем? Иногда возникают задачи, когда тебе необходимо хранить сразу несолько наборов данных.

Вот например – в задаче выше мне надо было хранить температуру по каждому дню месяца. А что, если мне надо было бы хранить температуру по каждому дню месяца в течении года – то есть 12 массивов на каждый месяц? Вот в этой ситуации мне бы и пригодился двумерный массив.

Чуть ниже я напишу изменённую программу, которая работает со всеми месяцами, а пока покажу как работать с многомерными массивами:

int arr[3][2];
for(int i = 0; i < 3; i++)
{
	for(int j = 0; j < 2; j++)
	{
		scanf("%d", &arr[i][j]);
	}
}
for(int i = 0; i < 3; i++)
{
	for(int j = 0; j < 2; j++)
	{
		printf("Element [%d][%d]: %d = %d = %d = %d\n", i, j, 
				arr[i][j],
				*(arr[i] + j),
				*(*(arr + i) + j),
				*((int*)arr + 2*i + j));
	}
}
/* Вывод (я ввёл значения 1 2 3 4 5 6):
Element [0][0]: 1 = 1 = 1 = 1
Element [0][1]: 2 = 2 = 2 = 2
Element [1][0]: 3 = 3 = 3 = 3
Element [1][1]: 4 = 4 = 4 = 4
Element [2][0]: 5 = 5 = 5 = 5
Element [2][1]: 6 = 6 = 6 = 6 */

Эмммм… Что это за чёрная магия там в выводе?

Сейчас объясню!

По сути, многомерные массивы в памяти выглядят точно так же, как и одномерные:

Вся разница лишь в том, что ты можешь первым индексом перескакивать между массивами, а вторым индексом перескакивать между элементами массивов.

А на счёт чёрной магии – ты же не забыл что индекс это просто сокращённая запись разыменования?

int arr[3][2];
arr[i][j] == *( *(arr + i) + j )

Окей, а почему мы к arr прибавляем число, а потом разыменовываем его?

Прикол в том, что arr – это не простой указатель, как в случае с одномерным массивом – arr это указатель на массив с размером 2.

Поэтому, когда мы прибавляем число к этому указателю, он смещается на (размер массива * размер элемента массива) байт:

// Смещаем arr на 8 байт вправо = 2 (размер массива) * 4 (размер int)
arr + 1

Если мы разыменуем его, то получим второй массив – указатель на его первый элемент:

*(arr + 1)
// То же самое что
arr[1]

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

*( *(arr + 1) + 1 )
// То же самое что
arr[1][1]

Всё то же самое можно провернуть и с обычным указателем, но тогда нам надо самим следить, что мы правильно переходим между массивами (домножать индекс на размер массива):

*((int*)arr + 2*i + j))

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

Трёхмерные массивы не сильно отличаются от двумерных – просто там добавляется ещё один слой указателей:

int arr[3][4][5];

// int элемент
arr[1][2][3] == *( *( *(arr + 1) + 2 ) + 3 )

// Указатель на массив из 5-ти int элементов
arr[1][2] == *( *(arr + 1) + 2 )

// Указатель на массив из 4-х элементов,
// где каждый из элементов это массив из 5-ти int элементов
arr[1] == *(arr + 1)

// Указатель на массив из 3-х элементов,
// где каждый элемент это массив из 4-х элементов,
// где каждый из элементов это массив из 5-ти int элементов
arr 

Пример использования многомерных массивов

Как и обещал – переписываю программу под многомерный массив:

int temperature[12][31];
int months, days;
scanf("%d", &months);
if(months < 1 || months > 12)
{
	printf("Incorrect months amount!\n");
	return 0;
}
scanf("%d", &days);
if(days < 1 || days > 31)
{
	printf("Incorrect days amount!\n");
	return 0;
}
for(int i = 0; i < months; i++)
{
	printf("Month %d\n", i+1);
	for(int j = 0; j < days; j++)
	{
		printf("Day %d temperature: ", i+1);
		scanf("%d", &temperature[i][j]);
	}
}
double average = 0;
int min, max;
min = max = temperature[0][0];
for(int i = 0; i < months; i++)
{
	for(int j = 0; j < days; j++)
	{
		int temp = temperature[i][j];
		min = min > temp ? temp : min;
		max = max < temp ? temp : max;
		average += temp;
	}
}
average /= months * days;
printf("Average temperature: %.1lf\nMin temperature: %d\nMax temperature: %d\n",
	average, min, max);
/* Ввод:
2
2
Month 1
Day 1 temperature: 4
Day 1 temperature: 5
Month 2
Day 2 temperature: 11
Day 2 temperature: -10

Вывод:
Average temperature: 2.5
Min temperature: -10
Max temperature: 11 */

Динамические массивы

До этого я показал как работать со статическими массивами – то есть мы знаем на момент написания программы, сколько максимально он будет занимать памяти.

Однако, иногда ты:

• Не можешь предположить максимальный размер массива
• Хочешь сэкономить память и использовать столько, сколько нужно

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

int size;
scanf("%d", &size);
int *arr = (int*)malloc(size * sizeof(int));
if(arr == NULL)
{
	printf("Can't allocate %d bytes\n", size);
	return 0;
}
for(int i = 0; i < size; i++)
{
	scanf("%d", &arr[i]);
}

В этой программе я считываю размер массива, выделяю под него память и заполняю его значениями.

А как я выделяю память, что это за malloc?

malloc

malloc – это функция, содержащаяся в “stdlib.h”. Она:

• Обращается к операционной системе, и запрашивает выделение указанного количества байт (в программе я указал size * размер int)
• Если операционная система может выделить такое количество байт, то функция возвращает указатель на первый байт выделенного блока памяти (возвращается указатель типа void*, поэтому я его явно привожу к int*)
• Если операционная система не может выделить такое количество байт, то функция возвращает NULL (по сути, это нулевой адрес)
• НЕ заполняет память нулями – в памяти останется то, что там было перед этим

Обычно malloc справляется со своей задачей, и NULL возвращается только в исключительных ситуациях. В учебных целях можешь не проверять результат на NULL, но при разработке серьёзного ПО, от которого могу зависеть жизни людей – проверка обязательна.

calloc

Кроме malloc, есть ещё функция calloc – делает почти то же самое, но со следующими отличиями:

• В параметрах отдельно указывается размер массива и размер элемента массива
• calloc ЗАПОЛНЯЕТ нулями выделяемую память

Вот пример его использования (не сильно отличается):

int size;
scanf("%d", &size);
int *arr = (int*)calloc(size, sizeof(int));
if(arr == NULL)
{
	printf("Can't allocate %d bytes\n", size);
	return 0;
}
for(int i = 0; i < size; i++)
{
	scanf("%d", &arr[i]);
}

free

После того как ты выделил память, её необходимо освободить – операционная система этого сама не сделает пока программа не завершится.

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

Для освобождения памяти есть функция free. Вот как она используется:

int size;
scanf("%d", &size);
int *arr = (int*)calloc(size, sizeof(int));
if(arr == NULL)
{
	printf("Can't allocate %d bytes\n", size);
	return 0;
}
for(int i = 0; i < size; i++)
{
	scanf("%d", &arr[i]);
}
free(arr);

Всегда-всегда-всегд помни – операционная система даёт твоей программе оперативную память в долг, а долги надо возвращать.

Пример использования динамического многомерного массива

И ещё раз я перепишу программу, чтобы показать как работать с динамической памятью в случае многомерных массивов:

Здесь будут использованы указатели на указатели – если забыл что это такое, то можешь освежить в памяти статью по указателям.

int** temperature;
int months, days;
scanf("%d", &months);
if(months < 1 || months > 12)
{
	printf("Incorrect months amount!\n");
	return 0;
}
scanf("%d", &days);
if(days < 1 || days > 31)
{
	printf("Incorrect days amount!\n");
	return 0;
}

// Выделяем память под массив int* указателей
temperature = (int**)calloc(months, sizeof(int*));
if(temperature == NULL)
	return 0;
for(int i = 0; i < months; i++)
{
	// Выделяем память под массив int значений, 
	// и записываем адрес на эту память в указатель
	temperature[i] = (int*)calloc(days, sizeof(int));
	if(temperature[i] == NULL)
	{
		// Освобождаем все массивы int значений, что успели выделиться
		for(int j = 0; j < i; j++)
			free(temperature[j]);
		// Освобождаем массив int* указателей
		free(temperature);
		return 0;
	}
}

for(int i = 0; i < months; i++)
{
	printf("Month %d\n", i+1);
	for(int j = 0; j < days; j++)
	{
		printf("Day %d temperature: ", i+1);
		scanf("%d", &temperature[i][j]);
	}
}
double average = 0;
int min, max;
min = max = temperature[0][0];
for(int i = 0; i < months; i++)
{
	for(int j = 0; j < days; j++)
	{
		int temp = temperature[i][j];
		min = min > temp ? temp : min;
		max = max < temp ? temp : max;
		average += temp;
	}
}
average /= months * days;
printf("Average temperature: %.1lf\nMin temperature: %d\nMax temperature: %d\n",
	average, min, max);
for(int i = 0; i < months; i++)
{
	// Освобождаем память, выделенную под массив int значений
	free(temperature[i]);
}
// Освобождаем память, выделенную под массив int* указателей
free(temperature);

Заключение

Итого, ты узнал что такое:

• Массив (множество переменных)
• Одномерные массивы
• Индексы (сокращённая запись разыменования)
• Многомерный массив (массив массивов)
• Динамические массивы (выделяем и освобождаем столько памяти, сколько нужно)