2.1.5 Variable-Length Records

When the records of a collection are not necessarily of the same length, they are called variable-length records. Looking back at the single-array and the multiarray representations for a collection of records, it is clear that selection of the ith record was possible only under the tacit assumption that the records were all the same length.

Suppose a field is added to carrecord for each previous rentee. Surely some newer cars will have few previous rentees, while older cars will have a long history of rentees. The programmer could decide to represent each car's record by using a single-length record large enough to accommodate the largest possible number of past rentees. This would aid in processing, as uniformity always does, but would waste a great deal of storage if many records actually have short histories.

With variable-length records, shorter records use fewer locations than longer records, as shown in Figure 2.8. Details of the implementation of such a collection of records must somehow specify where one record ends and the next starts. Separators between records would do, or a field associated with each record could give its total length. Using separators, the last element of the storage for a record would contain a special value denoting the end of the record's storage. If associated fields are used, the first storage element of each record would contain the record's length and would allow a determination of the last element of its storage. In either case, the ith record may no longer be selected, because its location cannot be calculated. However, given the position of the ith record, one can calculate the position of the (i + 1)th record.

Figure 2.8 Variable-Length Records Stored in Array A

Assuming the first element of each record contains its length, as in Figure 2.8, the following function accomplishes the traversal. A record of zero length is used as a sentinel to indicate that there are no more records in the array.

#define SENTINEL 0

>Comment

traverse(a)

*/ Traverses an array a */

int a[];

{

int i;

i = 0;

>Comment

while(a[i] != SENTINEL)

{

process(a,i);

i =i+a[i];

}

}

The record array here is simply an array of individual elements. The programmer imposes the record structure. Each field of the record must thus have the same type in C. Process is a function that does whatever processing is called for. Thus, traversal through the records can be used to access the ith record, but this takes time proportional to i.