Как выделить память под двумерный массив си
Перейти к содержимому

Как выделить память под двумерный массив си

  • автор:

Быстрое создание многомерных динамических массивов

В этом примере сначала выделяется память под массив указателей, потом M раз выделяется память под массивы. Во время удаления массива сначала M раз удаляются массивы, а потом удаляется массив указателей. Операции malloc и free затратные. Кроме того, выделение маленьких кусков памяти приводит к фрагментации памяти, так что последующее выделение памяти становится ещё медленнее.

Розовым обозначен массив указателей

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

const int M = 100; const int N = 200; int **a = NULL; int i; a = (int**) malloc(M * sizeof(int*)); a[0] = (int*) malloc(M * N * sizeof(int)); for (i = 1; i < M; i++) < a[i] = a[0] + i * N; >//Важные действия free(a[0]); free(a);

Теперь нам необходимо всего две операции выделения памяти и две операции для освобождения.

Розовым обозначен массив указателей

У этого подхода есть и ещё одно важное преимущество. Массив a[0] по структуре становится похож на одномерный, так что его можно передавать как одномерный, например, для сортировки. Элементы расположены в нём по рядам, как в двумерном статическом массиве, поэтому без проблем можно его привести к типу указателя на массивы.

Можно пойти ещё дальше и заменить всё одним вызовом malloc: упаковать друг за другом сначала массив указателей, а потом массив массивов.

const int M = 100; const int N = 200; int **a = NULL; int i, j; a = (int**) malloc(M * sizeof(int*) + N * M * sizeof(int)); a[0] = (int*)(a + M); for (i = 1; i < M; i++) < a[i] = a[0] + i * N; >//Важные действия free(a);

Здесь всего одна операция выделения и одна освобождения.

Розовым обозначен массив указателей

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

Скорость выполнения соотносится для данных способов выделения памяти как 404:13:12 для массива размером 100 x 200 типа int. Последние два способа выделения памяти, дабы не смущать неокрепшие умы, почти не используются в курсе, но на практике динамически выделять память под многомерные массивы лучше именно таким образом.

Рассмотрим выделение памяти под трёхмерный массив. Трёхмерный массив — массив указателей на указатели, которые ссылаются на массивы указателей, которые ссылаются на массивы объектов заданного типа. Выделение памяти под трёхмерный массив размером M*N*K, соответственно, потребует M + M*N операций выделения памяти и столько же для освобождения.

Серым обозначен массив указателей на указатели, розовым массив указателей

Первым делом объявим переменные

const int M = 10; const int N = 10; const int K = 10; int*** a = NULL; int* data; int** ptrs; int i, j, k;

Здесь a — наш будущий трёхмерный массив, data — вспомогательная переменная, которая хранит адрес, по которому начинаются непосредственно данные (белым цветом на рисунке). ptrs — вспомогательная переменная, которая хранит адрес, по которому начинаются массивы указателей (розовый на рисунке).

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

a = (int***) malloc(M * sizeof(int**) + M*N * sizeof(int*) + M*N*K * sizeof(int));

Затем инициализируем вспомогательные переменные

ptrs = (int**) (a + M); data = (int*) (a + M + M*N);

Затем надо инициализировать массив указателей на указатели

