6.4 Основные алгоритмы обработки двумерных массивов

6.4.1 Понятие многомерых массивов

Элементом массива может быть в свою очередь тоже массив. Размерность или количество измерений массива определяется количеством индексов при обращении к элементам массива. Массивы бывают одномерные, двухмерные, трехмерные и т.д.

Общий вид объявления массива:

<имя_типа> <имя_массива> [k1] [k2] … [kn] ;

где k1, k2, …, kn - количество элементов массива - константы или константные выражения по 1, 2, …, n измерениям. Причем значения индексов могут изменяться от 0 до ki-1.

Описание двумерного массива (или матрицы) строится из описания одномерного путем добавления второй размерности:

int a[4][3].

Анализ подобного описания необходимо проводить в направлении выполнения операций [], то есть слева направо. Таким образом, переменная a является массивом из четырех элементов, что следует из первой части описания a[4]. Каждый элемент a[i] этого массива в свою очередь является массивом из трех элементов типа int, что следует из второй части описания.

Имя двумерного массива с двумя индексными выражениями в квадратных скобках за ним обозначает соответствующий элемент двумерного массива и имеет тот же тип. Например, a[2][1] является величиной типа int, а именно ячейкой, в которой находится число 8, и может использоваться везде, где допускается использование величины типа int.

Примеры объявления массивов:

int C[10] [20] [15]; //трёхмерный целочисленный массив

Примеры обращение к элементам:

float B[50][20]; // двумерный вещественный массив

// из 50 строк и 20 столбцов.

Примеры обращения к его элементам :

B[0][0], B[0][1] ,.., B[i][j], …, B[4][19], …

C[i] [j] [k], ..., C[2*i] [0] [3*k+1], …

6.4.2 Динамические двумерные массивы

Обращение к элементу динамического массива осуществляется также, как и к элементам обычного массива.

Например, a[0], a[1], …, a[19], c[2][5] и т.д.

Другой способ обращения к элементу b[i][j] двумерного массива имеет вид:

*(*(b+i)+j).

Поясним это. Двумерный массив представляет собой массив массивов, т.е. это массив, каждый элемент которого является массивом. Имя двумерного массива также является константным указателем на начало массива. Например, int b[5][10] является массивом, состоящим из 5-ти массивов. Для обращения к b[i][j] сначала требуется обратиться к i-ой строке массива, т.е., к одномерному массиву b[i]. Для этого надо к адресу начала массива b прибавить смещение, равное номеру строки i: b+i (при сложении указателя b с i учитывается длина адресуемого элемента, т.е. i·(n·sizeof(int)), т.к. элементом массива b[i] является строка, состоящая из n элементов типа int). Затем требуется выполнить разадресацию: *(b+i). Получим массив из 10 элементов. Далее необходимо обратиться к j-му элементу полученного массива. Для получения его адреса опять применяется сложение указателя с j: *(b+i)+j (на самом деле прибавляется j·sizeof(int)). Затем применяется операция разадресации: *(*(b+i)+j). Т.о., получаем формулу для вычисления адреса элемента b[i][j]:

b+k·i·n+k·j=b+k·(i·n+j),

где k – длина в байтах одного элемента массива, b – адрес начала массива. Эта формула может быть использована в дальнейшем, например, для организации передачи в подпрограмму двумерного массива переменной размерности.

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

int i, m, n; //i – номер строки, m, n – количество строк и столбцов

puts("Введите m и n");

scanf("%d %d",&m, &n); // Ввод m, n

int **b=new int *[m]; //1

for (i=0; i<m; i++) //2

b[i]=new int[n]; //3

Здесь в операторе //1 объявляется переменная типа "указатель на указатель на int" и выделяется память под массив указателей на строки массива (m строк). В операторе //2 организуется цикл для выделения памяти под каждую строку массива. В операторе //3 выделяется память под каждую строку массива и i-му элементу массива указателей на строки присваивается адрес начала участка памяти, выделенного под строку двумерного массива. Каждая строка массива состоит из n элементов типа int.

Примечание. Для выделения динамической памяти для вещественного двумерного массива достаточно в приведенном фрагменте программы в строках //1, //3 имя типа int поменять на имя типа float.

Освобождение выделенной динамической памяти.

Динамическая память освобождается с помощью операции delete[] имя массива, например, освобождение памяти для двумерного массива b выглядит следующим образом:

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

delete [ ] b[i];

delete [ ] b;

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