Многомерные массивы, массивы указателей, динамические массивы

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

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. Схема имитации двухмерного динамического массива с помощью массива указателей и набора одномерных массивов