5.3.Выделение памяти под матрицы на этапе выполнения программы

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

double *a;

. . .

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

При этом считается, что элементы матрицы будут располагаться в массиве следующим образом: сначала идут элементы строки с индексом 0, затем элементы строки с индексом 1 и т.д., последними идут элементы строки с индексом m − 1. Каждая строка состоит из n элементов, следовательно, индекс элемента строки i и столбца j в линейном массиве равен

i * n + j

Таким образом, элементу матрицы в строке i и столбце j соответствует выражение

a[i * n + j]

Для освобождения памяти, занимаемой матрицей можно использовать функцию free:

free(a);

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

Также матрицу можно реализовать как массив указателей на ее строки, при этом память под каждую строку захватывается отдельно:

double **a; // Адрес массива указателей

int m, n; // Размеры матрицы: m строк, n столбцов

int i;

. . .

// Захватывается память под массив указателей

a = (double **) malloc(m * sizeof(double *));

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

// Выделяем память под строку с индексом i

a[i] = (double *) malloc(n * sizeof(double));

}

После этого к элементу a ij можно обращаться с помощью выражения

a[i][j]

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

for (i = 0; i < m; ++i) free(a[i]);

free(a);

Для выделения памяти под многомерные массивы лучше использовать способ, аналогичный первому способу. Например, пусть надо реализовать трехмерный вещественный массив размера m × n × k. Выделяем линейный массив вещественных чисел размером m * n * k:

double *a;

. . .

a = (double *) malloc(m * n * k * sizeof(double));

Доступ к элементу с индексами x, y, z осуществляется с помощью выражения

a[(x * n + y) * k + z].

Вопросы для повторения

1. Вопросы выделение памяти на этапе компиляции и на этапе выполнения программы

2. Функции malloc и free.

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

4. Выделение памяти под многомерные массивы на этапе выполнения программы.

Резюме по теме

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

Тема 6. Методы организации данных в памяти ЭВМ

Цели и задачи изучения темы

В данной теме рассматриваются различные методы организации данных в памяти ЭВМ.

6.1.Абстрактные типы данных

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

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