Pointers in C: Working with Pointers and Structures

You have seen how a pointer can be defined to point to a basic data type, such as an int or a char. But pointers can also be defined to point to structures. In Chapter 9, “Working with Structures,” you defined your date structure as follows:

struct date

{

int month;

int day;

int year;

};

Just as you defined variables to be of type struct date, as in

struct date todaysDate;

so can you define a variable to be a pointer to a struct date variable:

struct date *datePtr;

The variable datePtr, as just defined, then can be used in the expected fashion. For example, you can set it to point to todaysDate with the assignment statement

datePtr = &todaysDate;

After such an assignment has been made, you then can indirectly access any of the mem- bers of the date structure pointed to by datePtr in the following way:

(*datePtr).day = 21;

This statement has the effect of setting the day of the date structure pointed to by datePtr to 21. The parentheses are required because the structure member operator . has higher precedence than the indirection operator *.

To test the value of month stored in the date structure pointed to by datePtr,a statement such as

if ( (*datePtr).month == 12 )

can be used.

Pointers to structures are so often used in C that a special operator exists in the lan- guage. The structure pointer operator ->, which is the dash followed by the greater than sign, permits expressions that would otherwise be written as

(*x).y

to be more clearly expressed  as

x->y

So, the previous if statement can be conveniently written as

if ( datePtr->month == 12 )

Program 9.1, the first program that illustrated structures, was rewritten using the concept of structure pointers, as shown in Program 11.4.

Program 11.4   Using Pointers to Structures

// Program to illustrate structure pointers

#include <stdio.h>

int main (void)

{

struct date

{

int month;

int day;

int year;

};

struct date today, *datePtr;

datePtr = &today;

datePtr->month = 9;

datePtr->day = 25;

datePtr->year = 2004;

printf (“Today’s date is %i/%i/%.2i.\n”,

datePtr->month, datePtr->day, datePtr->year % 100);

return 0;

}

Program 11.4   Output

Today’s date is 9/25/04.

Figure 11.2 depicts how the variables today and datePtr would look after all of the assignment statements from the preceding program have been executed.

Once again, it should be pointed out that there is no real motivation shown here as to why you should even bother using a structure pointer when it seems as though you can get along just fine without it (as you did in Program 9.1).You will discover the motiva- tion shortly.

1. Structures Containing  Pointers

Naturally, a pointer also can be a member of a structure. In the structure definition

struct intPtrs

{

int *p1;

int *p2;

};

a structure called intPtrs is defined to contain two integer pointers, the first one called p1 and the second one p2.You can define a variable of type struct intPtrs in the usual way:

struct intPtrs pointers;

The variable pointers can now be used in the normal fashion, remembering that pointers itself is not a pointer, but a structure variable that has two pointers as its mem- bers.

Program 11.5 shows how the intPtrs structure can be handled in a C program.

Program 11.5   Using Structures Containing  Pointers

// Function to use structures containing pointers

#include <stdio.h>

int main (void)

{

struct intPtrs

{

int *p1;

int *p2;

};

struct intPtrs pointers;

int i1 = 100, i2;

pointers.p1 = &i1;

pointers.p2 = &i2;

*pointers.p2 = -97;

printf (“i1 = %i, *pointers.p1 = %i\n”, i1, *pointers.p1);

printf (“i2 = %i, *pointers.p2 = %i\n”, i2, *pointers.p2);

return 0;

}

Program 11.5   Output

i1 = 100, *pointers.p1 = 100

i2 = -97, *pointers.p2 = -97

After the variables have been defined, the assignment statement

pointers.p1 = &i1;

sets the p1 member of pointers pointing to the integer variable i1, whereas the next statement

pointers.p2 = &i2;

sets the p2 member pointing to i2. Next, –97 is assigned to the variable that is pointed to by pointers.p2. Because you just set this to point to i2, –97 is stored in i2. No parentheses are needed in this assignment statement because, as mentioned previously, the structure member operator . has higher precedence than the indirection operator. Therefore, the pointer is correctly referenced from the structure before the indirection operator is applied. Of course, parentheses could have been used just to play it safe, as at times it can be difficult to try to remember which of two operators has higher prece- dence.

The two printf calls that follow each other in the preceding program verify that the correct assignments were made.

Figure 11.3 has been provided to help you understand the relationship between the variables i1, i2, and pointers after the assignment statements from Program 11.5 have been executed. As you can see in Figure 11.3, the p1 member points to the variable i1, which contains the value 100, whereas the p2 member points to the variable i2, which contains the value –97.

