5. Основные функции дрп.

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

void *malloc(size_t size);

Выделяет блок ДП размером size байт. Здесь size_t совпадает с типом unsigned int. Таким образом, блок не превосходит размер в 64K. В случае отсутствия непрерывного блока заказанной длины, возвращается NULL.

Пример 1. Выделение массива для 1000 чисел типа float.

main() {

float *ptrf;

if((ptrf =(float *) malloc(1000 * sizeof(float)) == NULL)

printf("\nОшибка при выделении памяти!");

}

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

void free(void *block);

Освобождает блок ДП, начинающийся с адреса block. Этот адрес должен находится в заголовке ранее выделенного блока . В противном случае, будет освобожден случайный блок и возникнет логическая ошибка. Динамические переменные не освобождаются автоматически при выходе из области действия и, таким образом, засоряют кучу.

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

void *realloc(void *block, size_t size);

Изменяет размер блока, на который указывает block. Новый размер блока будет равен size. Старая информация сохраняется. При нехватке свободных байт блок будет перемещен в новое место с одновременным копированием информации. Функция возвращает адрес нового блока, не изменяя переменную block.

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

main() {

float **A;

int n=5, n=10;

A = (float **)malloc(m * sizeof(float *));

if(A == NULL)

{

printf("\nОшибка при выделении памяти под массив указателей!");

exit(1);

}

for (int i=0; i< m; i++)

{

A[i] = (float *)malloc(n * sizeof(float));

if(A[i] == NULL)

{

printf("\nОшибка памяти под%d-ую строку!", i);

for(int j=0; j< i; j++)

free(A[j]);

free(A);

exit(2);

}

//…….

for(i=0; i< m; i++)

free(A[i]);

free(A);

}

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

Адресная арифметика указателей и операторы выделения динамической памяти позволяют создавать массивы динамических переменных, или динамические массивы (ДМ), синтаксически не отличимые от обычных:

любой указатель в Си по определению адресует массив элементов указуемого типа неограниченной размерности, при работе с ним можно использовать стандартную операцию индексации [] для работы с памятью как с массивом;

функция malloc и оператор new могут выделять память под массивы переменных. Размерность массива задается значением в квадратных скобках оператора new. В функции malloc объем требуемой памяти указывается как произведение размерности элемента на их количество;

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

#include <malloc.h> // Библиотека функций управления памятью

double *pd1,*pd2; // Массивы динамических переменных

pd1=new double[n1]; // Выделение памяти под ДМ

pd2 = (double*)malloc(n2*sizeof(double));

if (pd1 ==NULL || pd2==NULL) return;

for (i=0; i<n1; i++) pd1[i]=0; // Работа с ДМ

for (i=0; i<n2; i++) pd2[i]=i;

delete [ ]pd1; // Освобождение памяти

free(pd2);

Замечание: функции динамического распределения памяти malloc/free/realloc и соответствующие операции new/delete являются механизмами разных уровней и не сводятся один к другому. Функции malloc/free/realloc представляют собой библиотеку «классического» Си и транслятором не контролируются. С их помощью можно работать с обычными переменными и их массивами, но никак не с объектами. Операции new/delete используют собственную систему контроля данных в динамической памяти, к тому же при работе с объектами необходимо использовать исключительно их. Отсюда рекомендации:

· не применять для динамической переменной или динамического массива одновременно функции и операции управления динамической памятью;

· при работе с объектами использовать только операции new/delete;

· при освобождении памяти из-под динамического массива «подсказывать» транслятору, что указатель ссылается именно на массив, записывая перед указателем пустые скобки: delete [] pd1.

Массивы, создаваемые в динамической памяти, называются динамическими. Свойства указателей позволяют одинаковым образом обращаться как с динамическими, так и с обычными массивами. Во многих языках интерпретирующего типа (например, Бейсик) подобный механизм скрыт в самом трансляторе, поэтому массивы там «по своей природе» могут быть переменной размерности.

На самом деле возможность получить массив заданной размерности проблемы не решает. Программа не всегда знает, сколько какой объем данных она получит для обработки. Как можно поступить в таком случае? Есть несколько вариантов:

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

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

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

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

7. Примеры работы с динамической памятью.

// Строка как динамический массив - объединение строк

char *twoToOne(char *p1, char *p2){

char *out; int n1,n2;

for (n1=0; p1[n1]!='\0'; n1++); // Длина первой строки

for (n2=0; p2[n2]!='\0'; n2++); // Длина второй строки

if ((out = new char [n1+n2+1]) == NULL)

return NULL; // Выделить память под результат

for (n1=0; *p1!='\0';) out[n1++] = *p1++;

while(*p2!=0) out[n1++] = *p2++; // Копировать строки

out[n1] = '\0';

return out; }

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

//------ Динамический массив простых множителей числа

// Размерность массива определяется двойным вычислением

int *mnog(long vv){

long nn=vv;

for (int sz=0; vv!=1; sz++){ // Цикл определения количества

for (int i=2; vv%i!=0; i++); // Определить очередной множитель

vv = vv / i; }

int *p=new int[sz+1]; // Создать динамический массив

for (int k=0; nn!=1; k++){ // Повторный цикл заполнения

for (int i=2; nn%i!=0; i++); // Определить очередной множитель

p[k]=i; // Сохранить множитель в массиве

nn = nn / i; }

p[k]=0; return p;} // Вернуть указатель на ДМ

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

// Загрузка динамического массива целых из файла

int *loadInt(char nm[],int &n){

FILE *fd=fopen(nm,"r");

int sz=10,*p=new int[sz]; n=0;

//----------------- или p=(int*)malloc(sz*sizeof(int));

while(fscanf(fd,"%d",&p[n])==1){ // пока есть числа в файле

n++;

if (n==sz){ // массив заполнен

sz*=2; // удвоить размерность

int *q=new int[sz]; // создать новый

for (int i=0;i<n;i++) // копировать старый в новый

q[i]=p[i];

delete p; // уничтожить старый

p=q; // считать новый за старый

//--------------- или p=(int*)realloc(p,sz*sizeof(int));

}} return p;}

Отдельного обсуждения заслуживает вопрос, на сколько следует увеличивать размерность нового массива. В нашем примере она удваивается, что приводит к геометрической прогрессии или экспоненциальному росту sz=sz0*2N. На это есть свои причины. При заранее неизвестной размерности программа должна достигать этой размерности достаточно быстро (иначе возникнет эффект «вычерпывания бочки чайной ложкой»). К тому же операция перераспределения тоже является довольно затратной. Можно еще оценить и эффективность использования памяти. Занятыми окажутся от 50% до 100% ячеек последнего выделенного массива (т.е. в среднем 75%). Суммарный объем ранее выделенных массивов будет примерно равен размерности последнего (sz0*(1+2+4+…2N-1)=sz0*(2N-1)). Если они не будут использованы другими динамическими структурами, то эффективность снизится до 37.5%.

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

p = (int*) realloc(p,sizeof(int)*(i+1+N));