Lab #7: Multidimensional arrays¶
This lab is ungraded
This lab is about multidimensional arrays in C. Multidimensional arrays are very common data structures that you will certainly see again if you continue taking CS courses and could make an appearance on our final exam. This is a tutorial-style lab in which you will learn about:
Creating stack-allocated 2D arrays
Creating and freeing heap-allocated 2D arrays
Working with 2D arrays
Using 2D arrays as function parameters
2D arrays as function return values
At the end, there are some exercises for you to complete to gain practice working with 2D arrays.
Getting Started¶
To pick up the files for this lab, navigate to your cmsc15200/labs-GITHUB_USERID directory
(where GITHUB_USERID is replaced with your GitHub account name)
and then run:
$ git pull upstream main
Remember, we use $ to indicate the Linux command-line prompt. It is
not part of the command that you will run.
If this command was successful, you will have a subdirectory named
lab7. As in earlier labs, we have provided a Makefile that has targets
for compiling your code with tests that you write and for cleaning up generated files.
See the file README.md for a description of all the files
in the distribution.
Stack-allocated 2D arrays¶
Creating stack-allocated 2D arrays¶
You are familiar with 1D arrays of different types, such as arrays of integers and character arrays (strings). Multidimensional arrays are allocated on the stack using the bracket notation. For example, here is code that creates a 2D array of integers with 4 elements in one direction and 5 elements in another:
int matrix[4][5];
C allows for the creation of arrays of any dimension. For example, here is code to stack-allocate an array with 3 elements in one dimension, 2 in a second, and 4 elements in a third dimension:
int matrix[3][2][4];
In this lab, we will focus on 2D arrays of integers, but the ideas within can easily be extended to arrays of higher dimensions or of other types.
You’ve seen how to initialize the values in a 1D array upon creation using the curly brace notation:
int array[3] = {7, 8, 9};
We can initialize the values of a 2D array when it’s created using nested curly braces:
int matrix[2][3] = {{0, 1, 2},
{3, 4, 5}};
So, matrix is the array:
0 1 2
3 4 5
We usually think of the first dimension as
the number of rows in the array and the second as the number of columns. So
matrix is a 2D array with two rows and three columns.
Once an array has been created, you can use the bracket notation to access and modify its elements:
int val = matrix[1][0]; // get the value from the second row, first column
matrix[1][0] = 7; // modify some elements
matrix[0][1] = 8;
val has the value 3 and now matrix is the array:
0 8 2
7 4 5
val is 3 because it was initialized before
that element of the array was modified.
The first index in the square brackets is the row index and the second is the
column index. That is, matrix[i][j] is the element in the i th
row and j th column of matrix. The row indices of the array range
from 0 to 1 (because there are
two rows) and the column indices range from 0 to 2 (because there are three
columns).
Working with 2D arrays is similar to working with 1D arrays, but you’ll
usually use nested loops to iterate through the elements. Here is some code
that subtracts a value from every element in matrix:
int val = 2;
int rows = 2;
int cols = 3;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
matrix[i][j] -= val;
}
}
Now matrix is the array:
-2 6 0
5 2 3
Stack-allocated 2D arrays as function parameters¶
Just like 1D arrays, 2D arrays can be passed to functions and parameters. Here is a function version of the code that subtracts a value from every element of a 2D array:
void subtract_val_from_array(int rows, int cols, int matrix[rows][cols], int val) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
matrix[i][j] -= val;
}
}
}
The first two arguments to subtract_val_from_array are the number of rows
and columns of the 2D array parameter. The third argument is the 2D array,
indicated by the square bracket notation. We are required to specify the size of its
second dimension for the compiler, but we’ll go ahead and specify the sizes
of both dimensions here. The last parameter is the value we want to subtract
from each element.
Here is some code that calls this function:
int my_matrix[2][3] = {{0, 1, 2},
{3, 4, 5}};
subtract_val_from_array(2, 3, my_matrix, 4);
printf("my_matrix[0][0]: %d\n", my_matrix[0][0]); // prints: -4
Heap-allocated 2D arrays¶
Creating heap-allocated 2D arrays¶
Here is code to allocate a 2D array on the heap with 3 rows and 4 columns in each row:
int rows = 3;
int cols = 4;
int **matrix = (int**)malloc(sizeof(int*) * rows);
for (int i = 0; i < rows; r++) {
matrix[i] = (int*)malloc(sizeof(int) * cols);
}
We have omitted the code that checks the output of malloc for NULL
in the interest of brevity, but we would of course include this in an actual implementation.
Line-by-line, this code:
Defines a number of rows,
Defines a number of columns,
Defines an int pointer pointer, and creates an array of int pointers (one for each row),
Iterates through each int pointer, and
Creates an array of ints (these are the rows).
Notice how you can access each row with the bracket notation matrix[i].
At this point, the integers in the array are uninitialized. You can use a nested loop to initialize the elements of a 2D array to, say, the number 2:
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
matrix[i][j] = 2;
}
}
Now matrix is the array:
2 2 2 2
2 2 2 2
2 2 2 2
Individual array elements can be accessed and modified in the same way as stack-allocated arrays:
int val = matrix[0][1]; // get the value from the first row, second column
matrix[0][0] = 0; // modify some elements
matrix[1][2] = 7;
matrix[2][3] = 8;
val has the value 2 and now matrix is the array:
0 2 2 2
2 2 7 2
2 2 2 8
The row indices of the array range from 0 to 2 and the column indices range from 0 to 3.
Since the rows of a heap-allocated 2D array are allocated individually, they do not need to be the same length (that is, the array does not need to be rectangular). Here is some code that creates a 2D array with two rows. The first row has 3 columns and the second row has 4 columns:
int **uneven = (int**)malloc(sizeof(int*) * 2);
uneven[0] = (int*)malloc(sizeof(int) * 3);
uneven[1] = (int*)malloc(sizeof(int) * 4);
Freeing heap-allocated 2D arrays¶
At this point, you know that it’s important to deallocate memory that you
have allocated with malloc. A good rule of thumb is to call free once
for every call to malloc. How many times was malloc called to create
matrix in the code above? Each row was allocated separately, which means
that we need to free each row separately, too. Here is code to free
the 2D array:
for (int i = 0; i < rows; i++) {
free(matrix[i]);
}
free(matrix);
Heap-allocated 2D arrays as function parameters¶
Here is a function that takes a heap-allocated 2D array as input and frees the space associated with the array:
void free_2D_array(int **matrix, int rows) {
for (int i = 0; i < rows; i++) {
free(matrix[i]);
}
free(matrix);
}
The first argument to free_2D_array is an int**, an array of pointers,
where each pointer points to an array of integers (the rows of
the 2D array). This is how we created a heap-allocated 2D array above.
Often, you’ll need to include another parameter for the number of columns in the 2D array (remember, there is no great way to ask C how many elements there are in an array).
Arrays as function return values¶
Just like 1D arrays, 2D arrays can be returned from functions.
As always, you should not return a stack-allocated array from a function,
as the memory for that array will be deallocated when the function returns.
So, the return type of a function that returns a 2D array of integers is
int** (the type of a heap-allocated 2D array of ints).
Here is a function that creates a 2D array with a specified number of rows and columns and initializes the elements of the array to the values 0, 1, 2, and so on:
int **make_2D_array(int rows, int cols) {
int **new_matrix = (int**)malloc(sizeof(int*) * rows);
int val = 0;
for (int i = 0; i < rows; i++) {
new_matrix[i] = (int*)malloc(sizeof(int) * cols);
for (int j = 0; j < cols; j++) {
new_matrix[i][j] = val++;
}
}
return new_matrix;
}
Again, we have omitted the code that checks the output of malloc for NULL
for brevity.
Here is a sample call to this function, taking care to free the array after we are finished using it:
int **my_matrix = make_2D_array_vals(5, 5);
printf("my_matrix[1][1]: %d\n", my_matrix[1][1]); // prints: 6
free_2D_array(my_matrix, 5);
Exercises¶
In the exercises below, we will use the int** type for 2D arrays. So, you should
call your functions with heap-allocated arrays in student_test_lab7.c when
you test your code by hand.
There is no test_lab7.c file for this lab, but
we have provided some testing infrustructure in student_test_lab7.c.
In addition to running the tests provided in the file, we recommend that you create
a few more small 2D integer
arrays to help you test your functions. Make sure you create both square and
rectangular arrays, as it’s easy to get the rows and columns mixed up. We have provided
the function make_2D_array shown above that creates a heap-allocated 2D array
given a number of rows and columns. We have also provided the corresponding
free_2D_array.
It is very difficult to tell whether functions that operate on arrays are
correct without visually inspecting the elements. To aid in testing, we have
provided a print_2D_array function, which prints the elements of a 2D
array, and print_1D_array function, which prints the elements of a 1D
array. You cand find the implementation of these functions in lab7.c.
Task 1
Complete the function:
bool search(int **matrix, int rows, int cols,
int val, int *found_row, int *found_col)
which takes a 2D array, its number of rows and columns, an integer to search
for, and two out parameters, and attempts to locate val in the 2D array
matrix. If val is found, its location should be returned in the
out parameters. if val is not found, you can set the out parameters
to -1. Furthermore, this function should return true if val was
found, and false otherwise. You can assume that the values in the array
are unique (that is, val will appear at most once in the array).
Task 2
Complete the function:
int *sum_rows(int **matrix, int rows, int cols, int *out_len)
which takes a 2D array, its number of rows and columns, and an out parameter, and returns a 1D array where each element of the output array is the sum of a row of the input array.
For example, say matrix has the values:
2 5 3
1 0 8
then a call to sum_rows should return the 1D array {10, 9}.
The elements in the first row of matrix sum to 10 and the elements in the
second row sum to 9. Furthermore, after this call the out parameter should point to 2.
Task 3
Complete the function:
int *flatten_array(int **matrix, int rows, int cols, int *out_len)
which takes a 2D array, its number of rows and columns, and an out parameter, and returns a 1D array where the rows of the 2D array have been concatendated (thereby creating a “flat” version of the 2D array).
For example, say matrix has the values:
2 5 3
1 0 8
then a call to flatten_array should return the 1D array {2, 5, 3, 1, 0, 8}.
This is also known as row-major order.
In row-major order, all of the elements of the first row come before any of the
elements in the second row.
Furthermore, after this call the out parameter should point to 6.
Task 4
Complete the function:
bool rows_and_columns_contain(int **matrix, int rows, int cols, int val)
which takes a 2D array, its number of rows and columns, and a value,
and returns true if every row and every column in matrix contains val,
and false otherwise.
For example, say matrix has the values:
2 1 3
1 2 8
2 7 1
then a call to rows_and_columns_contain with the value 1 should return
true. Every row and column contain the value 1.
A call to rows_and_columns_contain with the value 2 should return false.
The third column does not contain the value 2.
Task 5
Complete the function:
void flip(int **matrix, int rows)
which takes a square 2D array, its number of rows, and “flips” the values
of the array so that element (i, j) becomes element (j, i) for all i
and j. Note that the number of columns is not a parameter to this function
since matrix is square.
For example, say matrix has the values:
2 1 3
5 2 8
2 7 1
then after call to flip, matrix will have the values:
2 5 2
1 2 7
3 8 1
Task 6
Complete the function:
int **make_triangle(int rows)
that takes a number of rows and returns a triangular 2D array with the specified number of rows, each with an increasing number of columns, like this:
The first row should have one column with the value 1
The second rows should have two columns with the values 1 and 2
And so on
For example, create_triangle(3) should return the array:
1
1 2
1 2 3
The call create_triangle(5) should return the array:
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
Grading and submission¶
There is nothing to turn in for this lab, but we strongly encourage you to work through the exercises. Multidimensional arrays are very common data structures that you will certainly see again.
We also strongly encourage you to leave your directory into a clean state.
Run make clean to remove any executables that are laying around and then
run git status . to make sure you did not forget to add/commit any of
your files.