Motivation

Consider how you might write a program to read in some test scores and average them.

1. Our first attempt might be to use a variable to store each test score
   The problem with this approach is that we must know ahead of time how many test scores there will be, and changing this number requires editing and recompiling the program.
2. The second approach is to read the scores using a loop, accumulating the sum of the scores and counting the number of the scores as we go.
   This approach is promising, but if the requirements changed and we had to echo all the scores before displaying the average, we wouldn't be able to do this. Once the scores have been entered, we accumulate their value, but we cannot retrieve the individual scores.
3. In order to echo all the scores before displaying their average, we could use a recursive approach.
   This does work for any number of scores, however the scores are displayed in reverse order.

Solving the Scores Problem Using Arrays

The most natural way to solve the scores problem is to use arrays.

1. This solution declares a fixed-size array inside of main, which stores all the scores as they are entered.
   This allows use flexibility in how to use the scores, as they are all stored to be retrieved any way we wish. One limitation is that we must know the maximum number of scores ahead of time.
   A second version reads straight into the array, instead of into an intermediary variable.
2. We can pass the array to a function as a parameter, where the changes in the array are automatically reflected back to the calling part of the program.

Syntax for array declaration and usage

Rather than having to store multiple values of the same type in different variables, we can store them in an array. This is appropriate when we have a group of values of the same type, such as a list of numbers, or a group of characters representing a playing board for a game.

To declare an array, we use:
      type arrayName[ size];
where type can be any type (e.g. char, int, float), arrayName is an identifier you make up, and size indicates how many items will be stored in the array.

For example
      int theScores[ 10];
declares an array called theScores that can hold 10 integers. In the array shown above the first element is the 0th element, and the last is the 9th element. This element number is known as the index (a.k.a. the subscript) , which starts at 0 and goes to n-1 for an array of n elements.

Usage

1. Store a value into an array by using the array name with the subscript on the left-hand side of an assignment statement. E.g.:
         theScores[ 3] = 75;            // store 75 into array element 3 (the 4th element)
2. Retrieve a value from an array by using the array name with the subscript anywhere a value is needed. E.g.:
         printf(" %d", theScores[ 1]);
         sum = sum + theScores[ i];      // i is an integer between 0 and 10
3. You must make sure that you never read or write past the end of the array. The compiler will not stop you, but you may get strange results, as illustrated in this program.
4. Arrays can be initialized element by element in a loop
         for (i=0; i<10; i++) {
             theScores[ i] = 0;    
         }
   or by putting initial values in braces when the array is declared:
        int theScores[ 10] = {0,0,0,0,0,0,0,0,0,0};
   In the above case the size can be inferred from the number of initializing values, so this could be rewritten as:
        int theScores[ ] = {0,0,0,0,0,0,0,0,0,0};

Examples

The Maze Problem

Consider the maze problem, where there is a rabbit in a maze. The maze is represented as a one-dimensional array. There are several different versions of the solution:

maze1 shows how to make moves and how recursion explores all possible paths. The program gives a message once it reaches the destination, but it doesn't stop recursing, nor does it print a solution.

maze2 shows the solution path, though it is in reverse order.

maze3 uses recursion to give the solution path in order

maze4 eliminates the use of global variables, passing everything as a parameter.

Counting Characters

This program reads characters from an input file and counts how many there are of each character.

Searching and Sorting

This program uses binary searching to find a particular integer key within an array of ordered numbers, and bubble sort to put some integers in an array into ascending order.

Character Stack

A character stack can be used to check for balanced parenthesis in an input expression.

2-Dimensional Arrays

Why do we need 2-D arrays? Some information is easier to manage that way (tables, text, matrices, etc.)

Example: 2-D array to store results of temperature conversion table

Passing 2-D arrays to functions

In the above example, note that the first dimension of a multi-dimensional array can be omitted. This is because:

1. C does not check to make sure you stay within bounds of an array
2. Multi-dimensional arrays are stored row-major
   We could "spoof" a 2-D array using a one-dimensional array, which is actually what happens inside the machine, since computer memory is addressed linearly.

Dynamic Arrays

If we don't know the size of the array ahead of time, we would need dynamic arrays. (These examples require some knowledge of pointers)

[CS Dept] [UIC] [Prof. Reed]