将2D阵列映射到1D阵列上

Question

我想用一维数组表示一个二维数组.函数将传递两个指标(x,y)和要存储的值.这两个标记代表一维阵列的单个元素,并相应地设置它.我知道1D数组需要有arrayWidth×arrayHeight的大小,但我不知道如何设置每个元素.

例如,我如何区分(2,4,3)和(4,2,3)？我尝试将数组设置为x*y,但是2*4和4*2将导致数组中的相同位置,我需要它们不同.

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;  
 }

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)是两者中的"最后",选择上述两个公式之一.

Answer 3

示例:我们想要表示SIZE_X和SIZE_Y大小的2D数组.这意味着我们将拥有MAXY连续的MAXX大小行.因此设定功能是

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 ]; }

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