Introduction to C Programming

Introduction to C Programming by Rob Miles, Electronic Engineering


Arrays

Why We Need Arrays
Sorting
Array Types and Sizes
More Than One Dimension

Why We Need Arrays

Your fame as a programmer is now beginning to spread far and wide. The next person to come and see you is the chap in charge of the local cricket team. He would like to you write a program for him which allows the analysis of cricket results. What he wants is quite simple; given a list of cricket scores he wants a list of them in ascending order.

"This is easy" you think. Having agreed the specification and the price you sit down that night and start writing the program. The first thing to do is define how the data is to be stored:

int score1, score2, score3, score4, score5, score6, score7
	score8, score9, score10, score11 ;

Now you can start putting the data into each variable:

printf ( "\nEnter the score for each player in turn.\n\n" ) ;
scanf ( "%i", &score1 ) ;
scanf ( "%i", &score2 ) ; 
scanf ( "%i", &score3 ) ;
scanf ( "%i", &score4 ) ;
scanf ( "%i", &score5 ) ; 
scanf ( "%i", &score6 ) ;
scanf ( "%i", &score7 ) ;
scanf ( "%i", &score8 ) ; 
scanf ( "%i", &score9 ) ; 
scanf ( "%i", &score10 ) ; 
scanf ( "%i", &score11 ) ;

All we have to do next is sort them..... Hmmmm..... This is awful! There seems to be no way of doing it. Just deciding whether score1 is the largest value would take an if construction with 10 comparisons! Clearly there has to be a better way of doing this, after all, we know that computers are very good at sorting this kind of thing.

C provides us with a thing called an array. An array allows us to declare a whole row of a particular kind of box. We can then use things called subscripts to indicate which box in the row that we want to use. Consider the following:

void main ()
{
	int scores [11] ;
	int i ;
	for (i=0; i<11; i=i+1) {
		scanf ( "%i", &scores [i] ) ;
	}
}

The int scores [11] tells the compiler that we want to create an array. The bit which defines the size of the array is the [11]. When C sees this it says "aha! What we have here is an array". It then gets some pieces of wood and makes a long thin box with 11 compartments in it, each large enough to hold a single integer. It then paints the whole box red - because boxes which can hold integers are red - and then writes "scores" on the side.

Each compartment in the box is called an element. In the program you identify which element you mean by putting it's number in square brackets [ ] after the array name. This part is called the subscript. Note that the thing which makes arrays so wonderful is the fact that you can specify an element by using a variable, as well as a constant. In fact you can use any expression which returns an integer result as a subscript, i.e.

scores [i+1]

- is quite OK.

C numbers the boxes starting at 0. This means that you specify the first element of the array by giving the subscript 0. There is consequently no element scores [11]. If you look at the part of the program which reads the values into the array you will see that we only count from 0 to 10. This is very important. An attempt to go outside the array bounds of scores will not cause an error, but could lead to unpredictable things happening!

The real power of arrays comes from our being able to use a variable to specify the required element. By running the variable through a range of values we can then scan through an array with a very small program; indeed to change the program to read in 1000 scores we only have to make a couple of changes:

void main ()
{
	int scores [1000] ;
	int i ;
	for (i=0; i<1000; i=i+1)	{
		scanf ( "%i", &scores [i] ) ;
	}
}

The variable i now goes from 0 to 999, vastly increasing the amount of data we are storing. Note that if I ever create arrays like this I would use #define to set the limits on the sizes, so that I can easily change them later.

Sorting

Now we can think about sorting our list of cricket scores. Because of the human passion for order computers spend a lot of their time sorting things. There are vast and dusty tomes in any programming archive on the subject of sorting, and if you look carefully you will find that C actually has a sort routine hidden in one of its libraries. However, we are not going to use a piece of ready written code, we are going to do it all our way - perhaps humming a song made famous by Frank Sinatra.

