В чем разница между массивами массивов и многомерными массивами?

Question

У меня была языковая беседа с кем-то в чате на C++ и he said, что массивы массивов и многомерные массивы - это две вещи.

Но из того, что я узнал, многомерный массив представляет собой не что иное, как массив других массивов, все из которых имеют одинаковый размер. В частности, он говорит

Ну, они вроде в C, где вы симулировать несколько измерений с вложенными массивами , но это только потому, что C фактически не поддерживает несколько массивов измерений

Может кто-то пожалуйста, объясните, каково определение канонической компьютерной науки «массивов с несколькими измерениями» и почему C (или абстрактное определение «массив массивов») не соответствует этому определению?

Answer 1

Примите .NET массивы, которые иллюстрируют это красиво:

С # имеет различие между jagged arrays которые определены во вложенном моды:

int[][] jagged = new int[3][]; 

Каждый вложенный массив может иметь различную длину:

jagged[0] = new int[3]; 
jagged[1] = new int[4]; 

(Обратите внимание, что один из вложенных массивов не инициализирован вообще, то есть null.)

В противоположность этому, multidimensional array определяется следующим образом:

int[,] multidim = new int[3, 4]; 

Здесь, не имеет смысла говорить о вложенных массивов, и в самом деле пытается получить доступ к multidim[0] будет ошибка времени компиляции - вы необходимо получить к нему доступ, обеспечивая все размеры, то есть multidim[0, 1].

Их типы тоже разные, как показывают вышеприведенные декларации.

Кроме того, их обработка совершенно иная. Например, вы можете перебрать над зубчатым массив с объектом типа int[]:

foreach (int[] x in jagged) … 

но итерация многомерного массива осуществляется с помощью элементов типа int:

foreach (int x in multidim) … 

Концептуально, массив с зазубринами представляет собой массив массивов массивов (... массивов массивов ... ad infinitum) из T, а многомерный массив - массив T с шаблоном доступа к набору (т. индекс является кортежем).

Answer 2

Я ожидал бы, что многомерные массивы будут предлагать такие операции, как «Дайте мне количество измерений» или «Дайте мне определенную колонку» или «Дайте мне определенный под-просмотр». C не предлагают эти операции.

Answer 3

Материал из Википедии:

Multi-dimensional arrays

Число индексов, необходимых для определения элемента, называется размерность, размерность или ранг типа массива. (Эта номенклатура противоречит понятию размерности в линейной алгебре, [5], где это число элементов. Таким образом, массив чисел с 5 строками и 4 столбцами, а значит, и 20 элементов, имеет размерность 2 в вычислительных контекстах , но представляет собой матрицу с размерностью 4 × 5 или 20 в математике. Кроме того, значение информатики «ранга» аналогично его значению в тензорной алгебре, но не к понятию линейной алгебры ранга матрицы.)

Многие языки поддерживают только одномерные массивы. В этих языках многомерный массив обычно представлен вектором Iliffe, одномерным массивом ссылок на массивы одного измерения меньше. Двумерный массив, в частности, будет реализован как вектор указателей на его строки. Таким образом, элемент в строке i и столбце j массива A будет доступен путем двойной индексации (A [i] [j] в типичной записи). Этот способ эмуляции многомерных массивов позволяет создавать рваные или зубчатые массивы, где каждая строка может иметь другой размер - или, в общем, где допустимый диапазон каждого индекса зависит от значений всех предыдущих индексов.

Это представление для многомерных массивов довольно распространено в программном обеспечении C и C++. Однако C и C++ будут использовать линейную формулу индексирования для многомерных массивов, которые объявлены как таковые, например. от Int А [10] [20] или Int A [M] [N], вместо традиционного Int ** А [6]:. с.81

В качестве примера языка, поддерживающего многомерных массивов , см. here.

Answer 4

C не имеет многомерных массивов, но C имеет массивы массивов.

В стандарте используется многомерный массив , но C многомерные массивы на самом деле являются массивами массивов. От Керниган & Ritchie:

«В C, двумерный массив действительно одномерный массив, каждый из элементов которого является массивом.»

Некоторые языки поддерживают многомерные массивы как типы первого класса. В книге «Expert C Programming» показан пример Ada, который поддерживает как массивы массивов, так и многомерные массивы.

Answer 5

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

«Массив массива» использует линейную индексацию, поскольку он фактически реализован как один размерный массив, несмотря на языковой уровень, на который он ссылается через несколько индексов.Ex, в C:

int a[5][5]; 

фактически имеют такую ​​же структуру, как:

int a[25]; 

Компилятор перевести доступ, такие как:

a[i][j] 

к:

a[i * jDimensionWidth + j] 

где jDimensionWidth = 5 в приведенном выше e Xample. И это даже можно получить к нему доступ, как:

int* b = (int*) a; 
printf("%d\n",b[12] == a[2][2]); // should output 1 

«многомерный массив» вид реализуется через Iliffe вектор, как он сказал, где индексация не может быть линеаризовано, так как адрес не является линейным, а так как вектор обычно реализуется как объект кучи. Этот вид многомерного массива не соответствует уравнению (для 2-мерного массива):

addr(a[i + 1]) = addr(a[i]) + (a[i].width * sizeof(a[i][j].datatype)) 

, который выполняется с помощью «массива из массива» вид.