Data Structures Using C: 2.1.3 Two-Dimensional Arrays

2.1.3 Two-Dimensional Arrays

Until now we have discussed one-dimensional arrays. High-level languages also provide arrays of more than one dimension. Thus the C declaration

int a[5][3];

defines a two-dimensional array of 5 ?/FONT> 3 or 15 entries, each of type integer. This array a can also be viewed as a collection of 5 one-dimensional arrays, each of length 3, or 3 one-dimensional arrays, each of length 5. Again, we can think of two variables i and j of the correct index type as pointing to an entry of the array. Thus a[i][j] refers to the entry of the ith row and jth column, or to the entry of a currently pointed to by i and j. We assume that the (i,j)th entry can be accessed in constant time, no matter what the value of i or j . That is, the (i,j)th entry may be selected. Traversal of two-dimensional arrays is also easy.

A two-dimensional array is symmetric if a[i][j] and a[j][i] contain the same value for all i and j between 0 and n - 1. Suppose a collection of n²numbers, representing the distances between n(?/FONT>50) cities, is stored in a two-dimensional array a. Thus a[i][j] contains the distance between city i and city j. For this example, which involves distances, the array must be symmetric. However, the array a shown in Figure 2.4 is not symmetric, because a[2][3] does not equal a[3][2]. The n entries a[0][0], a[1][1],..., a[n - 1][n - 1] are called its diagonal entries. In the city-distance array, the diagonal entries must, of course, be zero.

Figure 2.4 An Asymmetric Two-Dimensional Array

Suppose a programmer wished, perhaps as part of an input validation function for the data of an array, to check the array for symmetry. The programmer might choose to write a function check to return the value true if the array is symmetric and false otherwise. A simple traversal, as follows, will do the checking. n

typedef int collection[50][50];

check(a,n)

/* Returns true only if the first n

rows and columns of a represent

a symmetric array

*/

collection a;

int n;

int i,j,ck;

ck = TRUE;

for (i = 0; i<n; i++)

for (j = 0; j<n; j++)

if (a[i][j] != a[j][i])

ck = FALSE;

return(ck);

This program does a complete traversal of the appropriate n entries of the array a. However, it is inefficient as a solution for a number of reasons. First, it does not exit immediately from the loops, even though it may have just found that a was not symmetric. Second, it checks the diagonal elements, which will always satisfy a[i][j] = a[j][i]. Finally, it double-checks each off-diagonal entry. For instance, when i = 2 and j = 3, it checks a[2][3] against a[3][2], and when i = 3 and j = 2, it checks a[3][2] against a[2][3] again. A better version would be a modified traversal, such as

typedef int collection[50][50];

check(a,n)

/* Returns true only if the first n

rows and columns of a represent

a symmetric array

*/

collection a;

int n;

int i,j,ck;

ck = TRUE;

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

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

if(a[i][j]! = a [j][i])

ck = FALSE;

return(ck);

Be sure you understand why the modified lines of code eliminate the inefficiencies.