2.3.1 Rowwise and Columnwise Representation

Suppose a has r rows and c columns, with row index range 0 . . . (r - 1) and column index range 0 . . . (c - 1). A rowwise representation for a uses a data array of length r ?/FONT> c and stores the first row of a in the first c consecutive entries of data, the second row in the next c entries, and so on.

Rowwise representation in arrays is similar to the first method discussed for storing records. In fact, it is logically the same as viewing each row as a record of length c. Thus the offset of the entry in position (i,j) of a is i * c + j in data. This is because rows 0, 1, . . . , i - 1 precede the ith row in data, and take up i ?/FONT> c entries. The jth position of the ith row is offset an additional j entries.

For the array a shown in Figure 2.11, with c = 5, the offset of a[2][3]is 2 * 5 + 3, or 13, and the third row of a starts at data[10]. a[2][3] is represented by data[13]. In C the offset and index are the same, since index values start at zero.

With this representation, function check of Example 2.3 would be written as

#define TRUE 1

#define FALSE 0

check(data,n)

/* Returns true only if an nxn

two-dimensional array stored in

rowwise representation in array

data is symmetric

*/

>Comment

int data[];

int n;

{

>Comment

int i,j,ck;

ck = TRUE;

for(i=1; i<n && ck ; i++)

for(j=0; j<i && ck ; j++)

>Comment

if(data[(i*n+j)] != data[(j*n+i)])

ck =FALSE;

return(ck);

}

Figure 2.11 Representing a Two-Dimensional Array as a One-DimensionalArray

Obviously, this representation in data allows a to be traversed, as well as allowing its (i,j)th entry to be selected.

The columnwise representation of a two-dimensional array is similar, except that the columns rather than the rows of a are stored sequentially in data. The offset for the entry in position (i,j) with the columnwise representation is j*r + i.