Fernando Aires Castello - 4 months ago 33

C Question

I have an 8x8 matrix, like this:

`char matrix[8][8];`

Also, I have an array of 64 elements, like this:

`char array[64];`

Then I have drawn the matrix as a table, and filled the cells with numbers, each number being incremented from left to right, top to bottom.

If I have, say, indexes 3 (column) and 4 (row) into the matrix, I know that it corresponds to the element at position 35 in the array, as it can be seen in the table that I've drawn. I believe there is some sort of formula to translate the 2 indexes of the matrix into a single index of the array, but I can't figure out what it is.

Any ideas?

Answer

The way most languages store multi-dimensional arrays is by doing a conversion like the following:

If `matrix`

has size, n by m [i.e. i goes from 0 to (n-1) and j from 0 to (m-1) ], then:

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

.

So its just like a number system of base 'n'. Note that the size of the last dimension doesn't matter.

For a conceptual understanding, think of a (3x5) matrix with 'i' as the row number, and 'j' as the column number. If you start numbering from `i,j = (0,0) --> 0`

. For *'row-major'* ordering (like this), the layout looks like:

```
|-------- 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
```

As you move along the row (i.e. increase the column number), you just start counting up, so the Array indices are `0,1,2...`

. When you get to the second row, you already have `5`

entries, so you start with indices `1*5 + 0,1,2...`

. On the third row, you have `2*5`

entries already, thus the indices are `2*5 + 0,1,2...`

.

For higher dimension, this idea generalizes, i.e. for a 3D `matrix`

L by N by M:

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

and so on.

For a really good explanation, see: http://www.cplusplus.com/doc/tutorial/arrays/; or for some more technical aspects: http://en.wikipedia.org/wiki/Row-major_order