12. Динамические массивы. Особенности обработки динамических массивов.

При определении статического массива: тип имя_массива [количество_элементов] , имя_массива становится указателем на область памяти, выделяемой для размещения элементов массива. Количество элементов должно быть константой. Таким образом, размеры памяти, выделяемой под массив, заданы в определении массива. Но иногда нужно, чтобы размеры памяти были не фиксированными, а выделялись в ходе выполнения программы при решении конкретной задачи.

Формирование массивов с переменными размерами можно организовать с помощью указателей и средств для динамического выделения памяти. Эти средства описаны в файле <alloc.h>. Функции malloc() и calloc() динамически выделяют память в соответствии со значениями их параметров и возвращают адрес начала выделенного участка памяти. Тип возвращаемого значения указателя void *. Его можно преобразовать к указателю любого типа с помощью явного приведения типа. Функция free(void *) освобождает память, выделенную с помощью malloc() или calloc().

int *p;

p=(int *)malloc(size); //Указателю на целое p присваивается адрес начала выделенной области памяти размером size байт.

p=(int *)calloc(n, size); //Указателю на целое p присваивается адрес начала выделенной области памяти размером n*size байт.

free(p); //Освобождает выделенную по адресу p память. Преобразование указателя любого типа к типу void * осуществляется автоматически, так что в качестве фактического параметра можно подставить указатель любого типа без явного приведения типов.

Пример формирования одномерного динамического массива

//lab11_1

#include <stdio.h>

#include <conio.h>

#include <alloc.h>

main()

{ float *p,d;

int i,n;

printf("\n input n:");

scanf("%d",&n);

p=(float *)malloc(n*sizeof(float));

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

{printf("x[%d]=",i);

scanf("%f",&d);

p[i]=d;

}

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

{ if (i%4==0) printf("\n");

printf("\t x[%d]=%6.2f",i,p[i]);

}

free(p);

getch();

}

Доступ к участкам выделенной памяти выполняется с помощью операции индексирования: p[i].

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

1. Определяем указатель на массив указателей , задающий адреса начала строк матрицы: тип **uk.

2. Вводим размеры матрицы n,m.

3. Создаём динамический массив указателей на указатели начала строк : uk=(тип **)malloc(n*sizeof(тип *));

4. В цикле выделяем память под n массивов – строк по m элементов в каждом: for (i=0;i<n;i++) uk[i]=(тип *)malloc(m*sizeof(тип));

5. Обработка массива (работа с индексированными элементами uk[i][j]).

6. В цикле освобождаем память, занятую под n массивов – строк : for (i=0;i<n;i++) free(uk[i]);

7. Освобождаем память, занятую под массив указателей : free(uk).

Пример обработки двумерного динамического массива

Пример программы, создающая динамическую матрицу размером n*n, заполняющая матрицу случайными числами. Вычисляет сумму каждой строки и помещает суммы строк в одномерный динамический массив.

//lab11_2

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include <alloc.h>

void main()

{ int n,j,i;

float ** matr; float * mass; // Объявляем matr - указатель на массив указателей и //mass – указатель на одномерный массив

clrscr();

printf("Введите размер квадратной матрицы n: "); scanf("%d",&n);

mass=(float *)malloc(n*sizeof(float )); // Выделяем память под одномерный массив

if (mass==NULL)

{ puts("не создан динамический массив!");

return;}

matr=(float **)malloc(sizeof(float *)*n); //Выделяем память под массив указателей

if (matr==NULL)

{ puts("не создан динамический массив!");

return;}

randomize();

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

{ matr[i]=(float *)malloc(sizeof(float)*n); // Выделяем память под i-ю строку

if (matr[i]==NULL)

{ puts("не создан динамический массив!");

return;}

for (j=0;j<n;j++) matr[i][j]=random(100);

}

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

{ mass[i]=0;

for (j=0;j<n;j++)

mass[i]+=matr[i][j];

}

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

{ for (j=0;j<n;j++)

printf("\t%6.2f",matr[i][j]);

printf("\n");

}

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

printf("\n сумма %d строки %8.2f",i,mass[i]);

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

free(matr[i]); //Освобождаем память i – й строки

free(matr); // Освобождаем память массива указателей

free(mass); // Освобождаем память массива сумм

getch();

}

ИНДЕКСАЦИЯ В МАССИВАХ

Указатели и массивы тесно связаны друг с другом. Имя массива без индекса — это указатель на первый (начальный) элемент массива. Рассмотрим, например, следующий массив:

char p[10];

Следующие два выражения идентичны:

p &p[0]

Выражение

p == &p[0]

принимает значение ИСТИНА, потому что адрес 1-го элемента массива — это то же самое, что и адрес массива.

Как уже указывалось, имя массива без индекса представляет собой указатель. И наоборот, указатель можно индексировать как массив. Рассмотрим следующий фрагмент программы:

int *p, i[10]; p = i; p[5] = 100; /* в присваении используется индекс */ *(p+5) = 100; /* в присвоении используется адресная арифметика */

Оба оператора присваивания заносят число 100 в 6-й элемент массива i. Первый из них индексирует указатель p, во втором применяются правила адресной арифметики. В обоих случаях получается один и тот же результат. (Подробно указатели и адресная арифметика рассматриваются в главе 5.)

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

a &a[0][0]

Более того, к элементу (0,4)[1] можно обратиться двумя способами: либо указав индексы массива: а[0][4], либо с помощью указателя: *((int*)а+4). Аналогично для элемента (1,2): а[1][2] или*((int*)а+12). В общем виде для двухмерного массива справедлива следующая формула:

a[j][k] эквивалентно *((базовый_тип*)а+(j*длина_строки)+k)

Правила адресной арифметики требуют явного преобразования указателя на массив в указатель на базовый тип (см. главу 5). Указатели используются для обращения к элементам массива потому, что часто операции адресной арифметики выполняются быстрее, чем индексация массива.

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

int num[10][10]; /* ... */ void pr_row(int j) { int *p, t; p = (int *) &num[j][0]; /* вычисление адреса 1-го элемента строки номер j */ for(t=0; t<10; ++t) printf("%d ", *(p+t)); }

Эту функцию можно обобщить, включив в список аргументов номер строки, длину строки и указатель на 1-й элемент:

void pr_row(int j, int row_dimension, int *p) { int t; p = p + (j * row_dimension); for(t=0; t<row_dimension; ++t) printf("%d ", *(p+t)); } /* ... */ void f(void) { int num[10][10]; pr_row(0, 10, (int *) num); /* печать 1-й строки */ }

Такой прием "понижения размерности" годится не только для двухмерных массивов, но и для любых многомерных. Например, вместо того, чтобы работать с трехмерным массивом, можно использовать указатель на двухмерный массив, причем вместо него в свою очередь можно использовать указатель на одномерный массив. В общем случае вместо того, чтобы обращаться к n-мерному массиву, можно работать с указателем на (n-1)-мерный массив. Причем этот процесс понижения размерности кончается на одномерном массиве.