for (i = 0; i

Но также нужно инициализировать каждый из массивов указателей

for (i = 0; i < M; i++) < a[i] = ptrs + i*N; for (j = 0; j < N; j++) < a[i][j] = data + j * N*K; >>

Теперь наш массив принимает вид:

Серым обозначен массив указателей на указатели, розовым массив указателей

const int M = 10; const int N = 10; const int K = 10; int*** a = NULL; int* data; int** ptrs; int i, j, k, q; a = (int***) malloc(M * sizeof(int**) + M*N * sizeof(int*) + M*N*K * sizeof(int)); ptrs = (int**) (a + M); data = (int*) (a + M + M*N); q = 0; for (i = 0; i < M; i++) < a[i] = ptrs + i*N; for (j = 0; j < N; j++) < a[i][j] = data + (q++) * N*K; >>

ru-Cyrl 18- tutorial Sypachev S.S. 1989-04-14 sypachev_s_s@mail.ru Stepan Sypachev students

email

Всё ещё не понятно? – пиши вопросы на ящик

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

При создании массива с фиксированными размерами под него выделяется определенная память. Например, пусть у нас будет массив с пятью элементами:

double numbers[5] = ;

Для такого массива выделяется память 5 * 8 (размер типа double) = 40 байт. Таким образом, мы точно знаем, сколько в массиве элементов и сколько он занимает памяти. Однако это не всегда удобно. Иногда бывает необходимо, чтобы количество элементов и соответственно размер выделяемой памяти для массива определялись динамически в зависимости от некоторых условий. Например, пользователь сам может вводить размер массива. И в этом случае для создания массива мы можем использовать динамическое выделение памяти.

Для управления динамическим выделением памяти используется ряд функций, которые определены в заголовочном файле stdlib.h :

    malloc() . Имеет прототип

void *malloc(unsigned s);
void *calloc(unsigned n, unsigned m);
void *realloc(void *bl, unsigned ns);
void *free(void *bl);

malloc

Функция malloc() выделяет память длиной для определенного количества байт и возвращает указатель на начало выделенной памяти. Через полученный указатель мы можем помещать данные в выделенную память. Рассмотрим простой пример:

#include #include // для подключения функции malloc int main(void) < int *ptr = malloc(sizeof(int)); // выделяем память для одного int *ptr = 24; // помещаем значение в выделенную память printf("%d \n", *ptr); free(ptr); >

Здесь с помощью функции malloc выделяется память для одного объекта int . Чтобы узнать, сколько байтов надо выделить, передаем в функцию malloc размер типа int на текущей и в результате получаем указатель ptr , который указывает на выделенную память

int *ptr = malloc(sizeof(int));

То есть поскольку int на большинстве архитектур занимает 4 байта, то в большинстве случаев будет выделяться память объемом в 4 байта. Стоит отметить, что мы также могли бы получить размер через разыменование указателя:

int *ptr = malloc(sizeof *ptr);

Для универсальности возвращаемого значения в качестве результата функция malloc() (как и calloc() и realloc() ) возвращает указатель типа void * . Но в нашем случае создается массив типа int, для управления которым используется указатель типа int * , поэтому выполняется неявное приведение результата функции malloc к типу int * .

Далее через этот указатель с помощью операции разыменования помещаем в выделенный участок памяти число 24:

*ptr = 24;

В дальнейшем, используя указатель, можно получить значение из выделенного участка памяти:

printf("%d \n", *ptr);

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

free(ptr);

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

#include #include // для подключения функции malloc int main(void) < int *ptr = malloc(sizeof(int)); // выделяем память для одного int if(ptr != NULL) < *ptr = 24; // помещаем значение в выделенную память printf("%d \n", *ptr); >free(ptr); >

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

free(ptr); ptr = NULL;
Выделение памяти для массива

Подобным образом можно выделять память и под набор объектов. Например, выделим память для массива из 4-х чисел int:

#include #include int main(void) < int n = 4; int *ptr = malloc(n * sizeof(int)); // выделяем память для 4-х чисел int if(ptr) < // помещаем значения в выделенную память ptr[0] = 1; ptr[1] = 2; ptr[2] = 3; ptr[3] = 5; // получаем значения for(int i = 0; i < n; i++) < printf("%d", ptr[i]); >> free(ptr); >
Выделение памяти для структуры

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

#include #include struct person < char* name; int age; >; int main(void) < // выделяем память для одной структуры person struct person *ptr = malloc(sizeof(struct person)); if(ptr) < // помещаем значения в выделенную память ptr->name = "Tom"; ptr->age = 38; // получаем значения printf("%s : %d", ptr->name, ptr->age); // Tom : 38 > free(ptr); return 0; >

calloc

Функция calloc() имеет прототип

void *calloc(unsigned n, unsigned m);

Она выделяет память для n элементов по m байт каждый и возвращает указатель на начало выделенной памяти. В случае неудачного выполнения возвращает NULL

В отличие от функции malloc() она инициализирует все выделенные байты памяти нулями. Например, выделим память для одного объекта int :

#include #include int main(void) < // выделяем память для одного объекта int int *ptr = calloc(1, sizeof(int)); if(ptr) < // получаем значение по умолчанию - 0 printf("Initial value: %d", *ptr); // Initial value: 0 // устанавливаем новое значение *ptr = 15; // получаем новое значение printf("New value: %d", *ptr); // New value: 15 >free(ptr); return 0; >
Initial value: 0 New value: 15

Подобным образом можно выделить память и для других объектов. Например, выделим память для массива из 4-х объектов int :

#include #include int main(void) < // выделяем память для 4-х объектов int int n = 4; int *ptr = calloc(n, sizeof(int)); if(ptr) < // устанавливаем значения ptr[0] = 1; ptr[1] = 2; ptr[2] = 3; ptr[3] = 5; // получаем значения for(int i = 0; i < n; i++) < printf("%d", ptr[i]); >> free(ptr); >

realloc

Функция realloc() позволяет изменить размер памяти, ранее выделенной с помощью функций malloc() b calloc() . Имеет прототип

void *realloc(void *bl, unsigned ns);

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

Если указатель bl имеет значение NULL , то есть память не выделялась, то действие функции аналогично действию malloc

Рассмотрим небольшой пример:

#include #include int main(void) < // выделяем память для 1-го объекта int int size = sizeof(int); int *ptr = malloc(size); if(ptr) < // отображаем адрес и размер памяти printf("Addresss: %p \t Size: %d\n", (void*)ptr, size); >// расширяем память до размера 4-х объектов int size = 4 * sizeof(int); int *ptr_new = realloc(ptr, size); // если выделение памяти прошло успещно if(ptr_new) < printf("Reallocation\n"); // заново отображаем адрес и размер памяти printf("Addresss: %p \t Size: %d\n", (void*)ptr_new, size); free(ptr_new); // освобождаем новый указатель >else < free(ptr); // освобождаем старый указатель >>

Здесь сначала выделяем память для одного объекта int с помощью функции malloc.

int size = sizeof(int); int *ptr = malloc(size);

Если память успешно выделена, то выводим на консоль адрес и размер выделенного блока памяти. Затем с помощью функции realloc расширяем память до 4 объектов int

size = 4 * sizeof(int); int *ptr_new = realloc(ptr, size);

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

Консольный вывод в моем случае

Addresss: 0000018B078A82F0 Allocated: 4 Reallocation Addresss: 0000018B078A82F0 Allocated: 16

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

#include #include int main(void) < int size = sizeof(int); int *ptr = malloc(size); if(ptr) < printf("Addresss: %p \t Allocated: %d\n", (void*)ptr, size); >size = 4 * sizeof(int); ptr = realloc(ptr, size); // используем старый указатель if(ptr) < printf("Reallocation\n"); printf("Addresss: %p \t Allocated: %d\n", (void*)ptr, size); >free(ptr); >

О динамических массивах в языке Си: что это такое, виды, как с ними работать

Массив — последовательная группа ячеек памяти, имеющих одинаковое имя и одинаковый тип. То есть это структуры, которые содержат связанные друг с другом однотипные элементы данных.

Они занимают область в памяти. Компилятор резервирует соответствующий объем памяти для каждого типа и количества элементов каждого массива.

Чтобы зарезервировать память при помощи компилятора для статического массива, необходимо указать ему сколько в нем будет элементов целых чисел. Для этого используется объявление int a [] ;

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

Пример объявления для 12 элементов:

Для динамического массива количество элементов не указывают.

На этапе написания программы размер динамических массивов неизвестен. Ввод количества элементов осуществляется во время работы программы.

Размером при объявлении динамического массива является числовая переменная, а не константа.

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

В динамических массивах также не указывают длину строк и их количество. Границы массивов полностью контролируются разработчиком.

Указатели для динамических массивов

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

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

Действия с указателями

Указатели:

  • int *pI;
  • char *pC;
  • float *pF;

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

Указатели:

Адрес присваивается указателю с помощью оператора &. Знак &, стоящий перед переменной, будет указывать на ее адрес.

  1. Получение значения по этому адресу.

Указатели:

  • f = *pF;
  • float f, *pF;

Для переменной определенного типа, на которую определен указатель, например, pF, указывается число соответствующего типа. Символ * перед pF означает информацию ячейки, указанной pF.

Указатели:

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

Указатели:

Указатель указывает на недействительный адрес, который равен нулю, соответственно, указатель тоже недействительный. Запись по нему не может быть осуществлена.

Указатели:

  • int i, *pI;
  • printf(«Адр.i =%p», pI);
  • pI = &i;

Для вывода указателей на экран применяют формат %p.

Ошибки, возникающие при неверном использовании динамических массивов

  1. Запись в чужую область памяти.

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

Вывод: необходимо всегда осуществлять проверку указателя на NULL. Если значение указателя будет равно нулю при проверке после выделения памяти, то использование такого массива будет приводить к зависанию компьютера.

Причина: Массив уже удален и теперь удаляется снова.

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

Причина: В массив записан элемент с отрицательным индексом или индексом, выходящим за границу массива.

Причина: Неиспользуемая память не освобождается. Если это происходит в функции, которая вызывается много раз, то ресурсы памяти скоро будут израсходованы. Вывод: необходимо тщательно проверить код, и удалить артефакты.

Виды динамических массивов

Классификация динамических массивов:

  • одномерные: int * A;
  • двумерные: int ** A;

Одномерный динамический массив представляет собой множество элементов одного типа данных.

Двухмерный массив имеет более сложную структуру и содержит в качестве элементов массива другие массивы. Каждому хранящемуся в массиве А указателю присвоено не одно значение, а одномерный динамический массив таких значений.

Переменная А сама является указателем и объявляется как указатель на указатель на нужный тип. Данный указатель нужно инициализировать, то есть положить ему адрес массива адресов. В памяти программы должен существовать массив адресов указателей на int и сам массив указателей на int. В этом массиве указателей должны быть разложены адреса, возможно лежащие отдельно друг от друга в памяти.

Пример двумерного массива:

  1. #include // здесь указывают заголовок файла, содержащего функции, переменные, классы, для организации операций ввода-вывода
  2. using namespace std; // объявление пространства имен для ограничения видимости переменных, функций и т.д.
  3. int main()
  4. setlocale(0, «»); “// указывают тип значения, возвращаемого функцией, и задают локаль для программы
  5. int **dinamic_array2 = new int* [5];
  6. for (int i = 0; i < 5; i++)
  7. dinamic_array2[i] = new int [i + 1];
  8. > // Создание двумерного массива
  9. for (int i = 0; i < 5; i++)
  10. cout
  11. for (int j = 0; j < i + 1; j++)
  12. cin >> dinamic_array2[i][j];
  13. >
  14. > // заполнение массива
  15. for (int j = 0; j < i + 1; j++)
  16. sum += dinamic_array2[i][j];
  17. >
  18. cout
  19. > // проведение различных операций по вводу-выводу
  20. for (int i = 0; i < 5; i++)
  21. delete [] dinamic_array2[i]; // удаление массива
  22. >
  23. system(«pause»);
  24. return 0;
  25. >

Строки 5-8 — создание динамического массива.

Строки 9-14 — заполнение.

Строки 15-19 — подсчет, сортировка и вывод на экран суммы всех массивов.

Строки 20-22 — удаление массива.

Стандартные функции динамического выделения памяти

В языке программирования Си имеются стандартные функции управления памятью:

  1. Malloc (от англ. memory allocation, выделение памяти). Функция malloc возвращает указатель на n байт неинициализированной памяти или NULL, если запрос на память нельзя выполнить: void *malloc(size_t n). Значение, которое возвращает malloc, — это адрес начала выделенной области памяти. При этом гарантируется соответствующее выравнивание этого адреса на границу памяти, обеспечивающую хранение в области любого объекта.
  2. Calloc (от англ. clear allocation, чистое выделение памяти). Функция calloc возвращает указатель на участок памяти, достаточный для размещения п объектов заданного размера size или NULL, если запрос на память невыполним. Память инициализируется нулями; void *calloc(size_t n, size_t size).
  3. Realloc (от англ. reallocation, перераспределение памяти). Используется для изменения величины выделенной памяти, на которую указывает ptr, на новую величину, задаваемую параметром newsize. Эта функция может перемещать блок памяти на новое место, в этом случае функция возвращает указатель на новое место в памяти.
  4. Free (англ. free, освободить). Функция free(p) освобождает участок памяти, на который указывает указатель р, первоначально полученный вызовом функции malloc или calloc. Порядок освобождения выделенных участков памяти не регламентируется. Однако если указатель не был получен с помощью malloc или calloc, то его освобождение является грубой ошибкой. Обращение по указателю после его освобождения — также ошибка. Правильным было бы записать все, что нужно, перед освобождением:

for (p = head; p != NULL; p = q)

Выделение памяти под двумерный массив

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

Например, есть указатель А: int ** A ;

Сначала создают массив, состоящий из указателей, которые будут отвечать количеству строк:

A = (int **) malloc (N * sizeof(int *)). Здесь важно указать тип указателя, а не int. Потому что в этом массиве, на который указывает A, будут храниться указатели, а не int.

Далее инициализируют уже сами элементы этого массива указателей путем запуска цикла:

for (int i = 0 ; i < N ; ++i).

Для каждого A[i] проводим инициализацию по отдельности. По сути этого разыменование А со смещением i:

A[i] = (int *) malloc (M * sizeof (int)). Указатели A[i] уже указывают на массив int. Если бы был другой тип, то указывали бы на него.

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

A = (int **) malloc (N * sizeof(int *)).

for (int i = 0 ; i < N ; ++i).

Нестандартные функции динамического выделения памяти

Когда требуемый размер массива становится известен, то используют оператор new из языка Си ++, который является расширенной версией языка Си. В скобках указывают размер массива:

При отрицательном или нулевом N использовать оператор new нельзя.

При динамическом распределении памяти основными операциями являются new и delete.

Операция new принимает в качестве аргумента тип динамически размещаемого объекта и возвращает на него указатель.

Например, оператор Node *newPtr = new NodeA0); используется для выделения области памяти размером sizeof(Node) байтов, а также его применяют для сохранения указателя на данной области памяти в указателе newPtr.

