Our intention now is to write a general function traverse, to carry out a traversal of a list, given its head, listname. The code for traverse should be independent of the list implementation, as was the code for insertion and deletion. To make traverse independent of the particular application as well, theprocessing to be done on each record will be functionally modularized in a function process. Its details are thus irrelevant; simply invoke process within traverse. However, to do its job, this function may need access to the list head, listname. It will surely need to know what record it is currently to process; recordprinter will be used to point to this record.
Often, the traversal must proceed through all the list records. To allow for the possibility of a partial traversal, however, a variable done can be introduced. Done may be set by process so that the traversal does not continue beyond the current record. Finally, process cannot retain any information between calls unless that information is kept nonlocal to it, is passed as one of its parameters, or is a static variable. So process is given the parameters listname, recordpointer, done, and other. Other denotes those parameters whose values must be preserved between calls to process.
The heart of a traversal is repeated access of the record pointed to by recordpointer, processing of the record, and updating of recordpointer to point to the next record. Clearly, a loop is its main construct. The function for a general traversal of a list is as follows:
Initialize may be used to set the initial value of any parameters that require initialization. Anotherrecord is a function returning true if recordpointer points to the next record to be processed, and returning false if the last record has already been processed. Finalize is used to carry out any tasks required after all list records have been processed?/FONT>for instance, to print an appropriate message.
It is a good idea to check a program for correctness, in lieu of a formal proof, by seeing if it handles all special cases (and the typical case) correctly. You should check traverse in this way for the case of a null list, a one-record list, and a list with more than one record. For example, if the list is null, the while loop is never executed as long as anotherrecord is correct (which is assumed), and the program terminates properly as long as finalize is correct (which is assumed). So traverse does work correctly for the special case of a null list.
traverse(listname)
listpointer listname;
{listpointer recordpointer,next();
moreparameters other;
int done;
initialize(listname,&other);
recordpointer = listname;
done = FALSE;
while(!done&&anotherrecord(listname,
recordpointer))
{process(listname,recordpointer,
&other,&done);
recordpointer =
next(recordpointer);
}
finalize(listname,other);
}