Функции динамического распределения

Содержание

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

Память, выделяемая в С функциями динамического распределения данных, находится в т.н. динамически распределяемой области памяти (heap)[1]. Динамически распределяемая область памяти — это свободная область памяти, не используемая программой, операционной системой или другими программами. Размер динамически распределяемой области памяти заранее неизвестен, но как правило в ней достаточно памяти для размещения данных программы. Большинство компиляторов поддерживают библиотечные функции, позволяющие получить текущий размер динамически распределяемой области памяти, однако эти функции не определены в Стандарте С. Хотя размер динамически распределяемой области памяти очень большой, все же она конечна и может быть исчерпана.

Основу системы динамического распределения в С составляют функции malloc() и free(). Эти функции работают совместно. Функция malloc() выделяет память, а free() — освобождает ее. Это значит, что при каждом запросе функция malloc() выделяет требуемый участок свободной памяти, a free() освобождает его, то есть возвращает системе. В программу, использующую эти функции, должен быть включен заголовочный файл <stdlib.h>.

Прототип функции malloc() следующий:

void *malloc(size_t количество_байтов);

Здесь количество_байтов — размер памяти, необходимой для размещения данных. (Тип size_t определен в <stdlib.h> как некоторый целый без знака.) Функция malloc() возвращает указатель типа void *, поэтому его можно присвоить указателю любого типа. При успешном выполнении malloc() возвращает указатель на первый байт непрерывного участка памяти, выделенного в динамически распределяемой области памяти. Если в динамически распределяемой области памяти недостаточно свободной памяти для выполнения запроса, то память не выделяется и malloc() возвращает нуль.

При выполнении следующего фрагмента программы выделяется непрерывный участок памяти объемом 1000 байтов:


char *p;
p = malloc(1000); /* выделение 1000 байтов */

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

В следующем примере выделяется память для 50 целых. Для повышения мобильности (переносимости программы с одной машины на другую) используется оператор sizeof.


int *p;
p = malloc(50*sizeof(int));

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


p = malloc(100);
if(!p) {
printf(«Нехватка памяти.\n»);
exit(1);
}

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

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

void free(void *p)

Здесь р — указатель на участок памяти, выделенный перед этим функцией malloc(). Функцию free() ни в коем случае нельзя вызывать с неправильным аргументом, это мгновенно разрушит всю систему распределения памяти.

Подсистема динамического распределения в С используется совместно с указателями для создания различных программных конструкций, таких как связные списки и двоичные деревья. Несколько примеров использования таких конструкций приведены в части IV. Здесь рассматривается другое важное применение динамического размещения: размещение массивов.

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


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


/* Динамическое распределение строки, строка вводится
пользователем, а затем распечатывается справа налево. */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
char *s;
register int t;

s = malloc(80);

if(!s) {
printf(«Требуемая память не выделена.\n»);
exit(1);
}

gets(s);
for(t=strlen(s)-1; t>=0; t—) putchar(s[t]);
free(s);

return 0;
}


Перед первым использованием s программа проверяет, успешно ли прошло выделение памяти. Эта проверка необходима для предотвращения случайного использования нулевого указателя. Обратите внимание на то, что указатель s используется в функции gets(), а также при выводе на экран (но на этот раз уже как обыкновенный массив).

Можно также динамически выделить память для многомерного массива. Для этого нужно объявить указатель, определяющий все, кроме самого левого измерения массива. В следующем примере[2] двухмерный динамический массив содержит таблицу чисел от 1 до 10 в степенях 1, 2, 3 и 4.


#include <stdio.h>
#include <stdlib.h>

int pwr(int a, int b);

int main(void)
{
/* Объявление указателя на массив из 10 строк
в которых хранятсяцелые числа (int). */
int (*p)[10];

register int i, j;

/* выделение памяти для массива 4 x 10 */
p = malloc(40*sizeof(int));

if(!p) {
printf(«Требуемая память не выделена.\n»);
exit(1);
}

for(j=1; j<11; j++)
for(i=1; i<5; i++) p[i-1][j-1] = pwr(j, i);

for(j=1; j<11; j++) {
for(i=1; i<5; i++) printf(«%10d «, p[i-1][j-1]);
printf(«\n»);
}

return 0;
}

/* Возведение чисел в степень. */
pwr(int a, int b)
{
register int t=1;

for(; b; b—) t = t*a;
return t;
}


Программа выводит на экран следующее:


1 1 1 1
2 4 8 16
3 9 27 81
4 16 64 256
5 25 125 625
6 36 216 1296
7 49 343 2401
8 64 512 4096
9 81 729 6561
10 100 1000 10000

Указатель р в главной программе (main()) объявлен как

int (*p)[10]

Следует отметить, что скобки вокруг обязательны. Такое объявление означает, что р указывает на массив из 10 целых. Если увеличить указатель р на 1, то он будет указывать на следующие 10 целых чисел. Таким образом, р — это указатель на двухмерный массив с 10 числами в каждой строке. Поэтому р можно индексировать как обычный двухмерный массив. Разница только в том, что здесь память выделена с помощью malloc(), а для обыкновенного массива память выделяет компилятор.

Как упоминалось ранее, в C++ нужно преобразовывать типы указателей явно. Поэтому чтобы данная программа была правильной и в С, и в C++, необходимо выполнить явное приведение типа значения, возвращаемого функцией malloc(). Для этого строчку, в которой указателю р присваивается это значение, нужно переписать следующим образом:

p = (int (*)[10]) malloc(40*sizeof(int));

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

----------
[1]Применяются и другие названия: динамическая область, динамически распределяемая область, куча, неупорядоченный массив (данных).
[2]В примере динамически размещается только левое измерение массива. Однако это нетрудно сделать и для всех измерений, объявив указатель **р и разместив каждое измерение отдельно. Такой прием особенно удобен при написании функции, один из аргументов которой — двухмерный массив с неизвестными заранее размерами измерений.