2.2.1 Pointers

In C, records can be stored in arrays. They can also be stored in an area of memory called the dynamic memory. Dynamic memory is managed automatically for the programmer, who can request and release storage as needed. Pointers are variables that point to data items. Those that point to array entries, as noted earlier, are called array indexes. Those that point to individual data items, or structures, are called pointer variables. By following a pointer, you can access a record. Sometimes it is necessary to access a record by following a sequence of pointers.

Pointers and pointer variables afford flexibility in structuring data but must be used with great care, since they can introduce subtle errors that cause difficulty in the debugging of a program. The errors are problems that arise when collections of records can expand or contract in unpredictable ways. Storage for such records must be managed carefully.

To understand pointers and pointer variables, it is practical to examine them in a more static context. They are useful even then, in solving problems involving variable-length records and the representation of arrays. A good way to become familiar with the workings of pointers and pointer variables is to solve the following promblem: Is there a way to store n variable-length records in a one-dimensional array so that traversal through the records is possible, and, more important, so that the (i + 1)th one can be selected?

The solution is not difficult conceptually. Suppose a pointer array pa is created, as in Figure 2.9. The information in pa[i] should state where the base, or origin, of the (i + 1)th record is in a. Thus pa [3] is 13, because the fourth record begins in a[13]. One describes this by saying that pa[i] contains a pointer to the (i + 1)th record in a. The variable i can be thought of as pointing indirectly to a record in a; to get to it requires an access to pa along the way.

Recall that records are represented by a sequence of consecutive entries, so pa[i] points to the first entry of the (i + 1)th record, its base. Once the base of a record and its field offsets are known, any field of the record can be selected. This technique of using pointer arrays is an old and very important technique in computer science. This kind of pointer is just an array index; it is also known as a relative pointer, because it indicates the position of the record in relation to the other records within the same array. This is different from the other type of pointer, the pointer variable, which refers to actual memory locations.

Figure 2.9 Pointer Array PA, with Pointers Stored in A

Selecting the (i + 1)th record is now possible by accessing pa[i] and following the pointer found there to the entry of a in which the (i + 1)th record begins. The base of this record has the name a[pa[i]]. Note that selection is being applied first to array pa, and then to array a. Each takes constant time, which is why we say the (i + 1)th record may be selected. It is also easy to traverse through the records using pa, as shown by the following program.

traverse(a,pa,n)

/* Traverses through the n

records stored in a which

are pointed to by indices

stored in the pointer array pa

*/

int a[],pa[],n;

{

int i;

for (i=0; i<n; i++)

process(a,pa,i);

}

Using the pointer array costs additional storage but solves the problem posed for variable-length records. Relative pointers to records stored in an array are easy to use when language typing constraints are not violated.