Once upon a time, there was a language that didn’t have 2 dimensional arrays. This greatly upset the programmer. Fortunately, the programmer was swift in the art of arithmetic and overcame this obstacle easily.

Lets say for example, we only have access to a 1 dimensional array data structure and it has 50 elements in it.

1 |
int data[50]; |

Lets break this array up into 10 rows and 5 columns to make a grid. So how do we get access to a position say data[4][3]?

There are two things I’m going to teach you now:

1) Retrieve the column & row numbers from a linear index counter.

2) Retrieve the index from a row & column numbers.

Before I continue, i want you to notice that the row and column numbers are zero based. So they start at zero, not one.

Lets do #1 first:

1 2 3 4 5 6 |
unsigned int index = 6; unsigned int numRows = 10; unsigned int numCols = 5; int row = index / numRows; int col = index % numCols; |

Here, “col” and “row” will contain the column and row number for index #6 in the linear array.

Here, we are taking advantage of dividing up a long linear array up into sections (rows), hence the division operator. So we have 10 rows / sections. We get a particular one by using the formula index / numRows.

If we were to loop through the linear array (0-50), moding (%) each number with some maximum number (say 5), we would obtain a series of numbers that went like the following: 0,1,2,3,4,0,1,2,3,4,0,1,2,3,4… (index % numCols). Notice how it repeats between 0 & numCols – 1? Where numCols is 5 in this case. Where index goes through 0 – 50, our column repeats from 0 – 4. Nifty huh? This works because the mod operator returns the remainder of a division (4 % 2 = 0 because there is no remainder).

As a side note: col could also be written like such: col = index – numRows * row. See below for why.

Now lets do #2:

1 2 3 4 5 |
unsigned int row = 4; unsigned int col = 3; unsigned int numRows = 10; data[ numOfRows * row + col ]; |

This is a pretty simple idea. We basically took the formula from #1 above and rearranged it. (row = index/numRows). Here we are also using col as an offset into the row. So we just add it on.

If you take index = numOfRows * row + col, you can solve for col, since we already solved for row. Hence the formula in #1’s side note: col = index – numRows * row

Example program:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include "stdafx.h" #include <iostream> using namespace std; const int LENGTH = 9; int data[LENGTH] = {0}; int numOfRows = 3; int numOfCols = 3; int _tmain(int argc, _TCHAR* argv[]) { for( unsigned i = 0; i < LENGTH; ++i ) data[i] = i; for( unsigned row = 0; row < numOfRows; ++row ) for( unsigned col = 0; col < numOfCols; ++col ) cout << data[ numOfRows * row + col ] << endl; // Get the column or row from a linear index unsigned indexNum = 4; int row2 = indexNum/numOfRows; int col2 = indexNum%numOfCols; cout << "row: " << row2 << endl; cout << "col: " << col2 << endl; // Get the index from a column & row int row = 1; int col = 1; cout << data[ numOfRows * row + col ] << endl; return 0; } |

The output for this program is:

1 2 3 4 5 6 7 8 9 10 11 12 |
0 1 2 3 4 5 6 7 8 row: 1 col: 1 4 |