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

Возможно представлять матрицу в программе как двумерный массив - естественное представление матрицы. Но при условии динамического размещения в памяти ее представление уже не такое простое. Возможны три варианта размещения в памяти и представления матрицы в программе. Во всех трех вариантах очевидно, что общий объем памяти для размещения данных матрицы должен быть S² элементов типа int.

Вариант 1 показан на рис.2

Рисунок 2. Размещение в памяти. Вариант 1.

Для данных матрицы выделяется необходимый объем памяти. В программе объявляется указатель на начало этой области. Тип этого указателя - int*. Таким образом, матрица является одномерным массивом и для того, чтобы по номеру строки (L) и столбца (R) определить индекс в одномерном массиве (N) следует выполнить вычисление: N=L*S+R.

Вариант 2 показан на рис.3.

Рисунок 3. Размещение в памяти. Вариант 2.

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

Вариант 3 показан на рис.4.

Рисунок 4. Размещение в памяти. Вариант 3

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

5.3. Определение переменных программы (вариант 1)

╧ варианта	Содержание задания	Иллюстрация
	Заполнить секторы матрицы, которые лежат выше и ниже главной и побочной диагоналей, ЛП, от левого верхнего угла вниз - вправо. Остаток матрицы заполнить нулями.

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

Переменные для функции main().

Указатель на начало линейного массива, в котором размещаются данные матрицы:

int *Ar;

Размерность массива:

int S;

Общее количество элементов массива (его использование будет видно из текста программы):

int size;

Указатель на текущий элемент массива при его выводе:

int *Cr;

Счетчик выведенных элементов:

int i;

Параметры для функции fill().

Указатель на начало линейного массива, в котором размещаются данные матрицы:

int *A;

Размерность массива:

int s;

Переменные для функции fill().

Указатель на текущий элемент массива при его обработке:

int *C;

Номера строки и столбца:

short l, r;

Текущий член линейной последовательности:

int k=1;

5.4. Разработка текста программы (вариант 1)

Текст программы начинаем с включения файлов: stdio.h, stdlib.h (в последнем определены макросы max и min).

Включаем описание функции fill() и открываем главную функцию. В главной функции объявляем ее локальные переменные, выводим приглашение и вводим значение размерности матрицы S. Размерность сравнивается с нижней и с верхней границей и, если она выходит за границы, выводится соответствующее сообщение и программа завершается (функцией exit()). Если S удовлетворяет установленным условиям, его значение выводится на экран.

Потом выделяется память для размещения матрицы. Для этого используется операция new. Она возвращает с присваиванием переменной **Ar (указатель на указатель) указательна массив из S указателей, который нужен для размещения S² элементов типа int. Таким образом, в Ar содержится значение указателя на выделенную область памяти (это будет указатель на начало массива, в котором разместятся данные матрицы).

ЗАМЕЧАНИЕ!!!!!. В динамической области памяти можно создавать двумерные массивы с помощью операции new или функции mallос. Остановимся на первом варианте, поскольку он более безопасен и прост в использовании.

При выделении памяти сразу под весь массив количество строк (самую левую размерность) можно задавать с помощью переменной или выражения, а количество столбцов должно быть константным выражением, то есть явно определено до выполнения программы. После слова new записывается тип создаваемого массива, а затем _ его размерности в квадратных скобках (аналогично описанию «обычных», нединамических массивов), например:

int n;

const int m = 5;

cin» n;

int (*a)[m] = new int [n][m]; // 1

int ** b = (int **) new int [n][m]; // 2

В этом фрагменте показано два способа создания динамического массива. В операторе 1 адрес начала выделенного с помощью new участка памяти присваивается переменной а, определенной как указатель на массив из m элементов типа int. Именно такой тип значения возвращает в данном случае операция new. Скобки необходимы, поскольку без них конструкция интерпретировалась бы как массив указателей. Всего выделяется n элементов.

В операторе 2 адрес начала выделенного участка памяти присваивается переменной b, которая описана как «указатель на указатель на int», поэтому перед присваиванием требуется выполнить преобразование типа.

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

int ** b = reinterpret_cast<int **> (new int [n][m]);

Обращение к элементам динамических массивов производится точно так же, как к элементам «обычных», с помощью конструкции вида a[i][j]. Для того чтобы понять, отчего динамические массивы описываются именно так, нужно разобраться в механизме индексации элемента массива, рассмотренном на предыдущем занятии. Поскольку для доступа к элементу массива применяется две операции разадресацпи, то переменная, в которой хранится адрес начала массива, должна быть указателем на указатель.

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

int nrow, ncol;

cout «" Введите количество строк и столбцов:";

cin» nrow» ncol;

int **a = new int *[nrow];

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

a[i] = new int [ncol];

В операторе 1 объявляется переменная типа «указатель на указатель на int» и выделяется память под массив указателей на строки массива (количество строк — nrow). В операторе 2 организуется цикл для выделения памяти под каждую строку массива. В операторе 3 каждому элементу массива указателей на строки присваивается адрес начала участка памяти, выделенного под строку двумерного массива. Каждая строка состоит из ncol элементов типа int (рис. 4.2).