将一个二维数组映射到一个一维数组上。

Question

我想用一个一维数组来表示一个二维数组。一个函数将传递两个指数（x，y）和要存储的值。这两个索引将表示一个一维数组的单个元素，并相应地设置它。我知道这个一维数组的大小需要为arrayWidth×arrayHeight，但我不知道如何设置每个元素。

例如，如何区分(2,4,3)和(4,2,3)？我尝试将数组设置为x*y，但是2*4和4*2会导致数组中同一个位置，而我希望它们不同。

- Blackbinary

Answer 1

你需要决定数组元素是按行顺序还是按列顺序存储，并保持一致。http://en.wikipedia.org/wiki/Row-major_order C语言使用行顺序来处理多维数组。

为了用单维数组模拟这种情况，你需要将行索引乘以宽度，再加上列索引。

 int array[width * height];

 int SetElement(int row, int col, int value)
 {
    array[width * row + col] = value;  
 }

- John Knoeller

---

我认为这个答案更清晰，特别是对于初学者来说，最好不要在一行内编写函数……！无论如何，这是不良的实践。 :) - Lipis

当你使用没有适当的多维数组支持的编译器（例如嵌入式系统）时，这个答案也很有用。 - Alex Marshall

令人惊讶的是，有多少人可以正确回答同一个问题，但只有其中一个人以易于理解的方式表达出来。这是最简单的答案之一。然而，约翰是唯一一个真正提供了一个好答案的人。其余的都是垃圾，只有那些已经知道答案的人才能轻松理解。感谢约翰，他实际上用英语而不是外星语言说话。这只是表明了有些人教学很差，而像约翰·克诺勒这样的好老师知道如何更有效地简化和沟通。 - user2948630

展示如何反转这个映射是很好的：如果1D数组的索引是alpha，2D数组在两个方向上的维数都是N，具有索引x, y，那么根据@JohnKnoeller，alpha=x+N*y。反转这个映射的方法是将x=alpha%N和y=(alpha-alpha%N)/N。 - Tim

Answer 2

将二维数组索引重新计算为一维数组索引的典型公式为：

index = indexX * arrayWidth + indexY;

或者你可以使用

index = indexY * arrayHeight + indexX;

（假设arrayWidth是沿X轴测量的，arrayHeight是沿Y轴测量的）

当然，可以提供许多不同的公式来提供替代唯一映射，但通常没有必要。

在C/C++语言中，内置的多维数组存储在内存中，最后一个索引变化最快，这意味着对于声明为的数组，例如：

int xy[10][10];

在内存中，元素xy[5][3]紧随其后的是xy[5][4]。您可能希望遵循该约定，根据您认为哪个索引（X或Y）是这两个中的“最后一个”，选择上述两个公式之一。

- AnT stands with Russia

Answer 3

示例：我们想要表示一个大小为SIZE_X和SIZE_Y的二维数组。这意味着我们将有MAXY个连续的行，每行的大小为MAXX。因此，set函数如下：

void set_array( int x, int y, int val ) { array[ x * SIZE_Y + y ] = val; }

获取的内容如下：

int get_array( int x, int y ) { return array[ x * SIZE_Y + y ]; }

- Kornel Kisielewicz

---

你的 MAXX 和 MAXY 值的命名有些混淆，因为 x 和 y 的最大值分别是 MAXX - 1 和 MAXY - 1。也许使用 SIZE_X 和 SIZE_Y 会更好？ - caf

[y * maxx + x] 是列序，而不是行序。这是Matlab的工作方式，但并不是C语言中数组通常的工作方式。 - John Knoeller

一个宏可能更合适，这样就不会在本应是低级数据访问的地方堆叠不必要的函数调用（特别是因为在伪二维数组中进行一维索引有时是一种优化技巧）。 - krs013

假设这段代码是类成员，那么它将被内联。否则，显式内联要比宏好得多。 - Kornel Kisielewicz

@KornelKisielewicz - 我知道这是一个老问题，但你的意思是： “MAXX大小的MAXY连续行？” - Rohan

Answer 4

就像其他人说的那样，C地图是按行顺序排列的。

   #include <stdio.h>

   int main(int argc, char **argv) {
   int i, j, k;
   int arr[5][3];
   int *arr2 = (int*)arr;

       for (k=0; k<15; k++) {
          arr2[k] = k;
          printf("arr[%d] = %2d\n", k, arr2[k]);
       }

       for (i=0; i<5; i++) {
         for (j=0; j< 3; j++) {
            printf("arr2[%d][%d] = %2d\n", i, j ,arr[i][j]);
         }
       } 
    } 

输出：

arr[0] =  0
arr[1] =  1
arr[2] =  2
arr[3] =  3
arr[4] =  4
arr[5] =  5
arr[6] =  6
arr[7] =  7
arr[8] =  8
arr[9] =  9
arr[10] = 10
arr[11] = 11
arr[12] = 12
arr[13] = 13
arr[14] = 14
arr2[0][0] =  0
arr2[0][1] =  1
arr2[0][2] =  2
arr2[1][0] =  3
arr2[1][1] =  4
arr2[1][2] =  5
arr2[2][0] =  6
arr2[2][1] =  7
arr2[2][2] =  8
arr2[3][0] =  9
arr2[3][1] = 10
arr2[3][2] = 11
arr2[4][0] = 12
arr2[4][1] = 13
arr2[4][2] = 14

- Sammy

Answer 5

使用行主序示例：

A(i,j) = a[i + j*ld]; // where ld is the leading dimension
                      // (commonly same as array dimension in i)

// matrix like notation using preprocessor hack, allows to hide indexing
#define A(i,j) A[(i) + (j)*ld]

double *A = ...;
size_t ld = ...;
A(i,j) = ...;
... = A(j,i);

- Anycorn

Answer 6

重要的是以一种可以检索所使用语言的方式存储数据。C语言按行主序存储（所有第一行先出现，然后是所有第二行，...），每个索引都从0到其维度-1运行。因此，数组x [2] [3]的顺序是x [0] [0]，x [0] [1]，x [0] [2]，x [1] [0]，x [1] [1]，x [1] [2]。因此，在C语言中，x [i] [j]与1维数组条目x1dim [i * 3 + j]存储在同一位置。如果以这种方式存储数据，则可以轻松地在C语言中检索。

Fortran和MATLAB是不同的。它们按列主序存储（所有第一列先存储，然后是所有第二行，...），每个索引从1到其维度。因此，索引顺序与C相反，并且所有索引都比C大1。如果您按照C语言的顺序存储数据，则FORTRAN可以使用X_FORTRAN(j+1, i+1)找到X_C_language[i][j]。例如，X_C_language[1][2]等于X_FORTRAN(3,2)。在1维数组中，该数据值位于X1dim_C_language[2*Cdim2 + 3]，这与X1dim_FORTRAN(2*Fdim1 + 3 + 1)的位置相同。请记住，Cdim2 = Fdim1，因为索引的顺序被颠倒了。

MATLAB与FORTRAN相同。Ada与C相同，只是索引通常从1开始。任何语言都会按照其中一个C或FORTRAN的顺序进行索引，并且索引将从0或1开始，并可以进行相应的调整以访问存储的数据。

如果这个解释令人困惑，我很抱歉，但我认为它对于程序员来说是准确而重要的知识。

- Mark

Answer 7

你应该能够使用简单的指针来访问2D数组。在指针中，array[x][y]将被排列为p[0x * width + 0y][0x * width + 1y]...[0x * width + n-1y][1x * width + 0y]等。

- Arthur Kalliokoski