Динамические “матрицы”

Динамическая “матрица” (или в отличие от частично динамической назовём её полностью динамичсеской) с одинаковым количеством элементов в строках создаётся следующим образом.

1) Динамическая “матрица” объявляется как указатель на указатель, или, лучше, как динамический массив указателей. Для объяснения этого проведём сначала аналогию с обычным одномерным массивом, например int a[10]. Для создания динамического одномерного массива его надо объявить, заменив размерность в квадратных скобках на символ “*”, который записывается после типа перед именем: int *d; и выполнить операцию d= new int [m], где m —константа или переменная.

Так как статический массив указателей объявляется, например, как int *ap[5], то динамический массив указателей объявляем, заменив формально [5] на звёздочку и записав её перед именем, то есть с помощью двух звёздочек, как было рассмотрено в предыдущем пункте:

int **D;

2) Мы знаем, что из объявления int *d не следует ещё, что в d будет адрес начала массива, может быть адрес простой целочисленной переменной. Точно также из объявления int **D; не видно, что в D будет адрес начала массива указателей. Это зависит от операции new. Если выполнить

D=new * int;

то выделяется память для размещения одного адреса на область памяти, в которой будет одно или несколько целых чисел. Нас такой вариант не устраивает, так как нам надо получить и сохранить в памяти адреса начала каждой строки матрицы. Чтобы зарезервировать память для массива указателей, в операции new после типа (* int) надо записать количество элементов данного типа, то есть количество указателей, которое также может быть как константой, так и переменной. Пусть int n; cin>>n; Тогда D=new * int[n]; выделяет память для размещения n указателей, и адрес начала этой области помещается в D. На рисунке этому этапу соответствует одна левая стрелка, над которой записано 2).

3) Теперь необходимо определить, что будет содержать каждый элемент этого массива указателей. Как и для частично динамической матрицы, определяем количество элементов в каждой строке. Пусть оно одинаковое для каждой строки: int m; cin>>m;

4) Резервируем память для каждой строки “матрицы”, то есть для числового одномерного массива, и определяем значение каждого элемента массива указателей D[i]:

for (int i=0; i<n; i++) D[i]= new int[m];

Этот этап на рисунке изображён в виде нескольких горизонтальных стрелок, над которыми записана цифра 3).

Таким образом, процесс создания динамической “матрицы” можно изобразить в виде следующего рисунка:

5) После этого доступ к элементам такой “матрицы” можно выполнять, как и для обычной статической матрицы с помощью двух индексов: D[i][j]. Но при работе с созданной динамической “матрицей” необходимо правильно пользоваться указателями для организации циклов вместо индексов. Объяснение аналогично как для частично динамической “матрицы”.

6) Удапение динамической “матрицы” выполняется в обратном порядке следующим образом

6.1) Сначала освобождаем память, выделенную для каждой строки. Так как количество таких участков памяти, в каждом из которых размещалось m чисел, соответствует количеству строк, то это выполняем в цикле n раз:

for (int i=0; i<n; i++) delete[]D[i];

Пустые квадратные скобки здесь означают, что в каждом элементе массива указателей D[i] был адрес не одного числа, а адрес одномерного массива, то есть адрес i -строки матрицы. Поэтому надо освобождать память для массива, то есть i -й строки матрицы

6.2) Освобождаем память, выделенную для массива указателей.

delete[]D;

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

Пример работы с такой “матрицей” приведен в лабораторной работе 5 (пример 1).

Как и для частично динамической “матрицы”, в строках полностью динамической матрицы может быть различное количество элементов. Здесь показан один из вариантов создания такой “матрицы”.

Объявляем указатель для динамического одномерного массива, в котором будут хранниться количество элементов в каждой строке.

int *arr_of_size;

Выделяем память для этого массива и запоминаем адрес его начала:

arr_of_size=new int[n];

Определяем значения массива, например, вводим, вообще говоря, различное количество элементов строк с экрана:

for (int i=0;i<n;i++) cin>>arr_of_size[i];

Четвёртый этап, на котором резервируется память для каждой строки “матрицы”, меняем следующим образом. Количество элементов i -й строки берём из сформированного массива arr_of_size

for (int i=0; i<n; i++) D[i]= new int[arr_of_size [i]];

Удаление такой “матрицы” из памяти выполняется аналогично, как и удаление динамической матрицы с одинаковым количеством элементов в строках. Объясняется это тем, что в операции delete размер освобождаемой памяти мы не указываем. Освобождаем память такого объёма, сколько зарезервировали с помощью операции new.

Пример работы с такой матрицей приведен в лабораторной работе 5 (пример 3).

Как и для частично динамической матрицы, можно создать “матрицу”, количество элементов в строках которой будет меняться по некоторому правилу. Например, можно создать в памяти нижний (или верхний) треугольник квадратной “матрицы” относительно главной (побочной) диагонали.

Пример работы с такой матрицей приведен в лабораторной работе 5 (пример 2).

Упражнение. Сравните динамическую матрицу со статической матрицей по следующему плану: 1) размерности матриц; 2) когда, на каком этапе выделяется память? 3) как она распределяется, как элементы матрицы расположены в памяти? 4) как осуществляется доступ к элементам матриц? 5) для какой матрицы, когда и как можно освободить память?