Если планируется использовать память повторно, после того, как динамический массив в какой-то момент работы программы перестанет быть нужным, то ее освобождают с помощью delete[],

При этом не указывают размерность массива. Операция delete освобождает область памяти, выделенную при помощи оператора new. Таким образом, она возвращает системе эту область памяти для дальнейшего распределения. Чтобы освободить память, которая была динамически выделена предыдущим оператором, применяют оператор delete newPtr;

Иногда выделение памяти под динамические массивы осуществляют с помощью двух языков Си и Си++ одновременно: операции new и функции malloc.

int *a = new int[n];

double *b = (double *)malloc(n * sizeof (double));

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

В третьей строке применяется функция malloc, которая в данном случае выделяет память под n элементов типа double. Для того, чтобы освободить память, выделенную с помощью функции malloc, применяют функцию free. Память не обнуляется при ее выделении. Динамический массив нельзя инициировать.

Перераспределение памяти

Динамическое перераспределение памяти позволяет создавать и поддерживать динамические структуры данных. Оно дает возможность осуществлять увеличение области памяти в процессе выполнения программы, для того чтобы хранить новые узлы и освобождать ресурсы памяти, в которых уже нет необходимости.

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

Функция realloc осуществляет перераспределение памяти. Она меняет размер динамически выделяемой области памяти, адресуемой указателем ptr, на новый размер size.

