Jump to: navigation, search

Chapter 6 - Arrays and pointers

An array is a group of numbers. A pointer is an object whose value is the address in memory of another object (or of a function). These ideas appear to be very different. Nevertheless, arrays and pointers, whilst by no means being the same thing, are quite closely related, and it therefore makes sense to deal with them both in the same chapter.

Arrays

Introduction to arrays

We saw in the last chapter that computers become really useful when they are able to execute a block of code repeatedly. Our table of square numbers was really the first program we have so far seen that has enabled us to do something quicker by computer than we could reasonably have hoped to do with pencil and paper.

Because we wanted to process our numbers in strict arithmetical order, it was easy to calculate one number from the previous number (just add 1). But if the relationship between our numbers were not so obvious, it would be much harder to write the loop. It would really be more useful to us if we could specify a list of numbers that we want to process. For example, what if we wanted to produce a list of the squares of the first twenty prime numbers?

In C, an array is a group of objects that all have the same type. So far, the only type we have really become familiar with is the int type, so we'll start with that.

We define an array by specifying what type of number we want, and how many we want of that type of number, like this:

  int prime[20];

This definition reserves storage for twenty ints, all arranged contiguously in the memory of the computer. We can access these ints individually, using an index. An index is simply an integer. For a twenty-element array, the legal index values range from 0 to 19.

