Arrays in C

The goal of this tutorial is to learn how to use basic static arrays in C.

We will also continue to make use of the turtle graphics library used in the last class.

Learning Objectives

By the end of this lab, you should be able to:

Write basic C programs using arrays and strings
Calculate the length of arrays
Traverse and search an array in multiple directions and intervals
Use arrays in combination with turtle graphics to draw lines and triangles
Explain C strings and their storage format

Starter Code

Begin by downloading the starter files:

IN THE LINUX LAB (ISAT 250): Download lab03.tar.gz and untar it from the command line with the following command from the folder that you saved the file in:

tar -zxvf lab03.tar.gz

IN THE MAC LAB (ISAT 248): Download lab03.zip and unzip it by either double-clicking it or using the following command line command in the Terminal from the folder that you saved the file in:

unzip lab03.zip

The starter code has four files, a main.c, which you will be modifying; turtle.h and turtle.c, which contain the turtle graphics library; and an Makefile to help with building the lab.

An array of options

Array data types

An array in C is a bounded sequence of memory locations that store data elements. These locations are accessed by an indexed offset from the variable name. Some examples of arrays are a list of grades for students in a class, salaries for employees in a company, or number of seats in each row at a theater.

An array can be of any C type, but all elements in the array must be of the same type.

One important difference betweeen C and Java is that in Java the size of the array is explicitly tracked by the language runtime, while C arrays do not explicitly track such information.

In particular, this means that you no longer have a .length attribute attached to each array. In Java, you might have done something like this:

    int[] numbers = {1, 2, 5, 9};
    for (int i = 0; i < numbers.length; i++) {
        System.out.println(numbers[i]);
    }

In C, however, there is no numbers.length attribute to access, and we would have to track the length manually. Thus, the loop above would have to be written something like:

    int numbers[4] = {1, 2, 5, 9};
    for (int i = 0; i < 4; i++) {
        printf("%d\n", numbers[i]);
    }

More importantly: if you write a function that takes an array as input, it will need to also take the length of the array as input. For example, in Java you could write an arithmetic product function like this:

    public int product(int[] nums)
    {
        int prod = 1;
        for (int i = 0; i < nums.length; i++) {
            prod *= nums[i];
        }
        return prod;
    }

In C, because there is no nums.length, you should pass the length of the array in as a parameter to the function as well:

    int product(int nums[], int nums_len)
    {
        int prod = 1;
        for (int i = 0; i < nums_len; i++) {
            prod *= nums[i];
        }
        return prod;
    }

Question: Can you think of another way to solve this problem? How else could we indicate the end of an array?

Declaration of an array

Static arrays in C are declared using syntax similar to (but not identical to) Java's:

    int numbers[4];         // this creates an array of four integers

Recall that in Java, you must both declare and allocate space for an array before you use it:

    int[] numbers = new int[4];

This is not the case for the kind of C arrays that we will use in this lab.

Arrays can also be declared and initialized in one statement as such:

    int a[4] = { 1, 2, 3, 4 };

Question: What would happen if you tried to read an array location before writing something to it?

Question: Can you create an array with a negative size?

Memory model

It is important to note at this point that the C arrays that we will use in this lab are allocated in a very different way than the arrays in Java.

Specifically, we are only currently using fixed-sized arrays, which means that the space for the array can be allocated from a fixed-size chuck of memory that is reserved for the program when it launches (or when the current function is executed). This means that we don't have to do any memory management, but it also means that we must know exactly how large each array should be in advance.

In Java, however, arrays were allocated from heap memory, which is a large pool of memory available to a program while it is running. You may not have been aware of this because Java managed the memory for you. In C, this is not the case, and you will need to think carefully about how much memory to reserve and when to reserve it.

Next week, we will learn how to allocate space for arrays and other data structures on the heap in C, but for now we will stick with fixed-size arrays.

We are also glossing over the details of how arrays are passed into functions. For now, just realize that you can pass arrays into functions by putting "[]" brackets after the parameter name in the function signature:

    int my_function(int numbers[], char characters[])

Also, we will for now NOT use arrays as return values from functions. Next week we will learn how to do this.

Exercise: Your first foray into arrays

For our first excercise, let's find the sum of elements in an array of numbers of type int.

DO THIS: Fill in the code of the sum function:

    int sum(int nums[], int nums_len) {
        // add your code here
        return 0;
    }

The input to this function is an array of integers and the length of that array. The output of the function is the sum of all numbers in the array. Add a call to sum() in your main() function to test it.

Multidimensional arrays

The C language provides support for multidimensional arrays. For instance, we could have an array of two dimensions to store x and y coordinates of points, or we could have a 3 dimensional array to store Minecraft-like block/cube data.

The syntax for declaring and accessing multidimensional arrays is array[i][j] where i is the row index and j is the column index.

A two-dimensional array of (x,y) points could be created in C as follows:

    int my_points[4][2] = {
        {11,12},
        {13,14},
        {15,16},
        {17,18}
    };

You can also think of multidimensional arrays as "array of arrays". In the example above, the first dimension ([4]), tells us that we are creating an array with 4 entries, and the second dimension ([2]) says that each of those four entries is itself an array with two entries (an x-coordinate and a y-coordinate).

Our first point is (x,y) = (11,12), which is stored at array[0]. To access the x-coordinate of this first point you would use my_points[0][0] and to access the y-coordinate of the first point, you would use: my_points[0][1].

Similarly, the value of my_points[1][0] is 13 and the value of my_points[1][1] is 14.

Question: How would you access the y-coordinate of the third point?

Exercise: Drawing points