2. Linked Lists

The concepts of pointers to structures and structures containing pointers are very pow- erful ones in C, for they enable you to create sophisticated data structures, such as linked lists, doubly linked lists, and trees.

Suppose you define a structure as follows:

struct entry

{

int         value;

struct entry *next;

};

This defines a structure called entry, which contains two members. The first member of the structure is a simple integer called value. The second member of the structure is a member called next, which is a pointer to an entry structure. Think about this for a moment. Contained inside an entry structure is a pointer to another entry structure. This is a perfectly valid concept in the C language. Now suppose you define two vari- ables to be of type struct entry as follows:

struct entry n1, n2;

You set the next pointer of structure n1 to point to structure n2 by executing the fol- lowing statement:

n1.next = &n2;

This statement effectively makes a link between n1 and n2, as depicted in Figure 11.4.

Assuming a variable n3 were also defined to be of type struct entry, you could add another link with the following statement:

n2.next = &n3;

This resulting chain of linked entries, known more formally  as a linked list, is illustrated in Figure 11.5. Program 11.6 illustrates this linked list.

Program 11.6   Using Linked Lists

// Function to use linked Lists

#include <stdio.h>

int main (void)

{

struct entry

{

int         value;

struct entry *next;

};

struct entry n1, n2, n3;

int        i;

n1.value = 100;

n2.value = 200;

n3.value = 300;

n1.next = &n2;

n2.next = &n3;

i = n1.next->value;

printf (“%i “, i);

printf (“%i\n”, n2.next->value);

return 0;

}

Program 11.6   Output

200 300

The structures n1, n2, and n3 are defined to be of type struct entry, which consists of an integer member called value and a pointer to an entry structure called next. The program then assigns the values 100, 200, and 300 to the value members of n1, n2, and n3, respectively.

The next two statements in the program

n1.next = &n2;

n2.next = &n3;

set up the linked list, with the next member of n1 pointing to n2 and the next member of n2 pointing to n3.

Execution of the statement

i = n1.next->value;

proceeds as follows: The value member of the entry structure pointed to by n1.next is accessed and assigned to the integer variable i. Because you set n1.next to point to n2, the value member of n2 is accessed by this statement. Therefore, this statement has the net result of assigning 200 to i, as verified by the printf call that follows in the pro- gram.You might want to verify that the expression n1.next->value is the correct one to use and not n1.next.value, because the n1.next field contains a pointer to a struc- ture, and not the structure itself. This distinction is important and can quickly lead to programming errors if it is not fully understood.

The structure member operator . and the structure pointer operator -> have the same precedence in the C language. In expressions such as the preceding one, where both operators are used, the operators are evaluated from left to right. Therefore, the expression is evaluated as

i = (n1.next)->value;

which is what was intended.

The second printf call in Program 11.6 displays the value member that is pointed to by n2.next. Because you set n2.next to point to n3, the contents of n3.value are displayed by the program.

As mentioned, the concept of a linked list is a very powerful one in programming. Linked lists greatly simplify operations such as the insertion and removal of elements from large lists of sorted items.

For example, if n1, n2, and n3 are as defined previously, you can easily remove n2 from the list simply by setting the next field of n1 to point to whatever n2 is pointing to:

n1.next = n2.next;

This statement has the effect of copying the pointer contained in n2.next into n1.next, and, because n2.next was set to point to n3, n1.next is now pointing to n3. Furthermore, because n1 no longer points to n2, you have effectively removed it from your list. Figure 11.6 depicts this situation after the preceding statement is executed. Of course, you could have set n1 pointing to n3 directly with the statement

n1.next = &n3;

but this latter statement is not as general because you must know in advance that n2 is pointing to n3.

Inserting an element into a list is just as straightforward.  If you want to insert a struct entry called n2_3 after n2 in the list, you can simply set n2_3.next to point to whatever n2.next was pointing to, and then set n2.next to point to n2_3. So, the sequence of statements

n2_3.next = n2.next;

n2.next = &n2_3;

inserts n2_3 into the list, immediately after entry n2. Note that the sequence of the pre- ceding statements is important because executing the second statement first overwrites the pointer stored in n2.next before it has a chance to be assigned to n2_3.next. The inserted element n2_3 is depicted in Figure 11.7. Notice that n2_3 is not shown between n1 and n3. This is to emphasize that n2_3 can be anywhere in memory and does not have to physically occur after n1 and before n3. This is one of the main motiva-tions for the use of a linked list approach for storing information: Entries of the list do not have to be stored sequentially in memory, as is the case with elements in an array.