Realloc может возвращать адрес новой области памяти:

realloc(void *ptr, size_t size);

Если ptr равен NULL, то realloc ведет себя подобно функции malloc.

Поведение функции realloc будет неопределенным, если:

  • значение ptr не было возвращено функциями calloc, malloc или realloc;
  • пространство памяти было освобождено функцией free, и ptr указывают на него.

Size указывают в абсолютном значении.

Важные моменты в перераспределении памяти с помощью функции realloc:

  1. Если существующее пространство меньше по размеру, чем size, то в конце будет выделяться новое неинициализированное непрерывное пространство, при этом предыдущие данные пространства будут сохранены.
  2. Значение, равное NULL, будет возвращено, если realloc не может выделить запрашиваемое пространство, а в указанном ptr пространстве содержимое остается нетронутым.
  3. Realloc будет действовать, как функция free, если size=0, а ptr не равен NULL.
  4. Если первым параметром функции realloc использовать NULL, то можно получить эффект, который достигается с помощью функции malloc с тем же значением size.

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

Например, при создании связанного списка linked list и применения realloc, чтобы выделить для цепочки пространство памяти, может оказаться, что оно будет перемещаться. В таком случае, указатели будут адресованы не в место их расположения в настоящий момент, а в то место, где были размещены последовательные звенья цепочки.

