Matrices
| Contents |

You can download the functions defined or used in this chapter with the following commands:

wget troll.cs.ua.edu/ACP-C/matrix.c wget troll.cs.ua.edu/ACP-C/matrix.h

These files will help you run the test code listed in this chapter.
You will also need to download the *scanner* module.

Matrices, commonly used in mathematics,
are easily represented by two-dimensional
arrays in C. A two-dimensional (2D) array is an array whose elements are arrays
themselves^{53}.
Matrices can be divided
into rows and columns. A matrix with *p* rows and *q* columns is said to
be an *p x q* matrix.
The same is true for 2D arrays,
so
we will use the term matrix and 2D array interchangeably.
We will also focus in matrices of integers in this chapter.
Matrices of other types would be processed similarly.

Matrices can be allocated statically or dynamically.
A static allocation representing
a 3x4 matrix *m* would be very similar to that of a simple array:

int m[3][4];

Note the extra pair of square brackets; the first set of brackets contains the number of rows while the second pair contains the number of columns. As with simple arrays, multi-dimensional arrays allocated this way are uninitialized and, therefore, filled with garbage. One can initialize multi-dimensional arrays when statically allocated; To initialize the matrix:

1 | 2 | 3 | 4 |

5 | 6 | 7 | 8 |

9 | 10 | 11 | 12 |

we would structure the initializers by row:

int m[3][4] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9,10,11,12 }, };

Passing static multi-dimensional arrays to functions is not straightforward (see the last section in the chapter on Arrays). Therefore, we will focus on multi-dimensional arrays that are allocated dynamically.

Matrices need to be
allocated in stages.
The first stage allocates the
the *backbone* of the matrix. The backbone consists of an array of
one-dimensional array pointers, with the number of slots in the
backbone equal to the number of rows^{54}:

int **m = allocate(sizeof(int *) * rows);

Recall that the *allocate* function is a wrapper for *malloc*.
Pictorially, *m* looks like this:

The next step is to assign each slot in the backbone to point to an array with the number of slots equal to the number of columns:

for (r = 0; r < rows; ++r) { m[r] = allocate(sizeof(int) * cols); }

Now *m* looks like this:

Putting it all together, we can define a constructor that creates a matrix:

