30.3 Динамическое размещение одномерных массивов и строк

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

При динамическом распределении памяти для одномерных массивов следует описать указатель соответствующего типа и присвоить ему значение при помощи фунций malloc() или calloc().

Одномерный массив из n целых чисел можно создать двумя способами:

int *a, *b;

int n = 10;

a = (int *)malloc(n * sizeof(int));

b = (int *)calloc(n, sizeof(int)); // инициализация 0

Освобождение памяти, выделенной под массивы:

free(a);

free(b);

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

int *a, n = 10;

a = (int *)malloc(n * sizeof(int));

a += 2; // перешли к элементу массива с индексом 2

*a = 100; // a[2] = 100

free(a); // ошибка, т.к. а != адрес начала массива

int *a, *p, n = 10;

a = (int *)malloc(n * sizeof(int));

p = a; // сохранение адреса начала массива

a += 2;

*a = 100;

free(p); // ошибки нет

Задача. Пример программы для работы с динамическим одномерным массивом целых чисел.

// выделение памяти и ввод массива

int vvod(int **m) {

int nn;

scanf ("%d", &nn);

*m = (int *)calloc(nn, sizeof(int));

// ввод массива

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

scanf("%d", *m+i); // *m+i == &(*m)[i]

return nn;

}

// поиск минимального элемента в массиве

int fmin(int *m, int nn) {

int min = 0x7FFF;

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

if (m[i] < min)

min = *(m+i);

return min;

}

void main() {

int n, i, min;

int *b; // указатель для массива b[n]

n = vvod(&b); // передается адрес указателя, а не его значение

// печать массива

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

printf("%d ", b[i]); // b[i] == *(b+i)

min = fmin(b, n);

printf("\nmin = %d\n", min);

free(b); // освобождение памяти

}

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

void main() {

struct Book {

char name[20];

int cost;

};

struct Book *p, min;

p = (struct Book *)malloc(5 * sizeof(struct Book));

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

scanf("%s %d", (p+i)->name, &(p+i)->cost);

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

printf("%s %d\n", p[i].name, p[i].cost);

min = p[0];

for (i=1; i<5; i++)

if (min.cost > (p+i)->cost)

min = *(p+i);

printf("min: %s %d\n", min.name, min.cost);

free(p);

}

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

Задача. Пример программы для работы с динамической строкой.

char *strsave(char *s) {

char *p = NULL;

p = (char *)malloc(strlen(s) + 1);

if (p != NULL) strcpy(p, s);

return p;

}

void main() {

char s1[80], *s2;

gets(s1);

s2 = strsave(s1);

if (s2 != NULL) {

puts(s2);

free(s2);

}

}

30.4 Динамическое размещение двумерных массивов

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

Есть два стандартных подхода к динамическому созданию двумерного массива: работа с двумерным массивом как с одномерным и имитация устройства двумерного массива как массива массивов. Рассмотрим оба эти подхода.

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

Задача. Пример программы для работы с динамическим двумерным массивом как с одномерным.

void vvodMatr (int *matr, int n, int m) {

int i, j;

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

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

scanf("%d", &matr[i*m+j]); // matr+i*m+j==&matr[i*m+j]

}

void main() {

int n, m, i, j;

int *a; // указатель для массива a[n][m]

scanf("%d %d", &n, &m);

// выделение памяти под матрицу a[n][m]

a = (int *) malloc(n * m * sizeof(int));

if(!a) { // a == NULL

printf("Недостаточно памяти!\n"); return;

}

vvodMatr(a, n, m);

printf("\nМатрица --------------\n");

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

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

printf("%5d ", *(a+i*m+j)); // a[i*m+j] == *(a+i*m+j)

printf("\n");

}

free(a);

}

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

Задача. Пример программы для работы c динамическим двумерным массивом как с обычным двумерным массивом.

void vvodMatr (int *matr[], int n, int m) {

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

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

scanf("%d", &matr[i][j]);// &matr[i][j] == *(matr+i)+j

}

void freeMatr (int *matr[], int n) {

// освобождение строк матрицы

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

free(matr[i]); // matr[i] == *(matr+i)

// освобождение массива указателей

free(matr);

}

void main() {

int n, m, i, j;

int **a; // матрица a[n][m]

scanf("%d %d", &n, &m);

// выделение памяти под матрицу

// выделение памяти под n указателей на строки матрицы

a = (int **) malloc( n * sizeof(int *) );

if(!a) { printf("Недостаточно памяти!\n"); return; }

// выделение памяти под строки матрицы

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

a[i] = (int *) malloc( m * sizeof(int) );

if(!a[i]) {

printf("Недостаточно памяти!\n");

freeMatr(a, i);

return;

}

}

vvodMatr(a, n, m);

printf("\nМатрица---------------\n");

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

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

printf("%4d ", a[i][j]); // a[i][j] == *(*(a+i)+j)

printf("\n");

}

freeMatr(a, n);

}