DO THIS: Fill in the code of the draw_points function:

    void draw_points(int points[][2], int num_points) {
        // add your code here
    }

The input to draw_points is a 2D array named points, containing num_points number of points stored in the same way as in the example above.

As output, your function should draw all of the points in points using the turtle graphics library. You may use the turtle_draw_pixel function, or you may manually move the turtle using turtle_goto function and draw the point using the turtle_draw_dot function. See the link for documentation on these functions.

The resulting image should have four dots in a diagonal row, as below:

Dots

Recall the following instructions for viewing the turtle graphics output:

IN THE LINUX LAB (ISAT 250): Use the following command from the project folder:

`eog output.bmp`

IN THE MAC LAB (ISAT 248): Double-click the bitmap file in Finder or use the following command in the Terminal from the project folder:

`open output.bmp`

Exercise: Drawing line segments

DO THIS: Fill in the code of the draw_segments function:

    void draw_segments(int points[][2], int num_points) {
        // add your code here
    }

The input to draw_segments is a 2D array named points that represents a list of segment endpoints. Each consecutive pair of points represents the two endpoints for a single segment. Note that because each segment has two endpoints, the length of points should be twice the value of num_points. As output, your function should draw the segments using turtle graphics.

For example, if your code is called in the following way:

    int my_segments[4][2] = {
        {10,40},
        {70,100},
        {50,40},
        {10,80}
    };
    draw_segments(my_segments, 2)

Then your code should draw two line segments as below:

Line segments

C strings

As with arrays, strings are handled a bit differently (and more low-level) than in Java.

In Java a string is stored in an actual object, which gives you access to various helpful attributes and functions, most notably a .length attribute for determining the length of the string. In C, however, a string is just an array of characters. You can declare and initialize a simple static C string using code like this:

    char my_message[] = "C ya, Morehead State!!";

This defines a string simply as a character array. Since a string is just an array, you can access a single character the same way you would an element of an array, i.e. my_message[6] will give you the 7th character (which is 'M')

Note that the quotes are really just syntactic sugar for a long array of characters. It is not, in principle, different from:

    char my_message[22] = {'C', ' ', 'y', 'a', ',', ' ',
        'M', 'o', 'r', 'e', 'h', 'e', 'a', 'd', ' ',
        'S', 't', 'a', 't', 'e', '!', '!'};

There is one important caveat. Notice that in the second case, as we have above, we gave the length of the array (22), but in the first case we did not.

Why? This is because C strings are just character arrays, but by convention they have one extra special character at the end. This character is called the null terminator, has the value zero, and is indicated in C code using an escape code: '\0'. In other words, the first definition for my_message above is really equivalent to:

    char my_message[23] = {'C', ' ', 'y', 'a', ',', ' ',
        'M', 'o', 'r', 'e', 'h', 'e', 'a', 'd', ' ',
        'S', 't', 'a', 't', 'e', '!', '!', '\0'};

Why is this helpful? The main reason is that when we are dealing with strings, unlike arrays, we don't necessarily have to keep track of how long the string is. We can simply rifle through the string until we find the null terminator '\0'. In fact, you can now use this to determine the length of any given string:

Exercise: Length of strings

DO THIS: Fill in the code of the string_length function:

int string_length(char my_string[]) {
    // add your code here
    return 0;
}

This function takes a character string (char[]) as input and returns the length of the string as an int.

Exercise: String splitting

DO THIS: Fill in the code of the tokenize function:

void tokenize(char my_string[])
{
    // add your code here
}

This function takes as input a string made up of words separated by spaces, (e.g. "fifty-six to seven") and prints each word on a new line, e.g.:

fifty-six
to
seven

The function should print a newline character after each token, even the last one.

HINT: Use printf("%c", a_string[i]) to print the ith character of the string named a_string. Recall that %c is the printf format specifier for a char value.

String library reference

The standard C library provides many useful functions for working with strings. Most of these functions are declared in the string.h header file. Here is a full reference to these functions.

Optional exercises

Finding the minimum value

In this exercise we will explore finding minimum values in an array.

1) DO THIS: Create a function to return the minimum value of an array of numbers. It should have the following signature:

int min(int nums[], int nums_len)

This should take as input an array of integers called nums. The second parameter, nums_len is the length of the array.

Next we want to modify the function to return not just the minimum but another like the second smallest or 3rd smallest value.

2) DO THIS: Create a function that returns the k-th minimum value of an array. So for example, calling min_k(nums, n, 2) should return the 2nd smallest element in the array. Here is the function signature:

int min_k(int nums[], int nums_len, int k)

The input to this function is the array of integers, the length of the array, and an integer k specifying which minimum value to find. For instance if k=3 you should find the third smallest element in nums. If there are duplicate elements, you should only count them once.

3) DO THIS: Use the min_k function to print the array in sorted order. Use this signature:

void print_sorted(int nums[], int nums_len)

The function should print the whole array on a single line, with a space character after each number. The function should print a single newline after the last number (and its associated space).

Question: How efficient (or inefficient) is your solution? Can you think of a faster way to print a sorted version of the array?

Triangle man

Do This: Write a function with the following signature:

void draw_triangles(int points[][2], int num_points)

Your function should take as input an array of points; num_points is the number of points. Each three consecutive points represents a triangle. As output your function should draw each three consecutive points as a triangle.

Palindromes

DO THIS: Write a routine with the following signature:

bool is_palindrome(char word[])

Your function should determine if the given string is a palindrome word (can be written the same way forwards and backwards - like "madam", "otto", "anna", "redivider", "kayak", and "racecar". Empty words and one-character words should be considered palindromes for the purposes of this function.

Challenge exercise: Same things in strings