The square brackets, technically, constitute an operator (although I don't think most people think of them as such).

We can initialise the array if we wish, by enclosing a list of values in braces, as follows:

  int prime[20] =
  {
     2,  3,  5,  7, 11, 13, 17, 19, 23, 29,
    31, 37, 41, 43, 47, 53, 59, 61, 67, 71
  };

You will note that the initialisers are separated by commas. You don't need a comma after the last initialiser.

To access a single element of the array, we specify an index value by enclosing it in square brackets, like this:

  int firstprime = prime[0];

The expression prime[0] means the first element in the prime array, which in this case is 2. So firstprime takes the value 2.

We don't have to use a literal integer 0 as the index. We can use an object instead. Thus:

  int index = 1;
  int secondprime = prime[index];

Since index has the value 1, prime[index] has the value prime[1], which is the second element of our array (remember, the first value was prime[0]). Since the second element of our array is 3, secondprime takes the value 3.

Here, then, is a program to print the squares of the first twenty primes.

#include <stdio.h>

void print_integer(int);

int main(void)
{
  int prime[20] =
  {
     2,  3,  5,  7, 11, 13, 17, 19, 23, 29,
    31, 37, 41, 43, 47, 53, 59, 61, 67, 71
  };

  int index = 0;
  int square;

  while(index < 20)
  {
    square = prime[index] * prime[index];

    print_integer(prime[index]);
    putchar(' ');
    print_integer(square);
    putchar('\n');

    index = index + 1;
  }
  return 0;
}

void print_integer(int n)
{
  if(n > 9)
  {
    print_integer(n / 10);
    n = n % 10;
  }
  putchar(n + '0');
}

You should spend a little time studying this program, and the associated output that you get from running it, which looks like this:

2 4
3 9
5 25
7 49
11 121
13 169
17 289
19 361
23 529
29 841
31 961
37 1369
41 1681
43 1849
47 2209
53 2809
59 3481
61 3721
67 4489
71 5041

We could even use arrays to make writing messages a little simpler. (We are, by degrees, approaching a usable way of writing messages!) Here is a program that writes the words Hello world! on the standard output device:

#include <stdio.h>

int main(void)
{
  int message[13] =
  {
    'H', 'e', 'l', 'l', 'o', ' ',
    'w', 'o', 'r', 'l', 'd', '!',
    '\n'
  };

  int index = 0;

  while(index < 13)
  {
    putchar(message[index]);
    index = index + 1;
  }
  return 0;
}

This program works well. Nevertheless, we could do better. At present, if we wish to write a different message, we have to count the letters very carefully so that we can get the while loop's condition right. If, however, there were a value that we would never want to print, we could place it at the end of the array, and then keep printing until we reach that value. The value 0 is good for this purpose. We'll never want to print the character with code point 0. (That's not '0', which we very often want to print! It's 0, not '0'. The '0' character is a digit character, but the character with code point 0 is a null character.) When we use a special value in this way to mark the end of data, it is known as a sentinel value.

Let's modify our program accordingly.

#include <stdio.h>

int main(void)
{
  int message[14] =
  {
    'H', 'e', 'l', 'l', 'o', ' ',
    'w', 'o', 'r', 'l', 'd', '!',
    '\n', 0
  };

  int index = 0;

  while(message[index] != 0)
  {
    putchar(message[index]);
    index = index + 1;
  }
  return 0;
}

C provides us with a handy shortcut for defining arrays. If we are going to initialise the array with all the values we want to store in it, then the compiler can work out how big the array should be, without our having to tell it explicitly. So we can do this:

#include <stdio.h>

int main(void)
{
  int message[] =  /* NOTE the absence of an element count! */
  {
    'H', 'e', 'l', 'l', 'o', ' ',
    'w', 'o', 'r', 'l', 'd', '!',
    '\n', 0
  };

  int index = 0;

  while(message[index] != 0)
  {
    putchar(message[index]);
    index = index + 1;
  }
  return 0;
}

As long as we remember to include the initialiser list, the above program works just as you would expect. What's more, we can now change the message, without having to re-count the letters:

#include <stdio.h>

int main(void)
{
  int message[] =  /* The compiler will count the letters for us */
  {
    'T', 'h', 'i', 's', ' ', 'a', 'r', 'r', 'a', 'y', ' ',
    'h', 'a', 's', ' ', 'm', 'o', 'r', 'e', ' ',
    'l', 'e', 't', 't', 'e', 'r', 's', ' ',
    't', 'h', 'a', 'n', ' ', 'b', 'e', 'f', 'o', 'r', 'e', '!',
    '\n', 0
  };

  int index = 0;

  while(message[index] != 0)
  {
    putchar(message[index]);
    index = index + 1;
  }
  return 0;
}
The char type

It isn't just ints that you can place in an array. For example, there is another basic C type, the char. In C, a char is a rather small integer. In fact, the only numbers you can be absolutely sure of representing in a char are 0 to 127. You might be able to store negative numbers in it, in which case you're guaranteed a range of -127 to +127 at least. If you're not allowed negative numbers, there is a consolation: a guaranteed range of 0 to 255.

This may seem like a backward step from int, but the char type turns out to be very useful when you want to represent character data. Every letter of the Roman alphabet, both upper and lower case; every digit character ('0' to '9'); and a considerable selection of punctuation characters -- all of these can be represented in a char, and all of them will have positive code point values (i.e. none of them are negative).

So why does the getchar function return an int, not a char? The simple answer is that it has to be able to return one special value that is not a char, an out-of-band value called EOF, which indicates that some kind of problem occurred or that there is no more data available on the standard input stream.

But, for character data that we know to be actual data, char is the best candidate.

We can, of course, define an array of char, like this:

#include <stdio.h>

int main(void)
{
  char message[] =  /* The compiler will count the letters for us */
  {
    'T', 'h', 'i', 's', ' ', 'a', 'r', 'r', 'a', 'y', ' ',
    'h', 'a', 's', ' ', 'm', 'o', 'r', 'e', ' ',
    'l', 'e', 't', 't', 'e', 'r', 's', ' ',
    't', 'h', 'a', 'n', ' ', 'b', 'e', 'f', 'o', 'r', 'e', '!',
    '\n', 0
  };

  int index = 0;

  while(message[index] != 0)
  {
    putchar(message[index]);
    index = index + 1;
  }
  return 0;
}

If you compare this program with the one before it, you will see that only one thing has changed: the type of the array. Now it's a char[20] array instead of an int[20] array. More importantly, one thing did not change: the call to putchar. So the question before us is: why not?

The putchar function requires an int argument to be passed to it, but message[index] is now a char, not an int. How is that allowable?

The answer is that a char can't be bigger than an int. In theory, it could be as big as an int, but it can't be bigger. And since a char is an integer, just like an int in that respect, the compiler has no problem at all in converting the smaller integer into the bigger one. This conversion process is called 'integer promotion', and it's a very useful shortcut.

There's another useful shortcut, too, that only applies to char. Let's take another look at our array of char from the previous program:

  char message[] =
  {
    'T', 'h', 'i', 's', ' ', 'a', 'r', 'r', 'a', 'y', ' ',
    'h', 'a', 's', ' ', 'm', 'o', 'r', 'e', ' ',
    'l', 'e', 't', 't', 'e', 'r', 's', ' ',
    't', 'h', 'a', 'n', ' ', 'b', 'e', 'f', 'o', 'r', 'e', '!',
    '\n', 0
  };

C gives us a shorthand for this, as follows:

  char message[] = "This array has more letters than before!\n";

Now isn't that an improvement! And, if you look very carefully, you will see that we didn't even have to insert our sentinel value of 0. C does that automatically. (We still have to put in the newline character, though, because that's something we want to retain control over. Sometimes we might have some more data to print before we write the newline character.)

Strings

This kind of array is so important in C that it has a special name: string. A string, then, is an array of char whose first null value (code point 0) marks the end of that string.

The construct in quotation marks ("This array has more letters than before!\n") is called a string literal. A string literal can be used to initialise an array of char, as shown above.

Please do understand that a C string is not a data type. It is a data format. If you don't have a sentinel 0 on the end (perhaps because you overwrote it with some other character value), it may still be an array of char but it's no longer a string. So do be careful with your sentinel 0 (normally known as the null terminating character, or the null terminator, or just null.

You may not be surprised to learn that C provides a library function for writing a string to the standard output device. That function is called puts. Unfortunately, the puts function writes a newline character as well as the string. If that's what you want, it's fine, but it's not always what you want. So, if you're going to use puts, remember that you won't be able to add any more to that line of text -- further output will go on the following line.

Here, then, at last, is a sane 'Hello world' program:

#include <stdio.h>

int main(void)
{
  puts("Hello, world!");
  return 0;
}

We didn't even have to define an array. C is quite happy to accept a string literal as an argument to puts.

I am carefully avoiding showing you the prototype for the puts function. We'll come to it shortly. In the meantime, let's see the puts function in action on some data we calculate at runtime:

#include <stdio.h>

int main(void)
{
  char output[16] = "The number is ";
  int input;
  puts("Please type a digit character. Then press ENTER.");
  input = getchar();
  output[14] = input;
  puts(output);
  return 0;
}

In this program, I have had to specify the number of characters I want in my array. This is because I need one more character than the string literal "The number is " will provide.

The program starts by reserving storage for sixteen char objects, which we might represent diagrammatically as follows:

  [T][h][e][ ][n][u][m][b][e][r][ ][i][s][ ][0][0]

(Those are code point 0s, not digit character '0's.)

Now, we can understand the first fifteen characters easily enough from the preceding discussion, but why is the last char set to 0 as well?

Partial array initialisation

If you don't specify an initialiser for an array at all, C doesn't do anything with the array except reserve storage for it. The values in that array are indeterminate, and could be pretty much anything.

If you fully specify an array's contents using an initialiser list, then obviously the whole list is honoured.

But if you only partly specify the contents, giving values for some elements but not others, C will zero-fill the rest of the array for you. This is guaranteed.

Back to our example program, then, and we can see now why I needed to specify an extra element. I needed room for the character that the program reads from the standard input stream. This character overwrites the value in output[14]. That was the sentinel value, the null terminator, but that's okay because I made room for another null terminator, and C obligingly wrote a 0 value into that position in the array, so I didn't have to worry about that.

There is just one more thing we need to clear up before we move on. In our example program, we have this line:

  output[14] = input;

But input is of type int, and output[14] is of type char. Why isn't this a problem?

Well, potentially it can be a problem when you try to place a value of a wider type into an object of a narrower type, like squeezing a quart into a pint pot. But in practice, getchar is going to send us a character from the basic character set (assuming it doesn't send us an error code instead), and all the characters in the basic character set have code points that will fit into a char. And so, as it turns out, there is no problem after all.

Pointers

One thing we haven't tried to do thus far in this tutorial is to change a value in main by passing it to a function. Let's try it now:

#include <stdio.h>

void change(int);

int main(void)
{
  int input = getchar();

  puts("Input received.");
  putchar(input);
  putchar('\n');

  change(input);
  puts("Tried to change to X: new value is:");
  putchar(input);
  putchar('\n');

  return 0;
}

void change(int i)
{
  i = 'X';
}

If you run this program and give input of, say, R (followed by the ENTER key), you will get output something like this:

R
Input received.R
Tried to change to X: new value is:
R

Why didn't this work?

The answer is that C passes data to functions by value. When we call change(input), the value of the input object is determined, and that value is passed to the change() function. The object itself is not passed. So change() gets, not the input object, but a copy of it. This copy is not tied to the original object in any way. So, when we update the value of that copy, the original is not affected.

Clearly it is beneficial to be able to change the value of an object from within a function. But how?

We can't change C's pass by value semantics. (Nor would we want to. A lot of the time, it's exactly what we want.) So what can we do?

To answer this question, let's think about what an object actually is. What characteristics does it have?

Firstly, an object has a type. Fair enough, but it's not going to help us here.

Secondly, an object has a value. But we've already seen that this isn't going to help us either.

But an object has a third characteristic, which is that it resides somewhere in the memory of the computer. This sounds more promising. If only we could work out where in memory it resides, perhaps there is some way that we can use that information within the function we are calling. If we could update the value stored at that memory location, that would achieve exactly what we want.

The address operator

To find out where in memory an object is stored, we use the address operator. This operator takes just one operand, the object whose address we wish to determine. (Thus, it is an example of a unary operator.) The result of this operation is a pointer. A pointer value is an address in the computer's memory.

The address operator looks like this: & - an ampersand. The operand follows it. So if we have an object named obj, then &obj is the memory address of obj. We can also call it a pointer to obj.

But that isn't quite enough. We also need a way to update the value stored at a particular address.

The indirection operator

Given a pointer p to some object, we can access (or update) the original object via the indirection operator, which is the * symbol. Yes, this is also the multiplication symbol, so we must be careful not to confuse them. When being used as an indirection operator, * takes just one operand, so it is another example of a unary operator.

If p points to (i.e. is the address of) some object obj, then *p is effectively an alias for obj.

Like any object, p must have a type. If we want p to point to an int, we give it the type int *.

Let's put this into the context of a program, just so that we can look at the syntax in operation.

int main(void)
{
  int n = 42; /* n is an int, and it has the value 42 */

  int *p;     /* p is an int *, which means a pointer to int */

  p = &n;     /* p now points to (stores the address of) n */

  *p = 6;     /* this means: change the value of the int object
                 that p points to, giving it the new value 6 */

              /* n how has the value 6 */

  return 0;
}

Note that we don't actually need to know where in memory n is. All we need is for that information to be stored in p. The actual print-it-out value is of no concern to us whatsoever.

The next step is to write a program that uses this technique to change an object's value from within a function. Let's take our original trial program, and rewrite it to use a pointer:

#include <stdio.h>

void change(int *);  /* This has changed from int to int *;
                        change() now takes not an int, but a
                        pointer-to-int. */

int main(void)
{
  int input = getchar();

  puts("Input received.");
  putchar(input);
  putchar('\n');

  change(&input);    /* This has changed too. Instead of passing the
                        value of the object, we pass the value of the
                        address of the object.
                      */
  puts("Tried to change to X: new value is:");
  putchar(input);
  putchar('\n');

  return 0;
}

void change(int *pi)  /* This has changed from int to int *;
                         change now takes not an int, but a
                         pointer-to-int. */
{
  *pi = 'X';          /* The final change: this means 'update the contents
                         of address pi with the new value 'X' */
}

Running this program with the same input as before, you will see this output:

R
Input received.R
Tried to change to X: new value is:
X

So it works. But why?

C is still passing the change() function a value. But the nature of the value is somewhat different now. Instead of passing the value of the object, we are passing the value of that object's address. Knowing the value of the object was no use to change(), but knowing where in memory it resides is very useful indeed. The fact that it received a copy of the address doesn't matter.

Here's an analogy to make this a little clearer (I hope). Imagine your windows need cleaning. Unfortunately, the local window cleaner is stone deaf, so you can't tell him your address. But you can show him a picture. You could, of course, take a photograph of your house, and carry the photograph to the window cleaner's place of business, and point at the windows. Well, he can wash the photograph all he likes, but it won't make your house's windows any cleaner. (This is like our first-try program.) But you could instead find something with your house address on it (say, a letter to you), photograph that, and carry it to the window-cleaner. He can read the photograph just as easily as you could read the original envelope. So he is able to go to that address, and your windows get cleaned after all.

The address of the house (a pointer-to-house) is on the envelope. But the address of the house (the pointer-to-house) is also on the photograph. It's a copy of the address, but for finding the house it's just as good as the original envelope.

As a matter of fact, we can stretch the analogy a little bit further. If, for any reason, the window-cleaner modifies the photograph, it will have no effect whatsoever on your house. If, for example, he takes a felt marker and modifies the photograph by overwriting the 3 in your address with a 4, this will not have any effect whatsoever on your house. To affect your house, he must actually go to the address you gave him.

The relationship between arrays and pointers

I said that arrays and pointers are intimately connected, and so they are. Here's the connection: when an array name is used without an index, in almost every case C will treat it as if it were a pointer to the first element of the array. (We'll cover the exceptions later.)

To illustrate this, let's create a function for printing a string onto the standard output device, without writing a newline character, so that we can write partial lines, adding the newline ourselves later on.

#include <stdio.h>

void write_string(char *); /* write_string takes a pointer-to-char */

int main(void)
{
  char report[] = "You entered the character ";
  int input;

  puts("Please type in a digit character and press ENTER.");

  input = getchar();

  write_string(report);
  putchar(input);
  putchar('\n');
  return 0;
}

void write_string(char *p)
{
  while(*p != 0)
  {
    putchar(*p);
    p = p + 1;
  }
  return;
}

The way that the write_string function works is profoundly important.

When we call write_string, we try to pass it an array:

  write_string(report);

But C's rules prevent this from happening. Instead, it is as if we had written:

  write_string(&report[0]);

That is, this reference to the report array is converted into a pointer to the first element of that array. And this is the value that is passed to the write_string function -- the address of (i.e. a pointer to) the first element.

The write_string function can now de-reference this value using the * operator, which lets it get at the character being pointed to. It tests this value to find out whether it is the null character that marks the end of the string. On finding out that it isn't the null character, write_string writes the value of the character on the standard output device using putchar, and then modifies the pointer by adding 1 to it. This has the effect of pointing p to the second element in the array (because array elements are contiguous in memory). Modifying the pointer itself will not have any effect on any object in the calling function, so we can move the pointer without worrying about that, just so long as we don't move it right off the end of the array.

Then the loop goes round again, but this time p is pointing to the second element, so it is the second element that is inspected to find out whether it's the null character. On this occasion it isn't, so the character is printed and then the pointer is again bumped along by one element. This loop goes round and round until eventually the last character has been printed, and the sentinel, the null terminator, is reached, at which point the write_string function stops executing and returns control to main.

And in case you're still wondering, that's pretty much how the puts function works (except that it irritatingly writes a newline character to the standard output device afterwards). So the prototype I promised you for puts is:

int puts(const char *);

(Don't worry about the const for now. It's just a promise that puts won't try to change your string.)

Things to do

Write a function to swap the values of two integer objects. You will need to pass their addresses to the function from main. Convince yourself that your program works (you may find the print_integer function we wrote earlier to be useful here).

Summary

In this chapter, you learned that arrays are contiguous groups of numbers that can be processed in a loop, you were introduced to strings, and you took your first steps towards understanding pointers.

In the next chapter, we will learn about some more of C's operators.

Progress

Terminology
  • array
  • index
  • pointer
  • sentinel value
  • null character
  • null terminator
  • string
  • sequence, selection, and iteration
  • control structure
  • recursion
  • code point
  • object
  • type
  • value
  • definition
  • assignment
  • initialisation
Syntax
  • comments
  • types
  • char
  • operators
    • assignment operators
      • the = operator
    • additive operators
      • the + operator
      • the - operator
    • multiplicative operators
      • the * operator
      • the / operator
      • the % operator
    • equality and relational operators
      • == != < > <= >= !
    • address and indirection operators
      • the unary * operator
      • the unary & operator
      • the array subscripting operator []
  • control structures
    • if/else
    • while
    • do/while
Standard library functions, by header
Personal tools