Пример использования функции realloc:

p2 = realloc(p1, new_size);

if (p2 1= NULL) p1 = p2;

Необходимо учитывать, что realloc работает с ранее выделенной памятью и старыми строками. Добавление новых строк и выделение памяти осуществляется посредством функций calloc или malloc.

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

Теги: Си память, malloc, calloc, realloc, free, Ошибки выделения памяти, Висячие указатели, Динамические массивы, Многомерные динамические массивы.

  • Функция malloc
  • Освобождение памяти с помощью free
  • Работа с двумерными и многомерными массивами
  • Функция calloc
  • Функция realloc
  • Типичные ошибки при динамической работе с памятью
  • Различные аргументы realloc и malloc

malloc

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

Для выделения памяти на куче в си используется функция malloc (memory allocation) из библиотеки stdlib.h

void * malloc(size_t size);

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

#include #include #include void main()

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

#include #include #include void main() < const int maxNumber = 100; int *p = NULL; unsigned i, size; do < printf("Enter number from 0 to %d: ", maxNumber); scanf("%d", &size); if (size < maxNumber) < break; >> while (1); p = (int*) malloc(size * sizeof(int)); for (i = 0; i < size; i++) < p[i] = i*i; >for (i = 0; i < size; i++) < printf("%d ", p[i]); >_getch(); free(p); >
p = (int*) malloc(size * sizeof(int));

Здесь (int *) – приведение типов. Пишем такой же тип, как и у указателя.
size * sizeof(int) – сколько байт выделить. sizeof(int) – размер одного элемента массива.
После этого работаем с указателем точно также, как и с массивом. В конце не забываем удалять выделенную память.

Теперь представим на рисунке, что у нас происходило. Пусть мы ввели число 5.

Выделение памяти.

Функция malloc выделила память на куче по определённому адресу, после чего вернула его. Теперь указатель p хранит этот адрес и может им пользоваться для работы. В принципе, он может пользоваться и любым другим адресом.
Когда функция malloc «выделяет память», то она резервирует место на куче и возвращает адрес этого участка. У нас будет гарантия, что компьютер не отдаст нашу память кому-то ещё. Когда мы вызываем функцию free, то мы освобождаем память, то есть говорим компьютеру, что эта память может быть использована кем-то другим. Он может использовать нашу память, а может и нет, но теперь у нас уже нет гарантии, что эта память наша. При этом сама переменная не зануляется, она продолжает хранить адрес, которым ранее пользовалась.

Это очень похоже на съём номера в отеле. Мы получаем дубликат ключа от номера, живём в нём, а потом сдаём комнату обратно. Но дубликат ключа у нас остаётся. Всегда можно зайти в этот номер, но в нём уже кто-то может жить. Так что наша обязанность – удалить дубликат.

Иногда думают, что происходит «создание» или «удаление» памяти. На самом деле происходит только перераспределение ресурсов.

Освобождение памяти с помощью free

Т еперь рассмотри, как происходит освобождение памяти. Переменная указатель хранит адрес области памяти, начиная с которого она может им пользоваться. Однако, она не хранит размера этой области. Откуда тогда функция free знает, сколько памяти необходимо освободить?

  • 1. Можно создать карту, в которой будет храниться размер выделенного участка. Каждый раз при освобождении памяти компьютер будет обращаться к этим данным и получать нужную информацию.
  • 2. Второе решение более распространено. Информация о размере хранится на куче до самих данных. Таким образом, при выделении памяти резервируется места больше и туда записывается информация о выделенном участке. При освобождении памяти функция free «подсматривает», сколько памяти необходимо удалить.

Работа с двумерными и многомерными массивами

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

