Java Reference
In-Depth Information
1
6
3
4
5
10
1
2
2
7
7
6
8
9
3
8
Transposed Array
4
9
5
10
Original Array
Figure 12.14: An Example of Array Transposition
X[j],whereX is the starting address of A[i].
Let us look at the actual computations needed. Assume array A is declared
to be an n by m array (e.g., it is declared as T A[n][m],whereT is the type of
the array's elements). We now know that:
address
(
A
[
i
][
j
])
=
address
(
X
[
j
]) where
X
=
address
(
A
[
i
])
address
(
A
[
i
])
=
address
(
A
)
+
i
∗
size
(
T
)
∗
m
Now:
address
(
X
[
j
])
=
address
(
X
)
+
j
∗
size
(
T
)
Putting these together:
address
(
A
[
i
][
j
])
=
address
(
A
)
+
i
∗
size
(
T
)
∗
m
+
j
∗
size
(
T
)
=
address
(
A
)
+
(
i
∗
m
+
j
)
∗
size
(
T
)
Computation of the address of elements in a column-major array is a
bit more involved, but we can make a useful observation. First, recall that
transposing
an array involves interchanging its rows and columns. That is, the
first column of the array becomes the first row of the transposed array, the
second column becomes the second row and so on (see Figure 12.14).
Now observe that a column-major ordering of elements in an array cor-
responds to a row-major ordering in the transposition of that array. Allocate
an n-by-m array, A, in column-major order and consider any element A[i][j].
Now transpose A into AT,anm-by-n array, and allocate it in row-major order.
Element AT[j][i] will always be the same as A[i][j].
What this means is that we have a clever way of computing the address of
A[i][j] in a column-major array. We simply compute the address of AT[j][i],
