如何将矩阵的索引映射到一维数组(C++)？

Question

我有一个8x8矩阵,像这样:

char matrix[8][8];

另外,我有一个包含64个元素的数组,如下所示:

char array[64];

然后我将矩阵绘制成一个表格,并用数字填充单元格,每个数字从左到右,从上到下递增.

如果我将索引3(列)和4(行)索引到矩阵中,我知道它对应于数组中位置35处的元素,因为它可以在我绘制的表格中看到.我相信有一些公式可以将矩阵的2个索引转换为数组的单个索引,但我无法弄清楚它是什么.

有任何想法吗？

Answer 1

大多数语言存储多维数组的方式是进行如下转换:

如果matrix有大小,n乘以m [即i从0变为(n-1),j从0变为(m-1)],则:

matrix[ i ][ j ] = array[ i*m + j ].

所以它就像一个基数'n'的数字系统.请注意,最后一个维度的大小无关紧要.

为了概念上的理解,可以考虑一个(3x5)矩阵,其中'i'作为行号,'j'作为列号.如果你开始编号i,j = (0,0) --> 0.对于'row-major'排序(如此),布局如下:

           |-------- 5 ---------|
  Row      ______________________   _ _
   0      |0    1    2    3    4 |   |
   1      |5    6    7    8    9 |   3
   2      |10   11   12   13   14|  _|_
          |______________________|
Column     0    1    2    3    4 

当你沿着行移动时(即增加列数),你只是开始计数,所以数组索引是0,1,2....当你到达第二行时,你已经有了5条目,所以你从索引开始1*5 + 0,1,2....在第三行,您已经有2*5条目,因此索引是2*5 + 0,1,2....

对于更高维度,这个想法概括,即对于3D matrixL乘以N乘以M:

matrix[ i ][ j ][ k ] = array[ i*(N*M) + j*M + k ]

等等.

有关一个非常好的解释,请参阅:http://www.cplusplus.com/doc/tutorial/arrays/ ; 或者更多技术方面:http://en.wikipedia.org/wiki/Row-major_order

Answer 2

对于行主要订购,我认为该陈述matrix[ i ][ j ] = array[ i*n + j ]是错误的.

偏移应该是offset = (row * NUMCOLS) + column.

你的陈述结果是row * NUMROWS + column,这是错误的.

您提供的链接给出了正确的解释.

Answer 3

像这样的东西？

//columns = amount of columns, x = column, y = row
var calculateIndex = function(columns, x, y){
    return y * columns + x;
};

下面的示例将索引转换回x和y坐标.

//i = index, x = amount of columns, y = amount of rows
var calculateCoordinates = function(index, columns, rows){
    //for each row
    for(var i=0; i<rows; i++){
        //check if the index parameter is in the row
        if(index < (columns * i) + columns && index >= columns * i){
            //return x, y
            return [index - columns * i, i];
        }
    }
    return null;
};