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

Пусть нужна матрица, размер которой определяется во время работы программы. Можно предложить два способа решения этой задачи. Первый способ основан на использовании одномерного массива для хранения элементов матрицы. Выделение памяти для такого массива можно выполнить с помощью функции 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. Методы организации данных в памяти ЭВМ

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

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

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

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

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

Время выполнения программ

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

Время выполнения программы обычно определяют как функцию от длины исходных данных. Обычно говорят, что время выполнения программы выражается функцией T(n) от входных данных размера n.

Для многих программ время выполнения является функцией входных данных, а не их размера. В этом случае T(n) определяется как функция времени выполнения программы в наихудшем случае, т.е. как максимум времени выполнения по всем входным данным размера n. Также иногда рассматривают T_ср(n) как среднее время выполнения по всем входным данным размера n. На практике среднее время найти сложнее, чем наихудшее.

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

Для описания скорости роста функций времени выполнения программ используется O-символика. Например, когда говорят, что время выполнения T(n) некоторой программы имеет порядок O(n²) (читается «о-большое от n в квадрате» или «о от n в квадрате»), то подразумевают, что существуют положительные константы c и n₀ такие, что для всех n³n₀ выполняется неравенство T(n)£ T¢(n), где T¢(n)=c×n².

Пример. Пусть T₁(n)=(n+5)². Тогда T₁(n) будет иметь порядок O(n²). Действительно, если положить n₀=1 и c=37, то легко показать, что для n³1 будет выполняться неравенство (n+5)²£T₂(n), T₂(n)=36×n².

В общем случае будем говорить, что T(n) имеет порядок O(f(n)), если существуют положительные константы c и n₀ такие, что для всех n³n₀ выполняется неравенство T(n)£c×f(n).

Пример. Пусть T₃(n)=3×n³+2×n². Данная функция имеет порядок O(n³). Действительно, если положить n0=0 и c=5, то легко показать, что для n³0 будет выполняться неравенство 3×n³+2×n²£5×n³. Можно сказать, что T₃(n)=3×n³+2×n² имеет порядок O(n⁴), но это более слабое утверждение, чем то, что T₃(n)=3×n³+2×n² имеет порядок O(n³).

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

Пример. Пусть одна и та же задача может быть решена с помощью двух программ P₁, P₂ или P₃, имеющих функции времени T₁(n)=(n+5)², T₂(n)=36×n², T₃(n)=3×n³+2×n² соответственно. Значения данных функций для различных значений n сведены в табл.6.1. Из таблицы видно, что функция T₃(n) для n=1 и n=2 имеет меньшее значение, чем функция T₁(n). Поэтому несмотря на то, что функция T₃(n) имеет порядок O(n³), а функция T₁(n) - O(n²), использование программы P₃ при n=1 и n=2 более предпочтительно, чем использование программы P₁. Также функция T₃(n) для n=1,2,…,11 имеет меньшее значение, чем функция T₂(n). Поэтому для n=1,2,…,11 предпочтительнее использовать программу P_З чем программу P₂, несмотря на то, что порядок функции T₃(n) - O(n³), а функция T₂(n) - O(n²).

Таблица 6.1