If you were given 11 numbers to put in order you would look through them for the biggest, write it down and then put down the second largest (which you spotted while you were looking for the biggest) then add the third, which you might have to look for, and then add the others which you can easily pick out from the remainder. In short you would apply massive amounts of processor power (i.e. your brain) in a fairly random, inefficient way. The problem is that when you try to write a program to sort a list of numbers you will find it difficult to describe to yourself how you would do the task, so explaining the task in C is rather difficult!

In the fullness of time you will get used to all the little tricks used when programming, and come to terms with the way that computers "think". Eventually you will be able to think down to the level of the computer, and at that point you can call yourself a programmer!

We are going to use a neat little sorting method called the Bubble Sort. This is a very simple sorting routine which is easy to write and make work. It involves the writing a program which works in following way:

  1. Start at the top of the array.

  2. Look at the first and the second elements.

  3. If they are the wrong way round, swap them.

  4. Look at the second and third elements.

  5. If they are the wrong way around, swap them.

  6. Keep on doing this until you get to the end of the array.

  7. Go back to the first step.

The little "program" above does not have a way of stopping, however it is quite easy to decide when you have finished, if you go through the entire list without making any swaps the list must be in the correct order. This solution, whilst a bit boring for a human brain, is the kind of thing that computers just love to bits, a C version of this is:

#include <stdio.h>
#define teamsize 11
void main ()
{
	int scores [teamsize] ; int i, swaps, temp ;
	printf ( "Cricket score sorter 1.0\n" );
	printf ( "Rob Miles\n\n" ) ;
	printf ( "Give each score and press return\n\n" ) ;
	for (i=0; i<teamsize; i++) {
		printf ( "Score for batsman %d : ", i+1 ) ; 
		scanf ( "%d", &scores [i] ) ;
	}
	printf ( "\nNow doing the sorting..." ) ;
	do {
		swaps = 0 ; /* clear our swap marker */
		for (i=0 ; i<10; i++) {
			if ( scores [i] > scores [i+1] ) {
				/* if we get here we have to do a swap */
				 temp = scores [i+1] ;
				scores [i+1] = scores [i] ;
				scores [i] = temp ;
				swaps = 1 ; /* mark a swap */ 
			}
		}
	} while (swaps != 0) ;

	printf ( "\nThe results are : \n\n" ) ;

	for ( i=0; i<teamsize; i++) {
		printf ( " %d\n", scores [i] ) ;
	}
}

The program above actually works! It splits naturally into three chunks, reading the data, sorting the data and printing the results out. Note the use of a temporary variable when we swap the elements around. Note also that, because we compare a value with the one after it in the array, we only count as far as 10 in the loop which does a pass through the data. If we said 11 the program would still run, but we might find a strange value from beyond the end of the array appearing in our data!


Array Types and Sizes

You can have arrays of any type you like, including ones that you create (see later). There is usually a limit on the maximum length of array that you can create, but this is usually very large and depends on the version of C that you are using.

The C compiler needs to know how big an array is going to be, i.e. when you write your program you must decide the amount of data you want to store. This can lead to problems, sometimes you do not know in advance how big an array needs to be. You run the risk of either asking the compiler for too much in which case your program will use more memory than it needs, or not asking for enough, in which case your program might fail for lack of room. As we shall see later, this problem is not insurmountable, but for now we must assume that our program must declare an array of appropriate size, and we must decide that size when we write the program itself.

More Than One Dimension

The array provides us with a way of grabbing a row of boxes, and accessing each box with a subscript. This is fine for linear lists of data, but sometimes you want to hold data of a different shape, perhaps a table or matrix.

You would hit this problem if your cricket playing friend comes back the following week, very pleased with your program and, as users always are, anxious to have it do something else. In this case he wants you to store the results of a whole team season, and then do various statistical things with them which are so beloved of cricket players, in this case find the highest score of the season and player who scored the greatest number of runs in the season.

