Concepts of Programming Languages

of an element is the base address of the structure plus the element size times

the number of elements that precede it in the structure. For a matrix in row

major order, the number of elements that precedes an element is the number

of rows above the element times the size of a row, plus the number of elements

to the left of the element. This is illustrated in Figure 6.5, in which we assume

that subscript lower bounds are all zero.

To get an actual address value, the number of elements that precede the

desired element must be multiplied by the element size. Now, the access func-

tion can be written as

location(a[i,j]) = address of a[0, 0]

+ ((((number of rows above the ith row) * (size of a row))

+ (number of elements left of the jth column)) *

element size)

Because the number of rows above the ith row is i and the number of elements

to the left of the jth column is j, we have

location(a[i, j]) = address of a[0, 0] + (((i * n) + j) *

element_size)

where n is the number of elements per row. The first term is the constant part

and the last is the variable part.

The generalization to arbitrary lower bounds results in the following access

function:

location(a[i, j]) = address of a[row_lb, col_lb]

+ (((i - row_lb) * n) + (j - col_lb)) * element_size

where row_lb is the lower bound of the rows and col_lb is the lower bound of

the columns. This can be rearranged to the form

Figure 6.5

The location of the
[i,j] element in a
matrix

6.5 Array Types 271