memory management of multi-dimensional array

Question

Could you please show me an example how to compute the location of an element in a multi-dimensional array.

It is illustrated in Robert Sebesta's book Concept of Programming Languages that location of an element is given by the formula

location(a[i,j]) = address_of(a[1,1]) + ((i - 1)*n + (j - 1))*element_size

where n is the number of elements per row and a[1,1] is the base address (1-based indexing).

I tried to find the location of [5,5] in a 7×7-matrix, assuming element_size=2. By calculating manually I got the value as 66. But while calculating by using the formula I got the value as 64:

location(a[5,5]) = 0 + ((4*7) + 4)*2 = 64

Is this correct or not? Could you tell me how the difference of two occurred.

Answer 1

To me it's always 64. The location of 5,5 is 0+(((5-1)*7)+(5-1))*2= ((4*7)+4)*2= 28*2+4*2= 56+8= 64.

When you manually trying to calculate did you by any chance calculated the end address of the element at location 5,5 while you expected it's starting address? It's a common mistake, I'm asking because you didn't post how you calculated it manually.

00 02 04 06 08 10 12
14 16 18 20 22 24 26
28 30 32 34 36 38 40
42 44 46 48 50 52 54
56 58 60 62 64 66 68
70 72 74 76 78 80 82
84 86 88 90 92 94 96

Answer 2

A multidimensional array behaves like paging of n elements. Say you have a set of two numbers a and b. You decide, that your pagesize should be 1. Then you find the first element on the first page and the second element on the second page.

This is equivalent to saying, you have an array of arrays; each subarray containing only one element. This could also be thought of as a one dimensional array.

To get the nth element on the mth page, you need to now:

1) Where to start counting

2) What the page size is

In order to get the first element (of the given set above ) on the second page, you have to know, where the first element lies. From there you have to step m times the pagesize(here =1) forward. Then you are on page m. Then take the first element. Done.

If you are dealing with adresses of elements or pointers to elements, you should take the size of these into account.

Answer 3

The formula assumes that the array indices are zero based (the first element is at position 0) and it is perfectly correct. I assume that you made the classical mistake we all did in the beginning by counting from point 1, as an older colleague pointed out to me the first time I did it...