int ** newMatrix(int rows,int cols) { int r; int **m = allocate(sizeof(int *) * rows); //allocate the backbone for (r = 0; r < rows; ++r) { m[r] = allocate(sizeof(int) * cols); //allocate a row } return m; }

One way to improve this function is to pass in an initializer for the slots of the constructed array. After the row is allocated, one would loop over the columns in the row, setting each element to the initializer.

Another interesting enhancement is to fill an array with random values:

int ** newRandomMatrix(int rows,int cols,int max) { int r,c; int **m = allocate(sizeof(int *) * rows); //allocate the backbone for (r = 0; r < rows; ++r) { m[r] = allocate(sizeof(int) * cols); //allocate a row for (c = 0; c < cols; ++c) //fill the row m[r][c] = random() % max; } return m; }

Note the addition of the inner loop which fills the newly allocated
row with random values. Those random values are limited in size
by *max*.

To retrieve a value at row *r* and column *c* from a matrix *m*,
one uses an expression similar to:

value = m[r][c];

One
can set the value of the element at row *r* and column *c*
with an expression similar to:

m[r][c] = value;

Because matrices are built from simple arrays, the first row has index 0
and the first column has index 0 as well. Thus the first value
in the
first row in matrix *m* can be found at:

m[0][0]

Where is the last element in the last row found in a matrix *m* with
*x* rows and *y* columns?
Highlight the following line to see the answers:

[ m[x-1][y-1] ]

Matrices are typically processed with with two nested *for* loops. The
outer loop runs over the rows, while the inner loop runs over the columns
of each row. Here is a generic function for working with a matrix:

void processMatrix(int **m,int rows,int cols) { int r,c; for (r = 0; r < rows; ++r) for (c = 0; c < cols; ++c) { //do something with m[r][c] ... } }

As with all functions that process arrays, we need to pass in the dimensions of the array.

One useful thing to do with a matrix is visualize it. In other words, we might
wish to print out its contents.
Using the general purpose template *processMatrix*
as a guide, we simply substitute a print statement for the processing
comment:

void displayMatrix(int *m,int rows,int cols) { int r,c; for (r = 0; r < rows; ++r) for (c = 0; c < cols; ++c) { printf("%d\n",m[r][c]); } }

If we were to print this matrix:

1 | 2 | 3 |

4 | 5 | 6 |

we would see this output:

1 2 3 4 5 6

The good news is we printed every element as desired. The bad news is our
output looks nothing like a matrix; every element is printed on a line
by itself. We can fix this problem by replacing the `\n`

in
*printf*'s guide string with a space:

printf("%d ",m[r][c]);

Our output becomes:

1 2 3 4 5 6

Better, but we need a newline after each row is printed. The easiest way to do this is to print the newline after the inner loop completes:

void displayMatrix(int **m,int rows,int cols) { int r,c; for (r = 0; r < rows; ++r) { for (c = 0; c < cols; ++c) { printf("%3d ",m[r][c]); //%3d to pad values with spaces } printf("\n"); } }

Note how we had to add braces to the outer loop since now that loop consists of two actions, the inner loop and the printing of the newline. Now our output becomes:

1 2 3 4 5 6

which is a reasonable approximation to the way a matrix is supposed to look. We can test both our constructor and display functions:

//test (compile with matrix.c) #include "matrix.h" int **m = newRandomMatrix(3,4,100); //100 is the limit on random values displayMatrix(m,3,4);

This code yields:

83 86 77 15 93 35 86 92 49 21 62 27

Note that no value reaches the limit (the limit is exclusive).

Reading a 2-dimensional array from a file is similar to reading a simple array. As a reminder, here is a function for doing just that:

void readMatrix(char *fileName,int **m,int rows,int cols) { int r,c; FILE *fp = fopen(fileName,"r"); //fopen failure check omitted for (r = 0; r < rows; ++r) for (c = 0; c < cols; ++c) m[r][c] = readInt(fp); fclose(fp); }

This function assumes the file being read has enough values in it to fill the matrix.

As a final note, use of the scanner means that the data in the input file does not need to be organized in matrix form; all the matrix elements could be on a single line, for example.

Matrix patterns are very similar to patterns that loop over simple arrays.

For our first example of a matrix pattern consider a filtered-count implementation for a simple array:

int countArrayEvens(int *items,int size) { int i; int count = 0; for (i = 0; i < size; ++i) { if (isEven(items[i])) ++count; } return count; }

The analogous function for matrices is similar:

int countMatrixEvens(int **items,int rows,int cols) { int r,c; int count = 0; for (r = 0; r < rows; ++r) for (c = 0; c < cols; ++c) { if (isEven(items[r][c])) ++count; } return count; }

Indeed, most of the patterns for matrices follow directly from the simple array versions. The only change is having two formal parameters specifying the size and two loops for walking the matrix.

Here is an instance of the *extreme* pattern:

int matrixMin(int **m,int rows,int cols) { int r,c,min; min = m[0][0]; //assume first value is the minimum for (r = 0; r < rows; ++r) for (c = 0; c < cols; ++c) { if (m[r][c] < min) min = m[r][c]; } return min; }

Like the implementation for simple arrays, we start out by assuming the "first" value is the minimum. In the case of a matrix, the first value is at row 0, column 0.

Finding the extreme index is a bit trickier since one needs to save
two indices, the row *and* the column of the extreme value.
We also need to return two values, so we choose to return
nothing. Instead, we update the addresses of the variables
that are to hold the row and column of the minimum value:

void matrixMinIndex(int **m,int rows,int cols,int *minr,int *minc) { int r,c; *minr = 0; *minc = 0; for (r = 0; r < rows; ++r) for (c = 0; c < cols; ++c) { if (m[r][c] < m[*minr][*minc]) { *minr = r; *minc = c; } } }

To call this function, one needs to remember to send addresses for the last two arguments:

//test (compile with matrix.c) #include "matrix.h" int minRow,minCol; int **m = newRandomMatrix(3,4,100); //3 rows,4 columns,values limited by 100 matrixMinIndex(m,3,4,&minRow,&minCol); displayMatrix(m,3,4); printf("the minimum values is at m[%d][%d]\n",minRow,minCol);

The output of this code is:

83 86 77 15 93 35 86 92 49 21 62 27 the minimum values is at m[0][3]

By inspection, we see that the smallest value is 15 and it is located in the first row, row zero, and the last column, column three.

Things can get even more complicated with matrices. Suppose you wished to find the index of the row with the largest sum. We can simplify the complexity of this task by taking advantage of the fact that a row in a matrix is a simple array and by using a helper function:

int largestRow(int **m,int rows,int cols) { int r,index,largestSum; index = 0; largestSum = sum(m[0],cols); //sum the 1st row with a helper for (r = 1; r < rows; ++r) //skip first row { int s = sum(m[r],cols); //sum this row and see if larger if (s > largestSum) { index = r; largestSum = s; } } return index; } int sum(int *items,int size) { int i,total; total = 0; for (i = 0; i < size; ++i) { total += items[i]; } return total; }

Curiously,
the *largestRow* function does not appear to follow the pattern of other
matrix functions;
it only has one loop over the rows. However, it calls a helper function from
within its loop and that helper function loops over the columns, so we still have our
nested loops.

The helper function implements, of course, an accumulation.

One can return from the innermost loop, if one knows what one is doing. This makes implementing a search rather easy:

int findMatrix(int target,int **m,int rows,int cols) { int r,c; for (r = 0; r < rows; ++r) { for (c = 0; c < cols; ++c) { if (m[r][c] == target) return 1; //true } } return 0; //false }

Be careful where you place the `return 0`

, though.
It has to be outside the outer loop.

When you pass a static array to a function, the compiler converts the
array name to a pointer. Therefore, the formal parameter that
receives the array must be a pointer type. For example,
given this call to *f*:

int a[10]; int x = f(a);

The definition of function *f* might start out something like:

int f(int *z) { ...

When we have a two-dimensional static array, things get more complicated. You might expect that a pointer to such an array would be defined with two asterisks, since one interpretation of:

int **p;

is that *p* can point to a two-dimensional array of integers.
This is true *if* the array was dynamically allocated. What
happens if we set this pointer to a static array?

int w[10][12]; int **p = w;

Compiling this fragment yields the following warning:

int **p = w; ^ initialization from incompatible pointer type

Upon the assignment, the compiler converts *w* into a pointer and
then assigns that address to pointer *p*. What is wrong? The variable
*p* holds the address of a pointer to an integer while the pointer generated
from *w* holds the address of an array of 12 integers.
These are not the same types, hence the warning.

Here is how one specifies a pointer to an array (of 12 integers) in C:

int w[10][12]; int (*q)[12] = w;

Now *w* and *q* can be used interchangeably, at least with respect to
setting and getting values of the slots. The parentheses in the definition
of q are necessary since square brackets have a higher precedence than
asterisk. The definition:

int *q[12];

means *q* is an array of twelve integer pointers, while

int (*q)[12];

means *q* is a pointer to an array of twelve integers.

To pass a two-dimensional array, the receiving formal parameter must have
a type similar to *q* above. Given this call to *g*:

double z[3][8]; double y = g(z);

the definition of function *g* would start out something like:

double g(double (*m)[8]) { ...

For pointers to multi-dimensional static arrays, one elides the first set of brackets, replacing them with the asterisk, using parentheses to override the precedence of the remaining brackets. Here is an example using a four-dimensional array:

char alpha[3][7][5][8]; char (*beta)[7][5][8] = alpha;

Although C and most other programming languages allow for two-dimensional arrays, some restricted languages do not. If you are programming in such a language and need a two-dimensional array, not to worry; two-dimensional arrays can be faked with simple arrays. The trick is to convert a two-dimensional address (row index and column index) into a one dimensional address (simple index).

Consider this matrix:

0 | 1 | 2 | 3 |

4 | 5 | 6 | 7 |

8 | 9 | 10 | 11 |

Using our second attempt at displaying this matrix, we would have obtained the following output:

0 1 2 3 4 5 6 7 8 9 10 11

which looks remarkably like a simple, one-dimensional array! In fact, we can think of this output representing a simple array in which the rows of our two-dimensional array have been stored sequentially.

Now consider extracting the 6 from the 2D version. If our matrix
was bound to the variable *m*, the location of the 6 would be:

m[1][2]

If our simple array version were bound to the variable *n*, then
the 6 can be found at:

n[6]

since the numbers in the array reflect the indices of the array. It turns out that there is a very simple relationship between the 2D address and the 1D address. Since the rows are laid out sequentially in the 1D case and since the row index in the 2D case is 1, that means there is an entire row preceding the row of interest in the 1D case. Since the rows are 4 columns long, then four elements precede the row of interest. The column of interest has two columns preceding it, so summing the preceding row elements and the preceding column elements yields 6, exactly the address in the the simple array!

In general, the index of a 2D location in a 1D array can be computed by the following function:

int simple2DIndex(int r,int c,int cols) { return r * cols + c; }

Note that this function must know the number of columns in the matrix in order to make its computation. If we wished to display a 1D simulation of a 2D array, our display function might look like this:

void display1DMatrix(int *n,int size,int cols) { int r,c,rows; rows = size / cols; for (r = 0; r < rows; ++r) { for (c = 0; c < cols; ++c) printf("%3d ",n[simple2DIndex(r,c)]); printf("\n"); } }

Testing our simulation:

//test (compile with matrix.c) #include "matrix.h" int n[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }; display1DMatrix(n,sizeof(n)/sizeof(int),3); //three column format

yields:

1 2 3 4 5 6 7 8 9 10 11 12

In general, when simulating a 2D array, one replaces all indexing of the form:

m[j][k]

with

m[j * cols + k]

- Modify the
*displayMatrix*function to print out the vertical bars that delineate a matrix. That is to say, the display function should output something like:| 1 2 3 | | 4 5 6 |

- Modify the
*displayMatrix*function to make the displayed matrix even fancier:+ + | 1 2 3 | | 4 5 6 | + +

- It is relatively easy to transpose a square matrix (a
square matrix has the number of rows and the number of
columns equal). Here is a such a routine:
void transposeSquare(int **m,int size) { int r,c; for (r = ???; r < ???; r += ???) for (c = ???; c < ???; c += ???) { int old = m[r][c]; m[r][c] = ???; m[c][r] = ???; } }

Complete and test this procedure.

Matrices
| Contents |