Resisting the temptation to point him at a spreadsheet program, which is what he really needs, you agree to improve your software. You now have to store several rows of data. If you were writing the results down on paper you might have something like:

Player    Games                          
          0      1      2      3      
0         10     23     25     80     
1         12     34     23     54     
2         23     54     6      7      
3         16     54     62     8      
4         40     23     65     4      
5         21     76     8      0      
6         4      43     32     2      
7         20     12     23     1      
8         12     43     22     11     
9         3      12     23     15     
10        32     2      32     43     

From this table you can see that the runs scored in game number 2 by player number 1 are 23 . You identify a particular score by looking along the top for the game number and down the side for the player number. Note that in my table I am numbering the rows and columns starting at 0, i.e. I have a game number 0 and a player number 0, which you might not have in real life (you would need to adjust the values when you display the answers (or make all the dimensions 1 bigger and then waste element 0).

If you think about the data above you can see that it is just a number of one dimensional arrays, i.e. the scores for a number of games which have been put side by side. C lets you create arrays of arrays:

#define TEAMSIZE 11
#define SEASONLENGTH 4
....
int scores [SEASONLENGTH]  [TEAMSIZE] ;

-what we have here is a number of arrays of length teamsize, one for each match in the season. I can refer to each individual element by giving two subscripts:

scores [2] [1]

- would refer to the score in game 2 of player 1. You can have as many arrays of arrays as you like, the only limit being your brainpower when it comes to sorting out what things mean...

The program to solve our problem would go as follows:

/* Cricket team score analyser  */
/* Rob Miles - 1993   */
/* Reads in the scores from 6 cricket seasons and then */ 
/* prints out some statistics */

#include <stdio.h> 

#define TEAMLENGTH 11 
#define SEASONLENGTH  7
void main ()
{
	/* define our main storage array */ 
	int scores [SEASONLENGTH] [TEAMLENGTH] ;

	/* define our totals array */
	int totals [TEAMLENGTH] ;

	/* define our counters	 */
	int game_count, player_count ;

	/* topscore holds the highest score so far */
	int topscore ;

	/* first read our data */
	for (	game_count = 0 ; 
		game_count < SEASONLENGTH ; 
		game_count++) {
		for (	player_count = 0 ; 
			player_count < TEAMLENGTH ;
			player_count++) {
			printf ( "Enter score for player %d game %d : ",
				game_count+1, player_count+1 ) ;
			scanf ( "%d",
				 &scores [game_count][player_count] ) ; 
			}
		}

	/* now zero our totals array */
	for (	player_count = 0 ; 
		player_count < TEAMLENGTH ;
		player_count++) {
		totals [player_count] = 0 ;
	}

	/* Now set our initial top score */
	topscore = 0 ;
	/* Now work out our results */
	for (	game_count = 0 ; 
		game_count < SEASONLENGTH ;
		 game_count++) {
		for (	player_count = 0 ;
			 player_count < TEAMLENGTH ;
			player_count++) {

			/* increase our totals */
			totals [player_count] +=
				scores [game_count] [player_count] ;

			/* decide if we have a highscore  */
			/*  bigger than our current one */
			if ( scores [game_count] [player_count] >
				topscore) {
				 topscore = 
				        scores game_count][player_count] ;
			}
		}
	}

	/* Now print out the results */ 
	printf ( "\n\nScore totals:\n\n" ) ; 
	for (	player_count = 0 ; 
		player_count < TEAMLENGTH ;
		player_count++ ) {
		printf ( "Total for player %d : %d\n", player_count+1,
			totals [player_count] ) ;
	}
	printf ( "\n\nHighest score was : %d\n\n", topscore ) ;
}

You will find it very useful to study this code carefully, it contains many programming tricks you will use in your programs over and over again!

As a little exercise you may wish to try the following modifications to the program :


Rob Miles, R.S.Miles@e-eng.hull.ac.uk, Electronic Engineering
HTML by Bronwen Reid, July 1995