Частично динамическая матрица

Статический массив указателей позволяет строить частично динамическую или полудинамическую “матрицу”. В ней количество строк (обозначим n) фиксируется в виде константы и меняться не может. Количество элементов в строках может быть как константой, так и переменной. Более того, оно не обязательно должно быть одинаковым для всех строк. Работа с такой матрицей выполняется следующим образом:

1) Объявляем статический массив указателей размерности n, соответствующей количеству строк:

const n=5; int * M[n];

2) Определяем одинаковое для всех строк количество элементов в каждой строке:

int m; cin>>m;

3) Память для каждой строки создаваемой матрицы резервируется не во время компиляции, как для массива указателей или в случае со статической матрицей, а во время выполнения с помощью известной операции new

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

M[i]= new int[m];

Кроме этого, в i -й элемент массива указателей M[i] помещается адрес начала i -й строки.

4) После этого доступ к элементам такой матрицы можно выполнять, как и для обычной статической матрицы matr, с помощью двух индексов: M[i][j].

Такую структуру данных можно назвать также статический массив динамических одномерных массивов. При работе с такой “матрицей” необходимо правильно пользоваться указателями для организации циклов вместо индексов (см. § 5). Связано это с тем, что имеется существенное отличие в распределении памяти для такой частично динамической “матрицы”. Её строки не обязательно располагаются рядом, то есть первый элемент строки, например, M[1][0] не обязательно будет находиться в памяти рядом с последним элементом предыдущей строки (M[0][m-1]). Это объясняется тем, что операция new выделяет память для нового одномерного массива не обязательно рядом с предыдущим массивом (строкой матрицы). Память выделяется там, где есть свободный непрерывный участок требуемого размера (у нас m*4 байт). Тогда из отмеченной выше особенности следует, что после выполнения следующего фрагмента

int *p=&M[0][m-1]; p++;

в p не обязательно будет адрес первого элемента следующей строки (& M[1][0]).

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

p=&M[0][0]; p++;

в p обязательно будет адрес элемента M[0][1].

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

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

delete[]M[i];

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

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

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

1) объявляем одномерный массив, в котором будут храниться количество элементов в каждой строке:

int arr_of_size[n];

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

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

3) Аналогично резервируем память для каждой строки матрицы, размер которой берём из массива arr_of_size:

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

M[i]= new int[arr_of_size[i]];

Работа с такой “матрицей” выполняется аналогично, только надо учитывать, что тело цикла для анализа, например, всех элементов строки выполняется не одинаковое для всех строк m раз, а разное количество, то есть arr_of_size[i] раз, где i — номер строки матрицы.

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

for (int i=0; i<n; i++) M[i]=new int[i+1];

В первой по порядку строке (i=0) резервируем память для одного элемента, во второй строке – для двух и т. д., в i -й строке резервируем память для (i+1) элемента Другими словами, создаём в памяти нижний треугольник квадратной “матрицы” относительно главной диагонали.