Многомерные массивы

Декларация многомерного массива имеет следующий формат:

тип ID[размер1][размер2]…[размерN] =

{ {список начальных значений},

{список начальных значений},

…

};

Списки начальных значений – атрибут необязательный.

Наиболее быстро изменяется последний индекс элементов массива, поскольку многомерные массивы в языке Си размещаются в памяти компьютера построчно друг за другом (см. следующую тему «Адресная функция»).

Рассмотрим особенности работы с многомерными массивами на конкретном примере двухмерного массива.

Например, пусть приведена следующая декларация двухмерного массива:

int m[3][4];

Идентификатор двухмерного массива – это указатель на массив указателей (переменная типа указатель на указатель: int **m;).

Поэтому двухмерный массив m[3][4]; компилятор рассматривает как массив трех указателей, каждый из которых указывает на начало массива со значениями размером по четыре элемента каждый. В ОП данный массив будет расположен следующим образом:

(А) (В)

Рис. 10.1. Схема размещения элементов массива m размером 3×4

Причем в данном случае указатель m[1] будет иметь адрес m[0]+4*sizeof(int), т.е. каждый первый элемент следующей строки располагается за последним элементом предыдущей строки.

Приведем пример программы конструирования массива массивов:

#include <stdio.h>

void main()

{

int x0[4] = { 1, 2, 3,4}; // Декларация и инициализация

int x1[4] = {11,12,13,14}; // одномерных массивов

int x2[4] = {21,22,23,24};

int *m[3] = {x0, x1, x2,}; // Создание массива указателей

int i,j;

for (i=0; i<3; i++) {

printf("\n Cтрока %d) ", i+1);

for (j=0; j<4; j++)

printf("%3d", m[ i ] [ j ]);

}

}

Результаты работы программы:

Cтрока 1) 1 2 3 4

Cтрока 2) 11 12 13 14

Cтрока 3) 21 22 23 24

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

#include <stdio.h>

void main()

{

int i, j;

int m[3][4] = { { 1, 2, 3, 4}, {11,12,13,14}, {21,22,23,24} };

for (i=0; i<3; i++) {

printf("\n %2d)", i+1);

for (j=0; j<4; j++)

printf(" %3d",m[ i ] [ j ]);

}

}

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

int m[3][4] = {1, 2, 3, 4, 11, 12, 13, 14, 21, 22, 23, 24};

Замена скобочного выражения m[3][4] на m[12] здесь не допускается, так как массив указателей не будет создан.

Таким образом, использование многомерных массивов в языке Си связано с расходами памяти на создание массивов указателей.

Очевидна и схема размещения такого массива в памяти – последовательное (друг за другом) размещение «строк» – одномерных массивов со значениями (векторная организация памяти).

Обращению к элементам массива при помощи операции индексации m[i][j] соответствует эквивалентное выражение, использующее адресную арифметику – *(*(m+i)+j).

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

Адресная функция

Векторная память поддерживается почти всеми языками высокого уровня и предназначена для хранения массивов различной размерности и различных размеров. Каждому массиву выделяется непрерывный участок памяти указанного размера. При этом элементы, например, двухмерного массива X размерностью n1´n2 размещаются в ОП в следующей последовательности:

Х(0,0), Х(0,1), Х(0,2),... Х(0, n2–1), ..., Х(1,0), Х(1,1), Х(1,2),... Х(1, n2–1), ..., Х(n1–1,0), Х(n1–1,1), Х(n1–1,2), ..., Х(n1–1, n2–1).

Адресация элементов массива определяется некоторой адресной функцией, связывающей адрес и индексы элемента.

Пример адресной функции для массива Х:

K(i, j) = n2*i + j;

где i = 0,1,2,... ,(n1–1); j = 0,1,2,... ,(n2–1); j – изменяется в первую очередь.

Адресная функция двухмерного массива A(n,m) будет выглядеть так:

N1 = K(i, j) = m*i + j,

i=0,1,..., n–1; j=0,1,... , m–1 .

Тогда справедливо следующее:

A(i, j) « B(K(i, j)) = B(N1),

B – одномерный массив с размером N1 = n*m.

Например, для двухмерного массива A(2,3) имеем:

Проведем расчеты:

i = 0, j = 0 N1 = 3*0+0 = 0 B(0)

i = 0, j = 1 N1 = 3*0+1 = 1 B(1)

i = 0, j = 2 N1 = 3*0+2 = 2 B(2)

i = 1, j = 0 N1 = 3*1+0 = 3 B(3)

i = 1, j = 1 N1 = 3*1+1 = 4 B(4)

i = 1, j = 2 N1 = 3*1+2 = 5 B(5)

Аналогично получаем адресную функцию для трехмерного массива Х(n1, n2, n3):

K(i, j, k) = n3*n2*i + n2*j + k ,

где i = 0,1,2,... ,(n1–1); j = 0,1,2,... ,(n2–1); ); k = 0,1,2,... ,(n3–1); значение k – изменяется в первую очередь.

Для размещения такого массива потребуется участок ОП размером (n1*n2*n3)*sizeof(type). Рассматривая такую область как одномерный массив Y(0,1,..., n1*n2*n3), можно установить соответствие между элементом трехмерного массива X и элементом одномерного массива Y:

X(i, j, k) « Y(K(i, j, k)) .

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