Before developing some functions to work with linked lists, two more issues must be discussed. Usually associated with a linked list is at least one pointer to the list. Often, a pointer to the start of the list is kept. So, for your original three-element list, which con- sisted of n1, n2, and n3, you can define a variable called list_pointer and set it to point to the beginning of the list with the statement

struct entry *list_pointer = &n1;

assuming that n1 has been previously defined. A pointer to a list is useful for sequencing through the entries in the list, as you see shortly.

The second issue to be discussed involves the idea of having some way to identify the end of the list. This is needed so that a procedure that searches through the list, for example, can tell when it has reached the final element in the list. By convention, a con- stant value of 0 is used for such a purpose and is known as the null pointer.You can use the null pointer to mark the end of a list by storing this value in the pointer field of the last entry of the list.1

In your three-entry list, you can mark its end by storing the null pointer in n3.next:

n3.next = (struct entry *) 0;

You see in Chapter 13, “The Preprocessor,” how this assignment statement can be made a bit more readable.

The type cast operator is used to cast the constant 0 to the appropriate type (“pointer to struct entry”). It’s not required, but makes the statement more readable.

Figure 11.8 depicts the linked list from Program 11.6, with a struct entry pointer called list_pointer pointing to the start of the list and the n3.next field set to the null pointer.

Program 11.7 incorporates the concepts just described. The program uses a while loop to sequence through the list and display the value member of each entry in the list.

Program 11.7   Traversing a Linked List

// Program to traverse a linked list

#include <stdio.h>

int main (void)

{

struct entry

{

int         value;

struct entry *next;

};

struct entry n1, n2, n3;

struct entry *list_pointer = &n1;

n1.value = 100;

n1.next = &n2;

n2.value = 200;

n2.next = &n3;

n3.value = 300;

n3.next = (struct entry *) 0; // Mark list end with null pointer

while ( list_pointer != (struct entry *) 0 ) {

printf (“%i\n”, list_pointer->value);

list_pointer = list_pointer->next;

}

return 0;

}

Program 11.7   Output

100

200

300

The program defines the variables n1, n2, and n3 and the pointer variable list_pointer, which is initially set to point to n1, the first entry in the list. The next program state- ments link together the three elements of the list, with the next member of n3 set to the null pointer to mark the end of the list.

A while loop is then set up to sequence through each element of the list. This loop is executed as long as the value of list_pointer is not equal to the null pointer. The printf call inside the while loop displays the value member of the entry currently pointed to by list_pointer.

The statement that follows the printf call,

list_pointer = list_pointer->next;

has the effect of taking the pointer from the next member of the structure pointed to by list_pointer and assigning it to list_pointer. So, the first time through the loop, this statement takes the pointer contained in n1.next (remember, list_pointer was initially set pointing to n1) and assigns it to list_pointer. Because this value is not null—it’s a pointer to the entry structure n2—the while loop is repeated.

The second time through, the while loop results in the display of n2.value, which is 200. The next member of n2 is then copied into list_pointer, and because you set this value to point to n3, list_pointer points to n3 by the end of the second pass through the loop.

When the while loop is executed the third time, the printf call displays the value of 300 as contained in n3.value. At that point, list_pointer->next (which is actually n3.next) is copied into list_pointer, and, because you set this member to the null pointer, the while loop terminates after it has been executed three times.

Trace through the operation of the while loop just discussed, using a pencil and paper, if necessary, to keep track of the values of the various variables. Understanding the operation of this loop is the key to your understanding the operation of pointers in C. Incidentally, it should be noted that this same while loop can be used to sequence through the elements of a list of any size, provided the end of the list is marked by the null pointer.

When working with actual linked lists in a program, you will not normally link together list entries that have been explicitly defined like in the program examples in this section.You did that here just to illustrate the mechanics of working with a linked list. In actual practice, you will typically ask the system to give you memory for each new list entry and you will link it into the list while the program is executing. This is done with a mechanism known as dynamic memory allocation, and is covered in Chapter 17.

Source: Kochan Stephen G. (2004), Programming in C: A Complete Introduction to the C Programming Language, Sams; Subsequent edition.

Leave a Reply

Your email address will not be published. Required fields are marked *