#include #include #include #define COL_NUM 10 #define ROW_NUM 10 void main() < float **p = NULL; unsigned i; p = (float**) malloc(ROW_NUM * sizeof(float*)); for (i = 0; i < ROW_NUM; i++) < p[i] = (float*) malloc(COL_NUM * sizeof(float)); >//Здесь какой-то важный код for (i = 0; i < ROW_NUM; i++) < free(p[i]); >free(p); >
  • 1. Создавать массивы «неправильной формы», то есть массив строк, каждая из которых имеет свой размер.
  • 2. Работать по отдельности с каждой строкой массива: освобождать память или изменять размер строки.

Создадим «треугольный» массив и заполним его значениями

#include #include #include #define SIZE 10 void main() < int **A; int i, j; A = (int**) malloc(SIZE * sizeof(int*)); for (i = 0; i < SIZE; i++) < A[i] = (int*) malloc((i + 1) * sizeof(int)); >for (i = 0; i < SIZE; i++) < for (j = i; j >0; j--) < A[i][j] = i * j; >> for (i = 0; i < SIZE; i++) < for (j = i; j >0; j--) < printf("%d ", A[i][j]); >printf("\n"); > for (i = SIZE-1; i > 0; i--) < free(A[i]); >free(A); _getch(); >

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

calloc

Ф ункция calloc выделяет n объектов размером m и заполняет их нулями. Обычно она используется для выделения памяти под массивы. Синтаксис

void* calloc(size_t num, size_t size);

realloc

Е щё одна важная функция – realloc (re-allocation). Она позволяет изменить размер ранее выделенной памяти и получает в качестве аргументов старый указатель и новый размер памяти в байтах:

void* realloc(void* ptr, size_t size)

Функция realloc может как использовать ранее выделенный участок памяти, так и новый. При этом не важно, меньше или больше новый размер – менеджер памяти сам решает, где выделять память.
Пример – пользователь вводит слова. Для начала выделяем под слова массив размером 10. Если пользователь ввёл больше слов, то изменяем его размер, чтобы хватило места. Когда пользователь вводит слово end, прекращаем ввод и выводим на печать все слова.

#include #include #include #include #define TERM_WORD "end" #define SIZE_INCREMENT 10 void main() < //Массив указателей на слова char **words; //Строка, которая используется для считывания введённого пользователем слова char buffer[128]; //Счётчик слов unsigned wordCounter = 0; //Длина введённого слова unsigned length; //Размер массива слов. Для уменьшения издержек на выделение памяти //каждый раз будем увеличивать массив слов не на одно значение, а на //SIZE_INCREMENT слов unsigned size = SIZE_INCREMENT; int i; //Выделяем память под массив из size указателей words = (char**) malloc(size*sizeof(char*)); do < printf("%d: ", wordCounter); scanf("%127s", buffer); //Функция strcmp возвращает 0, если две строки равны if (strcmp(TERM_WORD, buffer) == 0) < break; >//Определяем длину слова length = strlen(buffer); //В том случае, если введено слов больше, чем длина массива, то //увеличиваем массив слов if (wordCounter >= size) < size += SIZE_INCREMENT; words = (char**) realloc(words, size*sizeof(char*)); >//Выделяем память непосредственно под слово //на 1 байт больше, так как необходимо хранить терминальный символ words[wordCounter] = (char*) malloc(length + 1); //Копируем слово из буффера по адресу, который //хранится в массиве указателей на слова strcpy(words[wordCounter], buffer); wordCounter++; > while(1); for (i = 0; i < wordCounter; i++) < printf("%s\n", words[i]); >_getch(); for (i = 0; i < wordCounter; i++) < free(words[i]); >free(words); >

Хочу обратить внимание, что мы при выделении памяти пишем sizeof(char*), потому что размер указателя на char не равен одному байту, как размер переменной типа char.

Ошибки при выделении памяти

1. Бывает ситуация, при которой память не может быть выделена. В этом случае функция malloc (и calloc) возвращает NULL. Поэтому, перед выделением памяти необходимо обнулить указатель, а после выделения проверить, не равен ли он NULL. Так же ведёт себя и realloc. Когда мы используем функцию free проверять на NULL нет необходимости, так как согласно документации free(NULL) не производит никаких действий. Применительно к последнему примеру:

#include #include #include #include #define TERM_WORD "end" #define SIZE_INCREMENT 10 void main() < char **words; char buffer[128]; unsigned wordCounter = 0; unsigned length; unsigned size = SIZE_INCREMENT; int i; if (!(words = (char**) malloc(size*sizeof(char*)))) < printf("Error: can't allocate memory"); _getch(); exit(1); >do < printf("%d: ", wordCounter); scanf("%127s", buffer); if (strcmp(TERM_WORD, buffer) == 0) < break; >length = strlen(buffer); if (wordCounter >= size) < size += SIZE_INCREMENT; if (!(words = (char**) realloc(words, size*sizeof(char*)))) < printf("Error: can't reallocate memory"); _getch(); exit(2); >> if (!(words[wordCounter] = (char*)malloc(length + 1))) < printf("Error: can't allocate memory"); _getch(); exit(3); >strcpy(words[wordCounter], buffer); wordCounter++; > while(1); for (i = 0; i < wordCounter; i++) < printf("%s\n", words[i]); >_getch(); for (i = 0; i < wordCounter; i++) < free(words[i]); >free(words); >

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

