Многомерный массив в соответствии с синтаксисом языка - массив массивов, т.е. массив, элементами которого служат массивы. Определение многомерного массива в общем случае должно содержать сведение о типе, размерности и количествах элементов каждой размерности:
type имя_массива[K1][K2]… [KN];
type – допустимый тип (основной или производный); имя_массива – идентификатор; N – размерность массива, К – количество в массиве элементов размерности К -1 каждый. Например: long Array[4][3][6];
Трехмерный массив Array состоит из четырех элементов, каждый из которых – двухмерный массив с размерами 3х6. Язык Си++ гарантирует, что в памяти компьютера элементы массива будут размещаться последовательно друг за другом в порядке возрастания самого правого индекса, т. е. самый младший адрес имеет элемент Array[0][0][0], затем идёт Array[0][0][1], Array[0][0][2], …, Array[0][0][5] далее
Array[0][1][0], Array[0][1][1], …, Array[0][1][5], далее Array[0][2][0], …, Array[0][2][5] заканчивается первый и далее начинается второй элемент двухмерного массива с размерами 3х6 Array[1][0][0], Array[1][0][1] и т. д.
С учётом порядка расположения в памяти элементов многомерного массива нужно размещать начальные значения его элементов в списке инициализации.
Так long Array[4][3][6] = {0,1,2,3,4,5,6,7,8,9}; такая запись означает, что начальные значения получат первые десять элементов массива Array, т.е.
Array[0][0][0] = = 0, Array[0][0][1] = =1, Array[0][0][2]= = 2, Array[0][0][3] = =3, Array[0][0][4] = = 4, Array[0][0][5] = = 5, Array[0][1][0] = = 6, Array[0][1][1] = = 7, Array[0][1][2] = = 8, Array[0][1][3] = = 9. Остальные элементы массива Array остались не инициализированными.
Если необходимо инициализировать только часть элементов многомерного массива, но они размещены не в его начале или не подряд, то можно вводить дополнительные фигурные скобки, каждая пара которых выделяет последовательность значений, относящихся к одной размерности. (Нельзя использовать скобки без информации внутри них). Запятые между элементами обозначают переход к следующему элементу с увеличением младшего индекса, а запятые между скобками в зависимости от
long A[4][5][6] = { {{0}},
{ {100}, {110, 111} },
{ {200}, {210}, {220, 221, 222}} };
так задаётся только некоторое значения его элементов:
А[0][0][0] = = 0
А[1][0][0]== 100, А[1][1][0] == 110, А[1][1][1] == 111
А[2][0][0] = = 200, А[2][1][0] = = 210,
А[2][2][0]== 220, А[2][2][1] == 221, А[2][2][2] == 222
Остальные элементы массива явно не инициализируются.
Если многомерный массив при определении инициализируется, то его самая левая размерность может в скобках не указываться. Количество элементов компилятор определяет по числу членов в инициализирующем списке. Например, определение
float matrix [][5] = { {1}, (2}, {3} };
формирует массив matrix с размерами 3х5, но не определяет явно начальных значений всех его элементов. Оператор
cout «"\ n sizeof (matrix) = "«sizeof (matrix); /*выведет на экран: sizeof(matrix)=60*/
Начальные значения получают только
matrix[0][0] = 1
matrix[1][0] = 2
matrix[2][0] = 3
Как и в случае одномерных массивов, доступ к элементам многомерных массивов возможен с помощью индексированных переменных и с помощью указателей. Возможно объединение обоих способов в одном выражении. Чтобы не допускать ошибок при обращении к элементам многомерных массивов с помощью указателей, нужно помнить, что при добавлении целой величины к указателю его внутреннее значение изменяется на "длину" элемента соответствующего типа. Имя массива всегда константа-указатель. Для массива, определенного как type ar [N] [M] [L], ar - указатель, поставленный в соответствие элементам типа type [M] [L]. Добавление 1 к указателю ar приводит к изменению значения адреса на величину sizeof(type) * M * L.
Именно поэтому выражение * (ar + 1) есть адрес элемента ar[l], т.е. указатель на массив меньшей размерности, отстоящий от начала массива (&ar[0]), на размер одного элемента type[M] [L]. Сказанное иллюстрирует следующая программа:
//Программа 5.5
#include "stdafx.h"
#include <iostream>
void main(){
int b[3][2][4] = {0, 1, 2, 3,
10, 11, 12, 13,
100, 101, 102, 103,
110, 111, 112, 113,
200, 201, 202, 203,
210, 211, 212, 213,
};
// Адрес массива b[][][]
std::cout << "\nb = " << b;
// Адрес массива b[0][][]
std::cout << "\n*b = " << *b;
// Адрес массива b[0][0][]
std::cout << "\n**b = " << **b;
// Элемент b[0][0][0]
std::cout << "\n***b ="<< ***b;
// Адрес массива b[1][][]
std::cout << "\n*(b + 1) = " << *(b + 1);
// Адрес массива b[2][][]
std::cout << "\n*(b +2) = " << *(b + 2);
// Адрес массива b[0][1][]:
std::cout << "\n*(*b + 1) = " << *(*b + 1);
std::cout << "\n*(*(*(b + 1) + 1) + 1) = " <<*(*(*(b + 1) + 1) + 1);
std::cout << "\n*(b[l][l]+ 1) = " << *(b[1][1] + 1);
//Элемент b[2][0] [0];
std::cout<< "\n*(b[l] + 1)[1] = " << *(b[1] + 1)[1];
getchar();
}
Результаты выполнения программы:
b = 0x8d880fd0
*b = 0x8d880fd0
**b = 0x8d880fd0
***b = 0
*(b + 1) = 0x8d880fe0
*(b + 2) = 0x8d880ff0
*(*b + 1) = 0x8d880fd8
*(*(*(b + 1) + 1) + 1) = 111
*(b[1][1] + 1) = 111
*(b[1] + 1) [1] = 200
В программе доступ к элементам многомерного массива осуществляется с помощью операций с указателями. В общем случае для трехмерного массива индексированный элемент b[i] [j] [k] соответствует выражению *(*(* (b + i) + j) + k). В нашем примере:
*(*<*(b + 1) + 1) + 1) == b[1][1][1] ==111
Допустимо в одном выражении комбинировать обе формы доступа к элементам многомерного массива:
*(b[1][1] + 1) == 111
Как бы ни был указан путь доступа к элементу многомерного массива, внутренняя адресная арифметика, используемая компилятором, всегда предусматривает действия с конкретными числовыми значениями адресов. Компилятор всегда реализует доступ к элементам массива с помощью указателей и операции разыменования. Если в программе использована, например, такая индексированная переменная: ar[i][j][k], принадлежащая массиву type ar[N][M][L], где N, M, L - целые положительные константы, то последовательность действий компилятора такова:
· выбирается адрес начала массива, т.е. целочисленное значение указателя ar, равное (unsigned long)ar;
· добавляется смещение i * (М * L) * sizeof(type) для вычисления начального адреса i-го массива с размерами M на L, входящего в исходный трехмерный массив;
· добавляется смещение для вычисления начального адреса j-й строки (одномерный массив), включающей L элементов. Теперь смещение равно (i * (М * L) + j * L) * sizeof (type);
· добавляется смещение для получения адреса k-го элемента в строке, т.е. получается адрес (unsigned long) (i * (M * L) + j * L + k) * sizeof(type);
· применяется разыменование, т.е. обеспечивается доступ к содержимому элемента по его адресу: * ((unsigned long) (i * (м * l) + j * l + k)).
Массивы указателей. Синтаксис языка Си++ в отношении указателей непротиворечив, но весьма далек от ясности. Для понимания, что же определено с помощью набора звездочек, скобок и имен типов, приходится аккуратно применять синтаксические правила, учитывающие последовательность выполнения операций. Например, следующее определение
int *array[6];/*вводит массив указателей на объекты типа int. Имя массива array, он состоит из шести элементов, тип каждого int. Определение*/
int (*ptr)[6]; /*вводит указатель ptr на массив из шести элементов, каждый из которых имеет тип int. Таким образом, выражение (array + 1) соответствует перемещению в памяти на sizeof (int) байтов от начала массива (т.е. на длину указателя типа int). Если прибавить 1 к ptr, то адрес изменится на величину sizeof (int[6]), т.е. на 12 байт при двухбайтовом представлении данных типа int.*/
Эта возможность создавать массивы* указателей порождает интересные следствия, которые удобно рассмотреть в контексте многомерных массивов.
По определению массива, его элементы должны быть однотипными и одного "размера". Предположим, что мы хотим определить массив для представления списка фамилий (учеников класса, сотрудников фирмы и т.п.). Если определять его как двухмерный массив элементов типа char, то в определении для элементов массива необходимо задать предельные размеры каждого из двух индексов. Таким образом, "прямолинейное" определение массива для хранения списка фамилий может быть таким:
char spisok[25][20];
Для примера здесь предполагается, что количество фамилий в списке не более 25 и что длина каждой фамилии не превышает 19 символов (букв). После такого определения или с помощью инициализации в самом определении в элементы spisok[0], spisok[l],... можно занести конкретные фамилии, представленные в виде строк. Размеры так определенного массива всегда фиксированы.
При определении массива один из его предельных размеров (самого левого индекса) можно не указывать. В этом случае количество элементов массива определяется, например, инициализацией:
char spisok[][20] = { "Иванов", "Петров", "Сидоров" };
Теперь в массиве spisok только 3 элемента, каждый из них длиной 20 элементов типа char (рис. 5.2).
Рис. 5.2. Двухмерный массив char spisok[3][20] и одномерный массив указателей char *pointer[3], инициализированные одинаковыми строками
Нерациональное использование памяти и в этом случае налицо. Даже для коротких строк всегда выделяется одно и то же количество байтов, заранее указанное в качестве предельного значения второго индекса массива spisok.
В противоположность этому при определении и инициализации теми же символьными строками одномерного массива указателей типа char* память распределяется гораздо рациональнее:
char *pointer [] = {"Иванов", "Петров", "Сидоров"};
Для указателей массива pointer, в котором при таком определении 3 элемента и каждый является указателем-переменной типа char *, выделяется всего 3*sizeof (char *) байтов. Кроме того, компилятор размещает в памяти три строковые константы "Иванов" (7 байт), "Петров" (7 байт), "Сидоров" (8 байт), а их адреса становятся значениями элементов pointer[0], pointer[1], pointer[2]. Сказанное иллюстрирует рис. 5.2.
Применение указателей и их массивов позволяет весьма рационально решать задачи сортировки сложных объектов с неодинаковыми размерами. Например, для упорядочения (хотя бы по алфавиту) списка строк можно менять местами не сами строки, а переставлять значения элементов массива указателей на эти строки, что и продемонстрировано в приведённой ниже программе.
//Программа 5.6
#include "stdafx.h"
#include <iostream>
void main (){
char *pointer []={"Ivanov", "Petrov", "Cidorov", "Antonov"};
int i, j;
char* temp;
int iNumberOfElement = 4;
for(i = 0; i < iNumberOfElement; i++) std::cout<<"\n\n"<< pointer [i];/*Печать исходного массива*/
//Сортировка по алвавиту
for(i = 0; i < iNumberOfElement -1; i++)
for(j = iNumberOfElement-1; j>i;j--){
if(strcmp(pointer [j], pointer [j-1]) <0){
temp = pointer [j]; // Меняем местами указатели
pointer [j] = pointer [j-1];
pointer [j-1] = temp;
}
}
std::cout<<"\n\n\n";/*Печать отсортированного массива */
for(i = 0; i < iNumberOfElement; i++) std::cout<<"\n "<< pointer [i];
getchar();
}
Накладными расходами при этой "косвенной" сортировке списков объектов является требование к памяти, необходимой для массива указателей. Выигрыш - существенное ускорение сортировки.
void* malloc(unsigned int size);
void free(void* p)
new delete
Массивы динамической памяти. В соответствии с синтаксисом операция new при использовании с массивами имеет следующий формат:
new тип_массива
Такая операция позволяет выделить в динамической памяти участок для размещения массива соответствующего типа, но не позволяет его инициализировать. В результате выполнения операция new возвратит указатель, значением которого служит адрес первого элемента массива.
При выделении динамической памяти для массива его размеры должны быть полностью определены.
long (*1р)[2][4]; // Определили указатель
1р = new long[3][2][4]; // Выделили память для массива
В данном примере использован указатель на объекты в виде двухмерных массивов, каждый из которых имеет фиксированные размеры 2х4 и содержит элементы типа long. В определении указателя следует обратить внимание на круглые скобки, без которых обойтись нельзя. После выполнения приведенных операторов указатель 1р становится средством доступа к участку динамической памяти с размерами 3 ´ 2 ´ 4 ´ sizeof (long) байтов. В отличие от имени массива (имени у этого массива из примера нет) указатель 1р есть переменная, что позволяет изменять его значение и тем самым, например, перемещаться по элементам массива.
Изменять значение указателя на динамический массив нужно с осторожностью, чтобы не "забыть", где же находится начало массива, так как указатель, значение которого определяется при выделении памяти для динамического массива, используется затем для освобождения памяти с помощью операции delete. Например, оператор;
delete [] 1р;
освободит целиком всю память, выделенную для определенного выше трехмерного массива, если 1р адресует его начало. Следующая программа иллюстрирует сказанное:
Выделение и освобождение памяти для массива
//Программа 5.7
#include "stdafx.h"
#include <iostream>
void main(){
long (*lp) [2][4];
lp = new long [3][2][4];
std::cout<< "\n";
for (int i = 0; i < 3; i++) {
std::cout << "\n";
for (int j = 0; j < 2; j++)
for (int k = 0; k < 4; k++) {
lp[i][j][k] = i + j + k;
std::cout<<'\t'<< lp[i][j][k];
}
}
getchar();
delete [] lp;
}
Результаты выполнения программы:
01231234
12342345
23453456
В отличие от определения массивов, не относящихся к динамической памяти, инициализация динамических массивов не выполняется. Поэтому при выделении памяти для динамических массивов их размеры должны быть полностью определены явно. Только из типа_массива операция new получает информацию о его размерах:
new long[] // Ошибка, размер неизвестен
new long[][2][4] // Ошибка, размер неизвестен
new long[3][][4] // Ошибка, размер неизвестен
Существует еще одно ограничение на размерности динамических массивов. Только первый (самый левый) размер массива может быть задан с помощью переменной. Остальные размеры многомерного массива могут быть определены только с помощью констант. Это несколько затрудняет работу с многомерными динамическими массивами. Например, если пытаться создать матрицы в виде двухмерных массивов, то затруднения возникнут при попытке написать функцию, формирующую в динамической памяти транспонированную матрицу по исходной матрице с заранее не определенными размерами.
Обойти указанное ограничение многомерных динамических массивов позволяет применение массивов указателей. Однако при использовании массивов указателей для имитации многомерных динамических массивов усложняется не только их формирование, но и освобождение динамической памяти. В следующей программе формируется, заполняется данными, затем печатается и уничтожается массив, представляющий прямоугольную диагональную единичную матрицу, порядок которой (размеры массива) вводятся пользователем с клавиатуры:
Единичная диагональная матрица с изменяемым порядком
//Программа 5.8
#include "stdafx.h"
#include <iostream> // Для ввода-вывода
void main(){
int n; // Порядок матрицы
std::cout<< "\nInput order of matrix: ";
std::cin>> n; // Определяются размеры массива
float **matr; // Указатель для массива указателей
matr = new float *[n]; // Массив указателей float *
if (matr == NULL){
std::cout<< "He создан динамический массив!";
return; // Завершение программы
}
for (int i = 0; i < n; i++){
// Строка-массив значений типа float:
matr[i] = new float[n];
if (matr[i] == NULL){
std::cout<< "He создан динамический массив!";
return; // Завершение программы
}
for (int j = 0; j < n; j++) // Заполнение матрицы
// Формирование нулевых элементов
if (i!= j)
matr[i][j] = 0;
else // Формирование единичной диагонали:
matr[i][j] = 1;
}
for (int i = 0; i < n; i++){
std::cout<< "\n row" << (i + 1) << ":";// Цикл печати элементов строки:
for (int j = 0; j < n; j++)std::cout<< "\t" << matr[i][j];
}
for (int i = 0; i < n; i++)
delete matr[i];
delete[]matr;
getchar();
}
Результаты выполнения:
Введите размер матрицы: 5 <Enter>
Строка 1: 10000
Строка 2: 01000
Строка 3: 00100
Строка 4: 00010
Строка 5: 00001
На рис. 5.3 изображена схема взаимосвязи (n - 1) - одномерных массивов, из n элементов каждый. Эти (n - 1) массивов совместно имитируют квадратную матрицу с изменяемыми размерами, формируемую в программе.
Рис. 5.3. Схема имитации двухмерного динамического массива с помощью массива указателей и набора одномерных массивов
