ПРИМЕЧАНИЕ. Примеры, используемые в этом посте, предназначены только для объяснения понятий.Таким образом, примеры могут быть неполными, могут отсутствовать обработка ошибок и т. Д.
Когда дело доходит до использования многомерного массива в C, ниже приведены два возможных способа.
Уплощение массивов
В C массивы реализованы как непрерывный блок памяти.Эта информация может использоваться для манипулирования значениями, хранящимися в массиве, и обеспечивает быстрый доступ к определенному местоположению массива.
Например,
int arr[10][10];
int *ptr = (int *)arr ;
ptr[11] = 10;
// this is equivalent to arr[1][0] = 10; assign a 2D array
// and manipulate now as a single dimensional array.
Техника использования смежной природы массивовизвестен как flattening of arrays.
рваные массивы
Теперь рассмотрим следующий пример.
char **list;
list[0] = "United States of America";
list[1] = "India";
list[2] = "United Kingdom";
for(int i=0; i< 3 ;i++)
printf(" %d ",strlen(list[i]));
// prints 24 5 14
Этот тип реализации известен как рваный массив и полезен в местах, где используются строки переменного размера.Популярный метод - иметь dynamic-memory-allocation для каждого измерения.
ПРИМЕЧАНИЕ. Аргумент командной строки (char *argv[]) передается только как рваный массив.
Сравнение уплощенных и неровных массивов
Теперь давайте рассмотрим следующий фрагмент кода, который сравнивает массивы flattened и ragged.
/* Note: lacks error handling */
int flattened[30][20][10];
int ***ragged;
int i,j,numElements=0,numPointers=1;
ragged = (int ***) malloc(sizeof(int **) * 30);
numPointers += 30;
for( i=0; i<30; i++) {
ragged[i] = (int **)malloc(sizeof(int*) * 20);
numPointers += 20;
for(j=0; j<20; j++) {
ragged[i][j]=(int*)malloc(sizeof(int) * 10);
numElements += 10;
}
}
printf("Number of elements = %d",numElements);
printf("Number of pointers = %d",numPointers);
// it prints
// Number of elements = 6000
// Number of pointers = 631
Из приведенного выше примера для массивов ragged требуется 631-pointers, другими словами, 631 * sizeof(int *) дополнительные ячейки памяти для указания 6000 целых чисел.Принимая во внимание, что массиву flattened требуется только один базовый указатель: то есть имя массива, достаточное для указания на смежные 6000 области памяти.
Но OTOH, массивы ragged являются гибкими.В тех случаях, когда точное количество требуемых ячеек памяти неизвестно, вы не можете позволить себе роскошь выделить память для худшего возможного случая.Опять же, в некоторых случаях точное количество требуемой памяти известно только во время выполнения.В таких ситуациях ragged массивы становятся удобными.
Старший ряд и главный столбец массивов
C следует row-major упорядочение для многомерных массивов,Flattening массивов можно рассматривать как эффект из-за этого аспекта в C.Значение row-major порядка C в том, что он соответствует естественному способу, которым большая часть доступа осуществляется в программировании.Например, давайте рассмотрим пример обхода матрицы N * M 2D,
for(i=0; i<N; i++) {
for(j=0; j<M; j++)
printf(“%d ”, matrix[i][j]);
printf("\n");
}
Доступ к каждой строке в матрице один за другим путем быстрого изменения столбца.Массив C упорядочен в памяти таким естественным образом.Напротив, рассмотрим следующий пример:
for(i=0; i<M; i++) {
for(j=0; j<N; j++)
printf(“%d ”, matrix[j][i]);
printf("\n");
}
Это меняет индекс столбца чаще, чем индекс строки.И из-за этого существует большая разница в эффективности между этими двумя фрагментами кода.Да, первый более эффективен, чем второй!
Поскольку первый обращается к массиву в естественном порядке (порядок row-major) C, следовательно, он быстрее, тогда как второму требуется больше времени для прыжка.Разница в производительности будет увеличиваться по мере увеличения числа измерений и размера элемента.
Так что при работе с многомерными массивами в C хорошо рассмотреть приведенные выше детали!