2. Изменение указателя, который хранит адрес выделенной области памяти. Как уже упоминалось выше, в выделенной области хранятся данные об объекте — его размер. При удалении free получает эту информацию. Однако, если мы изменили указатель, то удаление приведёт к ошибке, например

#include #include #include void main() < int *p = NULL; if (!(p = (int*) malloc(100 * sizeof(int)))) < printf("Error"); exit(1); >//Изменили указатель p++; //Теперь free не может найти метаданные об объекте free(p); //На некоторых компиляторах ошибки не будет _getch(); >

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

3. Использование освобождённой области. Почему это работает в си, описано выше. Эта ошибка выливается в другую – так называемые висячие указатели (dangling pointers или wild pointers). Вы удаляете объект, но при этом забываете изменить значение указателя на NULL. В итоге, он хранит адрес области памяти, которой уже нельзя воспользоваться, при этом проверить, валидная эта область или нет, у нас нет возможности.

#include #include #include #define SIZE 10 void main() < int *p = NULL; int i; p = (int*) malloc(SIZE * sizeof(int)); for (i = 0; i < SIZE; i++) < p[i] = i; >free(p); for (i = 0; i < SIZE; i++) < printf("%i ", p[i]); >_getch(); >

Эта программа отработает и выведет мусор, или не мусор, или не выведет. Поведение не определено.

Если же мы напишем

free(p); p = NULL;

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

4. Освобождение освобождённой памяти. Пример

#include #include void main()

Здесь дважды вызывается free для переменной a. При этом, переменная a продолжает хранить адрес, который может далее быть передан кому-нибудь для использования. Решение здесь такое же как и раньше — обнулить указатель явно после удаления:

#include #include void main() < int *a, *b; a = (int*) malloc(sizeof(int)); free(a); a = NULL; b = (int*) malloc(sizeof(int)); free(a);//вызов free(NULL) ничего не делает free(b); b = NULL; _getch(); >

5. Одновременная работа с двумя указателями на одну область памяти. Пусть, например, у нас два указателя p1 и p2. Если под первый указатель была выделена память, то второй указатель может запросто скомпрометировать эту область:

#include #include #include #define SIZE 10 void main() < int *p1 = NULL; int *p2 = NULL; size_t i; p1 = malloc(sizeof(int) * SIZE); p2 = p1; for (i = 0; i < SIZE; i++) < p1[i] = i; >p2 = realloc(p1, SIZE * 5000 * sizeof(int)); for (i = 0; i < SIZE; i++) < printf("%d ", p1[i]); >printf("\n"); for (i = 0; i < SIZE; i++) < printf("%d ", p2[i]); >_getch(); >

Рассмотрим код ещё раз.

int *p1 = NULL; int *p2 = NULL; size_t i; p1 = malloc(sizeof(int) * SIZE); p2 = p1;

Теперь оба указателя хранят один адрес.

p2 = realloc(p1, SIZE * 5000 * sizeof(int));

А вот здесь происходит непредвиденное. Мы решили выделить под p2 новый участок памяти. realloc гарантирует сохранение контента, но вот сам указатель p1 может перестать быть валидным. Есть разные ситуации. Во-первых, вызов malloc мог выделить много памяти, часть которой не используется. После вызова ничего не поменяется и p1 продолжит оставаться валидным. Если же потребовалось перемещение объекта, то p1 может указывать на невалидный адрес (именно это с большой вероятностью и произойдёт в нашем случае). Тогда p1 выведет мусор (или же произойдёт ошибка, если p1 полезет в недоступную память), в то время как p2 выведет старое содержимое p1. В этом случае поведение не определено.

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

Различные аргументы realloc и malloc.

При вызове функции malloc, realloc и calloc с нулевым размером поведение не определено. Это значит, что может быть возвращён как NULL, так и реальный адрес. Им можно пользоваться, но к нему нельзя применять операцию разадресации.
Вызов realloc(NULL, size_t) эквиваленте вызову malloc(size_t).
Однако, вызов realloc(NULL, 0) не эквивалентен вызову malloc(0) 🙂 Понимайте это, как хотите.

Примеры

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

Скользящее среднее.

Пусть есть ряд
1, 4, 4, 6, 7, 8, 9, 11, 12, 11, 15
Тогда если период среднего будет 3, то мы получим ряд
(1+4+4)/3, (4+4+6)/3, (4+6+7)/3, (6+7+8)/3, (7+8+9)/3, (8+9+11)/3, (9+11+12)/3, (11+12+11)/3, (12+11+15)/3
Видно, что сумма находится в «окне», которое скользит по ряду. Вместо того, чтобы каждый раз в цикле находить сумму, можно найти её для первого периода, а затем вычитать из суммы крайнее левое значение предыдущего периода и прибавлять крайнее правое значение следующего.
Будем запрашивать у пользователя числа и период, а затем создадим новый массив и заполним его средними значениями.

