Teach Yourself C in 21 Days
- 15 -Pointers: Beyond the Basics
On Day 9, "Understanding Pointers," you were introduced to the basics of pointers, which are an important part of the C programming language. Today you'll go further, exploring some advanced pointer topics that can add flexibility to your programming. Today you will learn
Pointers to PointersAs you learned on Day 9, a pointer is a numeric variable with a value that is the address of another variable. You declare a pointer using the indirection operator (*). For example, the declaration
int *ptr; declares a pointer named ptr that can point to a type int variable. You then use the address-of operator (&) to make the pointer point to a specific variable of the corresponding type. Assuming that x has been declared as a type int variable, the statement
ptr = &x; assigns the address of x to ptr and makes ptr point to x. Again, using the indirection operator, you can access the pointed-to variable by using its pointer. Both of the following statements assign the value 12 to x:
x = 12; *ptr = 12; Because a pointer is itself a numeric variable, it is stored in your computer's memory at a particular address. Therefore, you can create a pointer to a pointer, a variable whose value is the address of a pointer. Here's how:
int x = 12; /* x is a type int variable. */
int *ptr = &x; /* ptr is a pointer to x. */
int **ptr_to_ptr = &ptr; /* ptr_to_ptr is a pointer to a */
/* pointer to type int. */
Note the use of a double indirection operator (**) when declaring a pointer to a pointer. You also use the double indirection operator when accessing the pointed-to variable with a pointer to a pointer. Thus, the statement
**ptr_to_ptr = 12; assigns the value 12 to the variable x, and the statement
printf("%d", **ptr_to_ptr);
displays the value of x on-screen. If you mistakenly use a single indirection operator, you get errors. The statement
*ptr_to_ptr = 12; assigns the value 12 to ptr, which results in ptr's pointing to whatever happens to be stored at address 12. This clearly is a mistake. Declaring and using a pointer to a pointer is called multiple indirection. Figure 15.1 shows the relationship between a variable, a pointer, and a pointer to a pointer. There's really no limit to the level of multiple indirection possible--you can have a pointer to a pointer to a pointer ad infinitum, but there's rarely any advantage to going beyond two levels; the complexities involved are an invitation to mistakes. Figure 15.1. A pointer to a pointer. What can you use pointers to pointers for? The most common use involves arrays of pointers, which are covered later in this chapter. Listing 19.5 on Day 19, "Exploring the C Function Library," presents an example of using multiple indirection.
Pointers and Multidimensional ArraysDay 8, "Using Numeric Arrays," covers the special relationship between pointers and arrays. Specifically, the name of an array without its following brackets is a pointer to the first element of the array. As a result, it's easier to use pointer notation when you're accessing certain types of arrays. These earlier examples, however, were limited to single-dimensional arrays. What about multidimensional arrays? Remember that a multidimensional array is declared with one set of brackets for each dimension. For example, the following statement declares a two-dimensional array that contains eight type int variables:
int multi[2][4]; You can visualize an array as having a row and column structure--in this case, two rows and four columns. There's another way to visualize a multidimensional array, however, and this way is closer to the manner in which C actually handles arrays. You can consider multi to be a two-element array, with each of these two elements being an array of four integers. In case this isn't clear to you, Figure 15.2 dissects the array declaration statement into its component parts. Figure 15.2. The components of a multidimensional array declaration. Here's how to interpret the components of the declaration:
You read a multidimensional array declaration starting with the array name and moving to the right, one set of brackets at a time. When the last set of brackets (the last dimension) has been read, you jump to the beginning of the declaration to determine the array's basic data type. Under the array-of-arrays scheme, you can visualize a multidimensional array as shown in Figure 15.3. Figure 15.3. A multidimensional array can be visualized as an array of arrays. Now, let's get back to the topic of array names as pointers. (This is a chapter about pointers, after all!) As with a one-dimensional array, the name of a multidimensional array is a pointer to the first array element. Continuing with our example, multi is a pointer to the first element of the two-dimensional array that was declared as int multi[2][4]. What exactly is the first element of multi? It isn't the type int variable multi[0][0], as you might think. Remember that multi is an array of arrays, so its first element is multi[0], which is an array of four type int variables (one of the two such arrays contained in multi). Now, if multi[0] is also an array, does it point to anything? Yes, indeed! multi[0] points to its first element, multi[0][0]. You might wonder why multi[0] is a pointer. Remember that the name of an array without brackets is a pointer to the first array element. The term multi[0] is the name of the array multi[0][0] with the last pair of brackets missing, so it qualifies as a pointer. If you're a bit confused at this point, don't worry. This material is difficult to grasp. It might help if you remember the following rules for any array of n dimensions used in code:
In the example, therefore, multi evaluates as a pointer, multi[0] evaluates as a pointer, and multi[0][0] evaluates as array data. Now look at what all these pointers actually point to. Listing 15.1 declares a two-dimensional array--similar to those you've been using in the examples--and then prints the values of the associated pointers. It also prints the address of the first array element.
Listing 15.1. The relationship between a multidimensional array and pointers.1: /* Demonstrates pointers and multidimensional arrays. */
2:
3: #include <stdio.h>
4:
5: int multi[2][4];
6:
7: main()
8: {
9: printf("\nmulti = %u", multi);
10: printf("\nmulti[0] = %u", multi[0]);
11: printf("\n&multi[0][0] = %u\n", &multi[0][0]);
13: return(0);
12: }
multi = 1328
multi[0] = 1328
&multi[0][0] = 1328
ANALYSIS: The actual value might not be 1328 on your system, but all three values will be the same. The address of the array multi is the same as the address of the array multi[0], and both are equal to the address of the first integer in the array, multi[0][0]. If all three of these pointers have the same value, what is the practical difference between them in terms of your program? Remember from Day 9 that the C compiler knows what a pointer points to. To be more exact, the compiler knows the size of the item a pointer is pointing to. What are the sizes of the elements you've been using? Listing 15.2 uses the operator sizeof() to display the sizes, in bytes, of these elements.
Listing 15.2. Determining the sizes of elements.1: /* Demonstrates the sizes of multidimensional array elements. */
2:
3: #include <stdio.h>
4:
5: int multi[2][4];
6:
7: main()
8: {
9: printf("\nThe size of multi = %u", sizeof(multi));
10: printf("\nThe size of multi[0] = %u", sizeof(multi[0]));
11: printf("\nThe size of multi[0][0] = %u\n", sizeof(multi[0][0]));
12: return(0);
13: }
The output of this program (assuming that your compiler uses two-byte integers) is as follows:
The size of multi = 16 The size of multi[0] = 8 The size of multi[0][0] = 2 ANALYSIS: If you're running a 32-bit operating system, such as IBM's OS/2, your output will be 32, 16, and 4. This is because a type int contains four bytes on these systems. Think about these size values. The array multi contains two arrays, each of which contains four integers. Each integer requires two bytes of storage. With a total of eight integers, the size of 16 bytes makes sense. Next, multi[0] is an array containing four integers. Each integer takes two bytes, so the size of eight bytes for multi[0] also makes sense. Finally, multi[0][0] is an integer, so its size is, of course, two bytes. Now, keeping these sizes in mind, recall the discussion on Day 9 about pointer arithmetic. The C compiler knows the size of the object being pointed to, and pointer arithmetic takes this size into account. When you increment a pointer, its value is increased by the amount needed to make it point to the "next" of whatever it's pointing to. In other words, it's incremented by the size of the object to which it points. When you apply this to the example, multi is a pointer to a four-element integer array with a size of 8. If you increment multi, its value should increase by 8 (the size of a four-element integer array). If multi points to multi[0], therefore, (multi + 1) should point to multi[1]. Listing 15.3 tests this theory.
Listing 15.3. Pointer arithmetic with multidimensional arrays.1: /* Demonstrates pointer arithmetic with pointers */
2: /* to multidimensional arrays. */
3:
4: #include <stdio.h>
5:
6: int multi[2][4];
7:
8: main()
9: {
10: printf("\nThe value of (multi) = %u", multi);
11: printf("\nThe value of (multi + 1) = %u", (multi+1));
12: printf("\nThe address of multi[1] = %u\n", &multi[1]);
13: return(0);
14: }
The value of (multi) = 1376
The value of (multi + 1) = 1384
The address of multi[1] = 1384
ANALYSIS: The precise values might be different on your system, but the relationships are the same. Incrementing multi by 1 increases its value by 8 (or by 16 on a 32-bit system) and makes it point to the next element of the array, multi[1]. In this example, you've seen that multi is a pointer to multi[0]. You've also seen that multi[0] is itself a pointer (to multi[0][0]). Therefore, multi is a pointer to a pointer. To use the expression multi to access array data, you must use double indirection. To print the value stored in multi[0][0], you could use any of the following three statements:
printf("%d", multi[0][0]);
printf("%d", *multi[0]);
printf("%d", **multi);
These concepts apply equally to arrays with three or more dimensions. Thus, a three-dimensional array is an array with elements that are each a two-dimensional array; each of these elements is itself an array of one-dimensional arrays. This material on multidimensional arrays and pointers might seem a bit confusing. When you work with multidimensional arrays, keep this point in mind: An array with n dimensions has elements that are arrays with n-1 dimensions. When n becomes 1, that array's elements are variables of the data type specified at the beginning of the array declaration line. So far, you've been using array names that are pointer constants and that can't be changed. How would you declare a pointer variable that points to an element of a multidimensional array? Let's continue with the previous example, which declared a two-dimensional array as follows:
int multi[2][4]; To declare a pointer variable ptr that can point to an element of multi (that is, can point to a four-element integer array), you would write
int (*ptr)[4]; You could then make ptr point to the first element of multi by writing
ptr = multi; You might wonder why the parentheses are necessary in the pointer declaration. Brackets ([ ]) have a higher precedence than *. If you wrote
int *ptr[4]; you would be declaring an array of four pointers to type int. Indeed, you can declare and use arrays of pointers. This isn't what you want to do now, however. How can you use pointers to elements of multidimensional arrays? As with single-dimensional arrays, pointers must be used to pass an array to a function. This is illustrated for a multidimensional array in Listing 15.4, which uses two methods of passing a multidimensional array to a function.
Listing 15.4. Passing a multidimensional array to a function using a pointer.1: /* Demonstrates passing a pointer to a multidimensional */
2: /* array to a function. */
3:
4: #include <stdio.h>
5:
6: void printarray_1(int (*ptr)[4]);
7: void printarray_2(int (*ptr)[4], int n);
8:
9: main()
10: {
11: int multi[3][4] = { { 1, 2, 3, 4 },
12: { 5, 6, 7, 8 },
13: { 9, 10, 11, 12 } };
14:
15: /* ptr is a pointer to an array of 4 ints. */
16:
17: int (*ptr)[4], count;
18:
19: /* Set ptr to point to the first element of multi. */
20:
21: ptr = multi;
22:
23: /* With each loop, ptr is incremented to point to the next */
24: /* element (that is, the next 4-element integer array) of multi. */
25:
26: for (count = 0; count < 3; count++)
27: printarray_1(ptr++);
28:
29: puts("\n\nPress Enter...");
30: getchar();
31: printarray_2(multi, 3);
32: printf("\n");
33: return(0);
34: }
35
36: void printarray_1(int (*ptr)[4])
37: {
38: /* Prints the elements of a single four-element integer array. */
39: /* p is a pointer to type int. You must use a type cast */
40: /* to make p equal to the address in ptr. */
41:
42: int *p, count;
43: p = (int *)ptr;
44:
45: for (count = 0; count < 4; count++)
46: printf("\n%d", *p++);
47: }
48:
49: void printarray_2(int (*ptr)[4], int n)
50: {
51: /* Prints the elements of an n by four-element integer array. */
52:
53: int *p, count;
54: p = (int *)ptr;
55:
56: for (count = 0; count < (4 * n); count++)
57: printf("\n%d", *p++);
58: }
1
2
3
4
5
6
7
8
9
10
11
12
Press Enter...
1
2
3
4
5
6
7
8
9
10
11
12
ANALYSIS: On lines 11 through 13, the program declares and initializes an array of integers, multi[3][4]. Lines 6 and 7 are the prototypes for the functions printarray_1() and printarray_2(), which print the contents of the array. The function printarray_1() (lines 36 through 47) is passed only one argument, a pointer to an array of four integers. This function prints all four elements of the array. The first time main() calls printarray_1() on line 27, it passes a pointer to the first element (the first four-element integer array) in multi. It then calls the function two more times, incrementing the pointer each time to point to the second, and then to the third, element of multi. After all three calls are made, the 12 integers in multi are displayed on-screen. The second function, printarray_2(), takes a different approach. It too is passed a pointer to an array of four integers, but, in addition, it is passed an integer variable that specifies the number of elements (the number of arrays of four integers) that the multidimensional array contains. With a single call from line 31, printarray_2() displays the entire contents of multi. Both functions use pointer notation to step through the individual integers in the array. The notation (int *)ptr in both functions (lines 43 and 54) might not be clear. The (int *) is a typecast, which temporarily changes the variable's data type from its declared data type to a new one. The typecast is required when assigning the value of ptr to p because they are pointers to different types (p is a pointer to type int, whereas ptr is a pointer to an array of four integers). C doesn't let you assign the value of one pointer to a pointer of a different type. The typecast tells the compiler, "For this statement only, treat ptr as a pointer to type int." Day 20, "Working with Memory," covers typecasts in more detail.
char *letters[26]; Arrays of PointersRecall from Day 8, "Using Numeric Arrays," that an array is a collection of data storage locations that have the same data type and are referred to by the same name. Because pointers are one of C's data types, you can declare and use arrays of pointers. This type of program construct can be very powerful in certain situations. Perhaps the most common use of an array of pointers is with strings. A string, as you learned on Day 10, "Characters and Strings," is a sequence of characters stored in memory. The start of the string is indicated by a pointer to the first character (a pointer to type char), and the end of the string is marked by a null character. By declaring and initializing an array of pointers to type char, you can access and manipulate a large number of strings using the pointer array. Each element in the array points to a different string, and by looping through the array, you can access each of them in turn.
Strings and Pointers: A ReviewThis is a good time to review some material from Day 10 regarding string allocation and initialization. One way to allocate and initialize a string is to declare an array of type char as follows:
char message[] = "This is the message."; You could accomplish the same thing by declaring a pointer to type char:
char *message = "This is the message."; Both declarations are equivalent. In each case, the compiler allocates enough space to hold the string along with its terminating null character, and the expression message is a pointer to the start of the string. But what about the following two declarations?
char message1[20]; char *message2; The first line declares an array of type char that is 20 characters long, with message1 being a pointer to the first array position. Although the array space is allocated, it isn't initialized, and the array contents are undetermined. The second line declares message2, a pointer to type char. No storage space for a string is allocated by this statement--only space to hold the pointer. If you want to create a string and then have message2 point to it, you must allocate space for the string first. On Day 10, you learned how to use the malloc() memory allocation function for this purpose. Remember that any string must have space allocated for it, whether at compilation in a declaration or at runtime with malloc() or a related memory allocation function.
Array of Pointers to Type charNow that you're done with the review, how do you declare an array of pointers? The following statement declares an array of 10 pointers to type char:
char *message[10]; Each element of the array message[] is an individual pointer to type char. As you might have guessed, you can combine the declaration with initialization and allocation of storage space for the strings:
char *message[10] = { "one", "two", "three" };
This declaration does the following:
This is illustrated in Figure 15.4, which shows the relationship between the array of pointers and the strings. Note that in this example, the array elements message[3] through message[9] aren't initialized to point at anything. Figure 15.4. An array of pointers to type char. Now look at Listing 15.5, which is an example of using an array of pointers.
Listing 15.5. Initializing and using an array of pointers to type char.1: /* Initializing an array of pointers to type char. */
2:
3: #include <stdio.h>
4:
5: main()
6: {
7: char *message[8] = { "Four", "score", "and", "seven",
8: "years", "ago,", "our", "forefathers" };
9: int count;
10:
11: for (count = 0; count < 8; count++)
12: printf("%s ", message[count]);
13: printf("\n");
14: return(0);
15: }
Four score and seven years ago, our forefathers ANALYSIS: This program declares an array of eight pointers to type char and initializes them to point to eight strings (lines 7 and 8). It then uses a for loop on lines 11 and 12 to display each element of the array on-screen. You probably can see how manipulating the array of pointers is easier than manipulating the strings themselves. This advantage is obvious in more complicated programs, such as the one presented later in this chapter. As you'll see in that program, the advantage is greatest when you're using functions. It's much easier to pass an array of pointers to a function than to pass several strings. This can be illustrated by rewriting the program in Listing 15.5 so that it uses a function to display the strings. The modified program is shown in Listing 15.6.
Listing 15.6. Passing an array of pointers to a function.1: /* Passing an array of pointers to a function. */
2:
3: #include <stdio.h>
4:
5: void print_strings(char *p[], int n);
6:
7: main()
8: {
9: char *message[8] = { "Four", "score", "and", "seven",
10: "years", "ago,", "our", "forefathers" };
11:
12: print_strings(message, 8);
13: return(0);
14: }
15:
16: void print_strings(char *p[], int n)
17: {
18: int count;
19:
20: for (count = 0; count < n; count++)
21: printf("%s ", p[count]);
22: printf("\n");
23: }
Four score and seven years ago, our forefathers ANALYSIS: Looking at line 16, you see that the function print_strings() takes two arguments. One is an array of pointers to type char, and the other is the number of elements in the array. Thus, print_strings() could be used to print the strings pointed to by any array of pointers. You might remember that, in the section on pointers to pointers, you were told that you would see a demonstration later. Well, you've just seen it. Listing 15.6 declared an array of pointers, and the name of the array is a pointer to its first element. When you pass that array to a function, you're passing a pointer (the array name) to a pointer (the first array element).
An ExampleNow it's time for a more complicated example. Listing 15.7 uses many of the programming skills you've learned, including arrays of pointers. This program accepts lines of input from the keyboard, allocating space for each line as it is entered and keeping track of the lines by means of an array of pointers to type char. When you signal the end of an entry by entering a blank line, the program sorts the strings alphabetically and displays them on-screen. If you were writing this program from scratch, you would approach the design of this program from a structured programming perspective. First, make a list of the things the program must do:
This list suggests that the program should have at least three functions: one to accept input, one to sort the lines, and one to display the lines. Now you can design each function independently. What do you need the input function--called get_lines()--to do? Again, make a list:
Now think about the second function, the one that sorts the lines. It could be called sort(). (Really original, right?) The sort technique used is a simple, brute-force method that compares adjacent strings and swaps them if the second string is less than the first string. More exactly, the function compares the two strings whose pointers are adjacent in the array of pointers and swaps the two pointers if necessary. To be sure that the sorting is complete, you must go through the array from start to finish, comparing each pair of strings and swapping if necessary. For an array of n elements, you must go through the array n-1 times. Why is this necessary? Each time you go through the array, a given element can be shifted by, at most, one position. For example, if the string that should be first is actually in the last position, the first pass through the array moves it to the next-to-last position, the second pass through the array moves it up one more position, and so on. It requires n-1 passes to move it to the first position, where it belongs. Note that this is a very inefficient and inelegant sorting method. However, it's easy to implement and understand, and it's more than adequate for the short lists that the sample program sorts. The final function displays the sorted lines on-screen. It is, in effect, already written in List- ing 15.6, and it requires only minor modification for use in Listing 15.7.
Listing 15.7. A program that reads lines of text from the keyboard, sorts them alphabetically, and displays the sorted list.1: /* Inputs a list of strings from the keyboard, sorts them, */
2: /* and then displays them on the screen. */
3: #include <stdlib.h>
4: #include <stdio.h>
5: #include <string.h>
6:
7: #define MAXLINES 25
8:
9: int get_lines(char *lines[]);
10: void sort(char *p[], int n);
11: void print_strings(char *p[], int n);
12:
13: char *lines[MAXLINES];
14:
15: main()
16: {
17: int number_of_lines;
18:
19: /* Read in the lines from the keyboard. */
20:
21: number_of_lines = get_lines(lines);
22:
23: if ( number_of_lines < 0 )
24: {
25: puts(" Memory allocation error");
26: exit(-1);
27: }
28:
29: sort(lines, number_of_lines);
30: print_strings(lines, number_of_lines);
31: return(0);
32: }
33:
34: int get_lines(char *lines[])
35: {
36: int n = 0;
37: char buffer[80]; /* Temporary storage for each line. */
38:
39: puts("Enter one line at time; enter a blank when done.");
40:
41: while ((n < MAXLINES) && (gets(buffer) != 0) &&
42: (buffer[0] != `\0'))
43: {
44: if ((lines[n] = (char *)malloc(strlen(buffer)+1)) == NULL)
45: return -1;
46: strcpy( lines[n++], buffer );
47: }
48: return n;
49:
50: } /* End of get_lines() */
51:
52: void sort(char *p[], int n)
53: {
54: int a, b;
55: char *x;
56:
57: for (a = 1; a < n; a++)
58: {
59: for (b = 0; b < n-1; b++)
60: {
61: if (strcmp(p[b], p[b+1]) > 0)
62: {
63: x = p[b];
64: p[b] = p[b+1];
65: p[b+1] = x;
66: }
67: }
68: }
69: }
70:
71: void print_strings(char *p[], int n)
72: {
73: int count;
74:
75: for (count = 0; count < n; count++)
76: printf("%s\n ", p[count]);
77: }
Enter one line at time; enter a blank when done.
dog
apple
zoo
program
merry
apple
dog
merry
program
zoo
ANALYSIS: It will be worthwhile for you to examine some of the details of this program. Several new library functions are used for various types of string manipulation. They are explained briefly here and in more detail on Day 17, "Manipulating Strings." The header file STRING.H must be included in a program that uses these functions. In the get_lines() function, input is controlled by the while statement on lines 41 and 42, which read as follows (condensed here onto one line):
while ((n < MAXLINES) && (gets(buffer) != 0) && (buffer[0] != `\0')) The condition tested by the while has three parts. The first part, n < MAXLINES, ensures that the maximum number of lines has not been input yet. The second part, gets(buffer) != 0, calls the gets() library function to read a line from the keyboard into buffer and verifies that end-of-file or some other error has not occurred. The third part, buffer[0] != `\0', verifies that the first character of the line just input is not the null character, which would signal that a blank line had been entered. If any of these three conditions isn't satisfied, the while loop terminates, and execution returns to the calling program, with the number of lines entered as the return value. If all three conditions are satisfied, the following if statement on line 44 is executed:
if ((lines[n] = (char *)malloc(strlen(buffer)+1)) == NULL) This statement calls malloc() to allocate space for the string that was just input. The strlen() function returns the length of the string passed as an argument; the value is incremented by 1 so that malloc() allocates space for the string plus its terminating null character. The library function malloc(), you might remember, returns a pointer. The statement assigns the value of the pointer returned by malloc() to the corresponding element of the array of pointers. If malloc() returns NULL, the if loop returns execution to the calling program with a return value of -1. The code in main() tests the return value of get_lines() and checks whether a value less than 0 is returned; lines 23 through 27 report a memory allocation error and terminate the program. If the memory allocation was successful, the program uses the strcpy() function on line 46 to copy the string from the temporary storage location buffer to the storage space just allocated by malloc(). The while loop then repeats, getting another line of input. Once execution returns from get_lines() to main(), the following has been accomplished (assuming that a memory allocation error didn't occur):
Now it's time to sort. Remember, you're not actually going to move the strings around, only the order of the pointers in the array lines[]. Look at the code in the function sort(). It contains one for loop nested inside another (lines 57 through 68). The outer loop executes number_of_lines - 1 times. Each time the outer loop executes, the inner loop steps through the array of pointers, comparing (string n) with (string n+1) for n = 0 to n = number_of_lines - 1. The comparison is performed by the library function strcmp() on line 61, which is passed pointers to two strings. The function strcmp() returns one of the following:
In the program, a return value from strcmp() that is greater than zero means that the first string is "greater than" the second string, and they must be swapped (that is, their pointers in lines[] must be swapped). This is done using a temporary variable x. Lines 63 through 65 perform the swap. When program execution returns from sort(), the pointers in lines[] are ordered properly: A pointer to the "lowest" string is in lines[0], a pointer to the "next-lowest" is in lines[1], and so on. Suppose, for example, that you entered the following five lines, in this order:
dog apple zoo program merry The situation before calling sort() is illustrated in Figure 15.5, and the situation after the return from sort() is illustrated in Figure 15.6. Figure 15.5. Before sorting, the pointers are in the same order in which the strings were entered. Figure 15.6. After sorting, the pointers are ordered according to the alphabetical order of the strings. Finally, the program calls the function print_strings() to display the sorted list of strings on-screen. This function should be familiar to you from previous examples in this chapter. The program in Listing 15.7 is the most complex you have yet encountered in this book. It uses many of the C programming techniques that were covered in previous chapters. With the aid of the preceding explanation, you should be able to follow the program's operation and understand each step. If you find areas that are unclear to you, review the related sections of this book until you understand.
Pointers to FunctionsPointers to functions provide another way of calling functions. "Hold on," you might be thinking. "How can you have a pointer to a function? Doesn't a pointer hold the address where a variable is stored?" Well, yes and no. It's true that a pointer holds an address, but it doesn't have to be the address where a variable is stored. When your program runs, the code for each function is loaded into memory starting at a specific address. A pointer to a function holds the starting address of a function--its entry point. Why use a pointer to a function? As I mentioned earlier, it provides a more flexible way of calling a function. It lets the program choose from among several functions, selecting the one that is appropriate for the current circumstances.
Declaring a Pointer to a FunctionLike other pointers, you must declare a pointer to a function. The general form of the declaration is as follows:
type (*ptr_to_func)(parameter_list); This statement declares ptr_to_func as a pointer to a function that returns type and is passed the parameters in parameter_list. Here are some more concrete examples:
int (*func1)(int x); void (*func2)(double y, double z); char (*func3)(char *p[]); void (*func4)(); The first line declares func1 as a pointer to a function that takes one type int argument and returns a type int. The second line declares func2 as a pointer to a function that takes two type double arguments and has a void return type (no return value). The third line declares func3 as a pointer to a function that takes an array of pointers to type char as its argument and returns a type char. The final line declares func4 as a pointer to a function that doesn't take any arguments and has a void return type. Why do you need parentheses around the pointer name? Why can't you write, for the first example:
int *func1(int x); The reason has to do with the precedence of the indirection operator, *. It has a relatively low precedence, lower than the parentheses surrounding the parameter list. The declaration just given, without the first set of parentheses, declares func1 as a function that returns a pointer to type int. (Functions that return pointers are covered on Day 18, "Getting More from Functions.") When you declare a pointer to a function, always remember to include a set of parentheses around the pointer name and indirection operator, or you will get into trouble.
Initializing and Using a Pointer to a FunctionA pointer to a function must not only be declared, but also initialized to point to something. That "something" is, of course, a function. There's nothing special about a function that gets pointed to. The only requirement is that its return type and parameter list match the return type and parameter list of the pointer declaration. For example, the following code declares and defines a function and a pointer to that function:
float square(float x); /* The function prototype. */
float (*p)(float x); /* The pointer declaration. */
float square(float x) /* The function definition. */
{
return x * x;
}
Because the function square() and the pointer p have the same parameter and return types, you can initialize p to point to square as follows:
p = square; Then you can call the function using the pointer as follows:
answer = p(x); It's that simple. For a real example, compile and run Listing 15.8, which declares and initializes a pointer to a function and then calls the function twice, using the function name the first time and the pointer the second time. Both calls produce the same result.
Listing 15.8. Using a pointer to a function to call the function.1: /* Demonstration of declaring and using a pointer to a function.*/
2:
3: #include <stdio.h>
4:
5: /* The function prototype. */
6:
7: double square(double x);
8:
9: /* The pointer declaration. */
10:
11: double (*p)(double x);
12:
13: main()
14: {
15: /* Initialize p to point to square(). */
16:
17: p = square;
18:
19: /* Call square() two ways. */
20: printf("%f %f\n", square(6.6), p(6.6));
21: return(0);
22: }
23:
24: double square(double x)
25: {
26: return x * x;
27: }
43.559999 43.559999
Line 7 declares the function square(), and line 11 declares the pointer p to a function containing a double argument and returning a double value, matching the declaration of square(). Line 17 sets the pointer p equal to square. Notice that parentheses aren't used with square or p. Line 20 prints the return values from calls to square() and p(). A function name without parentheses is a pointer to the function (sounds similar to the situation with arrays, doesn't it?). What's the point of declaring and using a separate pointer to the function? Well, the function name itself is a pointer constant and can't be changed (again, a parallel to arrays). A pointer variable, in contrast, can be changed. Specifically, it can be made to point to different functions as the need arises. Listing 15.9 calls a function, passing it an integer argument. Depending on the value of the argument, the function initializes a pointer to point to one of three other functions and then uses the pointer to call the corresponding function. Each of these three functions displays a specific message on-screen.
Listing 15.9. Using a pointer to a function to call different functions depending on program circumstances.1: /* Using a pointer to call different functions. */
2:
3: #include <stdio.h>
4:
5: /* The function prototypes. */
6:
7: void func1(int x);
8: void one(void);
9: void two(void);
10: void other(void);
11:
12: main()
13: {
14: int a;
15:
16: for (;;)
17: {
18: puts("\nEnter an integer between 1 and 10, 0 to exit: ");
19: scanf("%d", &a);
20:
21: if (a == 0)
22: break;
23: func1(a);
24: }
25: return(0);
26: }
27:
28: void func1(int x)
29: {
30: /* The pointer to function. */
31:
32: void (*ptr)(void);
33:
34: if (x == 1)
35: ptr = one;
36: else if (x == 2)
37: ptr = two;
38: else
39: ptr = other;
40:
41: ptr();
42: }
43:
44: void one(void)
45: {
46: puts("You entered 1.");
47: }
48:
49: void two(void)
50: {
51: puts("You entered 2.");
52: }
53:
54: void other(void)
55: {
56: puts("You entered something other than 1 or 2.");
57: }
Enter an integer between 1 and 10, 0 to exit:
2
You entered 2.
Enter an integer between 1 and 10, 0 to exit:
9
You entered something other than 1 or 2.
Enter an integer between 1 and 10, 0 to exit:
0
ANALYSIS: This program employs an infinite loop starting on line 16 to continue execution until a value of 0 is entered. When a nonzero value is entered, it's passed to func1(). Note that line 32, in func1(), contains a declaration for a pointer ptr to a function. Being declared within a function makes ptr local to func1(), which is appropriate because no other part of the program needs access to it. func1() then uses this value to set ptr equal to the appropriate function (lines 34 through 39). Line 41 then makes a single call to ptr(), which calls the appropriate function. Of course, this program is for illustration purposes only. You could have easily accomplished the same result without using a pointer to a function. Now you can learn another way to use pointers to call different functions: passing the pointer as an argument to a function. Listing 15.10 is a revision of Listing 15.9.
Listing 15.10. Passing a pointer to a function as an argument.1: /* Passing a pointer to a function as an argument. */
2:
3: #include <stdio.h>
4:
5: /* The function prototypes. The function func1() takes as */
6: /* its one argument a pointer to a function that takes no */
7: /* arguments and has no return value. */
8:
9: void func1(void (*p)(void));
10: void one(void);
11: void two(void);
12: void other(void);
13:
14: main()
15: {
16: /* The pointer to a function. */
18: void (*ptr)(void);
19: int a;
20:
21: for (;;)
22: {
23: puts("\nEnter an integer between 1 and 10, 0 to exit: ");
24: scanf("%d", &a);
25:
26: if (a == 0)
27: break;
28: else if (a == 1)
29: ptr = one;
30: else if (a == 2)
31: ptr = two;
32: else
33: ptr = other;
34: func1(ptr);
35: }
36: return(0);
37: }
38:
39: void func1(void (*p)(void))
40: {
41: p();
42: }
43:
44: void one(void)
45: {
46: puts("You entered 1.");
47: }
48:
49: void two(void)
50: {
51: puts("You entered 2.");
52: }
53:
54: void other(void)
55: {
56: puts("You entered something other than 1 or 2.");
57: }
Enter an integer between 1 and 10, 0 to exit:
2
You entered 2.
Enter an integer between 1 and 10, 0 to exit:
11
You entered something other than 1 or 2.
Enter an integer between 1 and 10, 0 to exit:
0
ANALYSIS: Notice the differences between Listing 15.9 and Listing 15.10. The declaration of the pointer to a function has been moved to line 18 in main(), where it is needed. Code in main() now initializes the pointer to point to the correct function, depending on the value the user entered (lines 26 through 33), and then passes the initialized pointer to func1(). func1() really serves no purpose in Listing 15.10; all it does is call the function pointed to by ptr. Again, this program is for illustration purposes. The same principles can be used in real-world programs, such as the example in the next section. One programming situation in which you might use pointers to functions is when sorting is required. Sometimes you might want different sorting rules used. For example, you might want to sort in alphabetical order one time and in reverse alphabetical order another time. By using pointers to functions, your program can call the correct sorting function. More precisely, it's usually a different comparison function that's called. Look back at Listing 15.7. In the sort() function, the actual sort order is determined by the value returned by the strcmp() library function, which tells the program whether a given string is "less than" or "greater than" another string. What if you wrote two comparison functions--one that sorts alphabetically (where A is less than Z), and another that sorts in reverse alphabetical order (where Z is less than A)? The program can ask the user what order he wants and, by using pointers, the sorting function can call the proper comparison function. Listing 15.11 modifies Listing 15.7 to incorporate this feature.
Listing 15.11. Using pointers to functions to control sort order.1: /* Inputs a list of strings from the keyboard, sorts them */
2: /* in ascending or descending order, and then displays them */
3: /* on the screen. */
4: #include <stdlib.h>
5: #include <stdio.h>
6: #include <string.h>
7:
8: #define MAXLINES 25
9:
10: int get_lines(char *lines[]);
11: void sort(char *p[], int n, int sort_type);
12: void print_strings(char *p[], int n);
13: int alpha(char *p1, char *p2);
14: int reverse(char *p1, char *p2);
15:
16: char *lines[MAXLINES];
17:
18: main()
19: {
20: int number_of_lines, sort_type;
21:
22: /* Read in the lines from the keyboard. */
23:
24: number_of_lines = get_lines(lines);
25:
26: if ( number_of_lines < 0 )
27: {
28: puts("Memory allocation error");
29: exit(-1);
30: }
31:
32: puts("Enter 0 for reverse order sort, 1 for alphabetical:" );
33: scanf("%d", &sort_type);
34:
35: sort(lines, number_of_lines, sort_type);
36: print_strings(lines, number_of_lines);
37: return(0);
38: }
39:
40: int get_lines(char *lines[])
41: {
42: int n = 0;
43: char buffer[80]; /* Temporary storage for each line. */
44:
45: puts("Enter one line at time; enter a blank when done.");
46:
47: while (n < MAXLINES && gets(buffer) != 0 && buffer[0] != `\0')
48: {
49: if ((lines[n] = (char *)malloc(strlen(buffer)+1)) == NULL)
50: return -1;
51: strcpy( lines[n++], buffer );
52: }
53: return n;
54:
55: } /* End of get_lines() */
56:
57: void sort(char *p[], int n, int sort_type)
58: {
59: int a, b;
60: char *x;
61:
62: /* The pointer to function. */
63:
64: int (*compare)(char *s1, char *s2);
65:
66: /* Initialize the pointer to point to the proper comparison */
67: /* function depending on the argument sort_type. */
68:
69: compare = (sort_type) ? reverse : alpha;
70:
71: for (a = 1; a < n; a++)
72: {
73: for (b = 0; b < n-1; b++)
74: {
75: if (compare(p[b], p[b+1]) > 0)
76: {
77: x = p[b];
78: p[b] = p[b+1];
79: p[b+1] = x;
80: }
81: }
82: }
83: } /* end of sort() */
84:
85: void print_strings(char *p[], int n)
86: {
87: int count;
88:
89: for (count = 0; count < n; count++)
90: printf("%s\n ", p[count]);
91: }
92:
93: int alpha(char *p1, char *p2)
94: /* Alphabetical comparison. */
95: {
96: return(strcmp(p2, p1));
97: }
98:
99: int reverse(char *p1, char *p2)
100: /* Reverse alphabetical comparison. */
101: {
102: return(strcmp(p1, p2));
103: }
Enter one line at time; enter a blank when done.
Roses are red
Violets are blue
C has been around,
But it is new to you!
Enter 0 for reverse order sort, 1 for alphabetical:
0
Violets are blue
Roses are red
C has been around,
But it is new to you!
ANALYSIS: Lines 32 and 33 in main() prompt the user for the desired sort order. The value entered is placed in sort_type. This value is passed to the sort() function along with the other information described for Listing 15.7. The sort() function contains a couple of changes. Line 64 declares a pointer to a function called compare() that takes two character pointers (strings) as arguments. Line 69 sets compare() equal to one of the two new functions added to the listing based on the value of sort_type. The two new functions are alpha() and reverse(). alpha() uses the strcmp() library function just as it was used in Listing 15.7; reverse() does not. reverse() switches the parameters passed so that a reverse-order sort is done.
Linked ListsA linked list is a useful method of data storage that can easily be implemented in C. Why are we covering linked lists in a chapter on pointers? Because, as you will soon see, pointers are central to linked lists. There are several kinds of linked lists, including single-linked lists, double-linked lists, and binary trees. Each type is suited for certain types of data storage. The one thing that these lists have in common is that the links between data items are defined by information that is contained in the items themselves, in the form of pointers. This is distinctly different from arrays, in which the links between data items result from the layout and storage of the array. This section explains the most fundamental kind of linked list: the single-linked list (which I refer to as simply a linked list).
Basics of Linked ListsEach data item in a linked list is contained in a structure (you learned about structures on Day 11, "Structures"). The structure contains the data elements needed to hold the data being stored; these depend on the needs of the specific program. In addition, there is one more data element--a pointer. This pointer provides the links in a linked list. Here's a simple example:
struct person {
char name[20];
struct person *next;
};
This code defines a structure named person. For the data, person contains only a 20-element array of characters. You generally wouldn't use a linked list for such simple data, but this will serve for an example. The person structure also contains a pointer to type person--in other words, a pointer to another structure of the same type. This means that each structure of type person can not only contain a chunk of data, but also can point to another person structure. Figure 15.7 shows how this lets the structures be linked together in a list. Figure 15.7. Links in a linked list. Notice that in Figure 15.7, each person structure points to the next person structure. The last person structure doesn't point to anything. The last element in a linked list is identified by the pointer element being assigned the value of NULL.
You have seen how the last link in a linked list is identified. What about the first link? This is identified by a special pointer (not a structure) called the head pointer. The head pointer always points to the first element in the linked list. The first element contains a pointer to the second element, the second element contains a pointer to the third, and so on until you encounter an element whose pointer is NULL. If the entire list is empty (contains no links), the head pointer is set to NULL. Figure 15.8 illustrates the head pointer before the list is started and after the first list element is added. Figure 15.8. A linked list's head pointer.
Working with Linked ListsWhen you're working with a linked list, you can add, delete, or modify elements or links. Modifying an element presents no real challenge; however, adding and deleting elements can. As I stated earlier, elements in a list are connected with pointers. Much of the work of adding and deleting elements consists of manipulating these pointers. Elements can be added to the beginning, middle, or end of a linked list; this determines how the pointers must be changed. Later in this chapter you'll find a simple linked list demonstration, as well as a more complex working program. Before getting into the nitty-gritty of code, however, it's a good idea to examine some of the actions you need to perform with linked lists. For these sections, we will continue using the person structure that was introduced earlier.
PreliminariesBefore you can start a linked list, you need to define the data structure that will be used for the list, and you also need to declare the head pointer. Since the list starts out empty, the head pointer should be initialized to NULL. You will also need an additional pointer to your list structure type for use in adding records (you might need more than one pointer, as you'll soon see). Here's how you do it:
struct person {
char name[20];
struct person *next;
};
struct person *new;
struct person *head;
head = NULL;
Adding an Element to the Beginning of a ListIf the head pointer is NULL, the list is empty, and the new element will be its only member. If the head pointer is not NULL, the list already contains one or more elements. In either case, however, the procedure for adding a new element to the start of the list is the same:
Here is the code to perform this task:
new = (person*)malloc(sizeof(struct person)); new->next = head; head = new
Figure 15.9 illustrates the procedure for adding a new element to an empty list, and Figure 15.10 illustrates adding a new first element to an existing list. Figure 15.9. Adding a new element to an empty linked list. Figure 15.10. Adding a new first element to an existing list. Notice that malloc() is used to allocate the memory for the new element. As each new element is added, only the memory needed for it is allocated. The calloc() function could also be used. You should be aware of the differences between these two functions. The main difference is that calloc() will initialize the new element; malloc() will not.
Adding an Element to the End of the ListTo add an element to the end of a linked list, you need to start at the head pointer and go through the list until you find the last element. After you've found it, follow these steps:
Here is the code:
person *current;
...
current = head;
while (current->next != NULL)
current = current->next;
new = (person*)malloc(sizeof(struct person));
current->next = new;
new->next = NULL;
Figure 15.11 illustrates the procedure for adding a new element to the end of a linked list. Figure 15.11. Adding a new element to the end of a linked list.
|
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}
){kind=link}