Comparing Recursion and Looping Top FootnotesMatrices Contents

Matrices

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

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 themselves53. 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.

Creating a matrix

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 rows54:

    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:

Let's rotate the image 90 degrees so that the rows of the matrix are oriented horizontally, the natural way of viewing the matrix:

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.

Retrieving and modifying values in a matrix

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]      ]

Working with matrices

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 matrix data from a file

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

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

The filtered-count pattern

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.

The extreme and extreme index patterns

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.

The search pattern

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.

Passing static arrays to functions

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;

Simulating 2D arrays with simple arrays

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]

Problems

lusth@cs.ua.edu


Comparing Recursion and Looping Top FootnotesMatrices Contents