#include #include #include #define MAX_INCREMENT 20 void main() < //Считанные числа float *numbers = NULL; //Найденные значения float *mean = NULL; float readNext; //Максимальный размер массива чисел unsigned maxSize = MAX_INCREMENT; //Количество введённых чисел unsigned curSize = 0; //Строка для считывания действия char next[2]; //Шаг unsigned delta; //float переменная для хранения шага float realDelta; unsigned i, j; //Сумма чисел float sum; numbers = (float*) malloc(maxSize * sizeof(float)); do < //Пока пользователь вводит строку, которая начинается с y или Y, //то продолжаем считывать числа printf("next? [y/n]: "); scanf("%1s", next); if (next[0] == 'y' || next[0] == 'Y') < printf("%d. ", curSize); scanf("%f", &readNext); if (curSize >= maxSize) < maxSize += MAX_INCREMENT; numbers = (float*) realloc(numbers, maxSize * sizeof(float)); >numbers[curSize] = readNext; curSize++; > else < break; >> while(1); //Считываем период, он должен быть меньше, чем //количество элементов в массиве. Если оно равно, //то результатом станет среднее арифметическое всех введённых чисел do < printf("enter delta (>=%d): ", curSize); scanf("%d", &delta); if (delta > while(1); realDelta = (float) delta; //Находим среднее для первого периода mean = (float*) malloc(curSize * sizeof(float)); sum = 0; for (i = 0; i < delta; i++) < sum += numbers[i]; >//Среднее для всех остальных mean[0] = sum / delta; for (i = delta, j = 1; i < curSize; i++, j++) < sum = sum - numbers[j-1] + numbers[i]; mean[j] = sum / realDelta; >//Выводим. Чисел в массиве mean меньше на delta curSize = curSize - delta + 1; for (i = 0; i < curSize; i++) < printf("%.3f ", mean[i]); >free(numbers); free(mean); _getch(); >

Это простой пример. Большая его часть связана со считыванием данных, вычисление среднего всего в девяти строчках.

2. Сортировка двумерного массива. Самый простой способ сортировки — перевести двумерный массив MxN в одномерный размером M*N, после чего отсортировать одномерный массив, а затем заполнить двумерный массив отсортированными данными. Чтобы не тратить место под новый массив, мы поступим по-другому: если проходить по всем элементам массива k от 0 до M*N, то индексы текущего элемента можно найти следующим образом:
j = k / N;
i = k — j*M;
Заполним массив случайными числами и отсортируем

#include #include #include #include #define MAX_SIZE_X 20 #define MAX_SIZE_Y 20 void main() < int **mrx = NULL; int tmp; unsigned i, j, ip, jp, k, sizeX, sizeY, flag; printf("cols: "); scanf("%d", &sizeY); printf("rows: "); scanf("%d", &sizeX); //Если введённый размер больше MAX_SIZE_?, то присваиваем //значение MAX_SIZE_? sizeX = sizeX > //Выводим массив for (i = 0; i < sizeX; i++) < for (j = 0; j < sizeY; j++) < printf("%6d ", mrx[i][j]); >printf("\n"); > //Сортируем пузырьком, обходя все sizeX*sizeY элементы do < flag = 0; for (k = 1; k < sizeX * sizeY; k++) < //Вычисляем индексы текущего элемента j = k / sizeX; i = k - j*sizeX; //Вычисляем индексы предыдущего элемента jp = (k-1) / sizeX; ip = (k-1) - jp*sizeX; if (mrx[i][j] >mrx[ip][jp]) < tmp = mrx[i][j]; mrx[i][j] = mrx[ip][jp]; mrx[ip][jp] = tmp; flag = 1; >> > while(flag); printf("-----------------------\n"); for (i = 0; i < sizeX; i++) < for (j = 0; j < sizeY; j++) < printf("%6d ", mrx[i][j]); >free(mrx[i]); printf("\n"); > free(mrx); _getch(); >

3. Бином Ньютона. Создадим треугольную матрицу и заполним биномиальными коэффициентами

#include #include #include #define MAX_BINOM_HEIGHT 20 void main() < int** binom = NULL; unsigned height; unsigned i, j; printf("Enter height: "); scanf("%d", &height); height = height binom[0][0] = 1; for (i = 1; i < height; i++) < binom[i][0] = binom[i][i] = 1; for (j = i - 1; j >0; j--) < binom[i][j] = binom[i-1][j-1] + binom[i-1][j]; >> for (i = 0; i < height; i++) < for (j = 0; j free(binom[i]); printf("\n"); > free(binom); _getch(); >

Если Вы желаете изучать этот материал с преподавателем, советую обратиться к репетитору по информатике

ru-Cyrl 18- tutorial Sypachev S.S. 1989-04-14 sypachev_s_s@mail.ru Stepan Sypachev students

email

Всё ещё не понятно? – пиши вопросы на ящик

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *