Как 3D-массивы хранятся в C?
Я понимаю, что массивы в C размещаются в порядке следования строк. Поэтому для массива 2 x 3:
0 1
2 3
4 5
Хранится в памяти как
0 1 2 3 4 5
Однако, что если у меня есть массив 2 x 3 x 2:
0 1
2 3
4 5
а также
6 7
8 9
10 11
Как они хранятся в памяти? Это просто подряд, как:
0 1 2 3 4 5 6 7 8 9 10 11
Или это какой-то другой путь? Или это от чего-то зависит?
8 ответов
Все "измерения" хранятся последовательно в памяти.
Рассматривать
int arr[4][100][20];
Вы можете сказать, что arr[1] а также arr[2] (типа int[100][20]) являются смежными
или это arr[1][42] а также arr[1][43] (типа int[20]) являются смежными
или это arr[1][42][7] а также arr[1][42][8] (типа int) являются смежными
На низком уровне нет такого понятия, как многомерный массив. Это просто плоский блок памяти, достаточно большой, чтобы вместить определенное количество элементов. В C многомерный массив концептуально является массивом, элементы которого также являются массивами. Так что если вы делаете:
int array[2][3];
Концептуально вы получите:
array[0] => [0, 1, 2]
array[1] => [0, 1, 2]
Это приводит к тому, что элементы располагаются в памяти непрерывно, потому что array[0] а также array[1] на самом деле не содержат никаких данных, это просто ссылки на два внутренних массива. Обратите внимание, что это означает, что только [0, 1, 2] Записи на самом деле занимают место в памяти. Если вы расширите этот шаблон до следующего измерения, вы увидите, что:
int array[2][3][2];
... даст вам такую структуру, как:
array[0] => [0] => [0, 1]
[1] => [0, 1]
[2] => [0, 1]
array[1] => [0] => [0, 1]
[1] => [0, 1]
[2] => [0, 1]
Который продолжает упорядочивать элементы последовательно в памяти (как указано выше, только [0, 1] записи на самом деле занимают место в памяти, все остальное является лишь частью ссылки на одну из этих записей). Как видите, этот шаблон будет продолжаться независимо от того, сколько у вас измерений.
И просто для удовольствия
int array[2][3][2][5];
Дает тебе:
array[0] => [0] => [0] => [0, 1, 2, 3, 4]
[1] => [0, 1, 2, 3, 4]
[1] => [0] => [0, 1, 2, 3, 4]
[1] => [0, 1, 2, 3, 4]
[2] => [0] => [0, 1, 2, 3, 4]
[1] => [0, 1, 2, 3, 4]
array[1] => [0] => [0] => [0, 1, 2, 3, 4]
[1] => [0, 1, 2, 3, 4]
[1] => [0] => [0, 1, 2, 3, 4]
[1] => [0, 1, 2, 3, 4]
[2] => [0] => [0, 1, 2, 3, 4]
[1] => [0, 1, 2, 3, 4]
Да, вы правы - они хранятся последовательно. Рассмотрим этот пример:
#include <stdio.h>
int array3d[2][3][2] = {
{{0, 1}, {2, 3}, {3, 4}},
{{5, 6}, {7, 8}, {9, 10}}
};
int main()
{
int i;
for(i = 0; i < 12; i++) {
printf("%d ", *((int*)array3d + i));
}
printf("\n");
return 0;
}
Выход:
0 1 2 3 3 4 5 6 7 8 9 10
Да, они просто хранятся в последовательном порядке. Вы можете проверить это следующим образом:
#include <stdio.h>
int main (int argc, char const *argv[])
{
int numbers [2][3][4] = {{{1,2,3,4},{5,6,7,8},{9,10,11,12}}
,{{13,14,15,16},{17,18,19,20},{21,22,23,24}}};
int i,j,k;
printf("3D:\n");
for(i=0;i<2;++i)
for(j=0;j<3;++j)
for(k=0;k<4;++k)
printf("%i ", numbers[i][j][k]);
printf("\n\n1D:\n");
for(i=0;i<24;++i)
printf("%i ", *((int*)numbers+i));
printf("\n");
return 0;
}
Это означает, что доступ к мультииндексированному массиву с размерами (N,M,L) преобразуется в одномерный доступ, например так:
array[i][j][k] = array[M*L*i + L*j + k]
Я думаю, что вы ответили на свой вопрос. Многомерные массивы хранятся в главном порядке строк.
См. Раздел спецификации ANSI C 3.3.2.1 (есть также конкретный пример):
Последовательные операторы нижнего индекса обозначают член объекта многомерного массива. Если E - это n-мерный массив ( n =2) с размерами i x j "x ... x" k, то E (используемый как отличное от l-значение) преобразуется в указатель на ( n -1)-мерный массив с размерами j "x ... x" k . Если унарный оператор * применяется к этому указателю явно или неявно в результате подписки, результатом является массив с указателем (n -1), который сам преобразуется в указатель, если используется как значение, отличное от lvalue, Из этого следует, что массивы хранятся в основном порядке строк (последний индекс изменяется быстрее всего).
Для вашего примера вы можете просто попробовать и посмотреть - http://codepad.org/10ylsgPj
Допустим, у вас есть массив char arr[3][4][5], Это массив из 3 массивов из 4 массивов по 5 символов.
Для простоты, скажем, что значение в arr[x][y][z] является xyz И в arr[1][2][3] мы храним 123,
Итак, расположение в памяти:
| 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
--+--------------------------------------------------------------------------------
00| 000 001 002 003 004 010 011 012 013 014 020 021 022 023 024 030 031 032 033 034
20| 100 101 102 103 104 110 111 112 113 114 120 121 122 123 124 130 131 132 133 134
40| 200 201 202 203 204 210 211 212 213 214 220 221 222 223 224 230 231 232 233 234
arr[0], arr[1] а также arr[2] идут один за другим, но каждый элемент имеет тип char[4][5] (это три строки в таблице).
arr[x][0] - arr[x][3] также идут один за другим, и каждый элемент в них имеет тип char[5] (это четыре части каждой строки в таблице, 000 - 004 является одним элементом arr[0][0])
arr[x][y][0] - arr[x][y][4] 5 байтов, которые идут один за другим.
Чтобы ответить на комментарий ОП к основному вопросу (он будет несколько длинным, поэтому я решил пойти с ответом, а не с комментарием):
Должны ли массивы в C быть объявлены как
array[ny][nx]гдеnyа такжеnxколичество элементов в направлении у и х. Кроме того, означает ли это, что мой 3D-массив должен быть объявлен какarray[nz][ny][nx]?
В математике матрица MxN имеет M строк и N столбцов. Обычная запись для матричного элемента a(i,j), 1<=i<=M, 1<=j<=N, Итак, первая матрица в вашем вопросе - это матрица 3х2.
Действительно, оно отличается от обозначения, обычно используемого, например, для элементов GUI. Растровое изображение 800x600 имеет 800 пикселей по горизонтали (по оси X) и 600 пикселей по вертикали (вдоль оси Y). Если кто-то захочет описать его как матрицу, в математической записи это будет матрица 600x800 (600 строк, 800 столбцов).
Теперь многомерные массивы в C хранятся в памяти таким образом, что a[i][j+1] рядом с a[i][j] в то время как a[i+1][j] это N элементов. Обычно говорят, что "последний нижний индекс изменяется быстрее всего" или часто как "хранимый по строкам": строка (то есть элементы с одинаковым первым индексом) в двумерной матрице размещается в памяти непрерывно, а столбец (тот же второй индекс)) состоят из элементов, лежащих далеко друг от друга. Из соображений производительности важно знать: доступ к соседним элементам обычно намного быстрее (из-за кэшей HW и т. Д.), Поэтому, например, вложенные циклы должны быть организованы так, чтобы самый внутренний цикл проходил по последнему индексу.
Возвращаясь к вопросу: если ваша ментальная картина (абстракция) двумерного массива представляет собой решетку в картезианских координатах, то да, вы можете думать о ней как о array[NY][NX] в C. Однако если вам нужно описать реальные 2D или 3D данные в виде массива, выбор индексов, вероятно, зависит от других вещей: форматов данных, удобной записи, производительности и т. д. Например, если представление в памяти для растрового изображения является array[NX][NY] в формате, с которым вам нужно работать, вы объявите его таким образом, и, возможно, вам даже не нужно будет знать, что растровое изображение становится своего рода "транспонированным":)
3d массив - это расширенный 2d массив.
Например, у нас есть массив - int arr(3)(5)(6);
Это массив, который состоит из двух двумерных массивов, где массив будет иметь двумерный массив, имеющий 4 строки и 3 столбца.