3.5: Using the Traverse Function for Lists

Sometimes a solution to a new problem can be obtained by modifying a known program that solves a related problem. Also, maintenance or adaptation of programs frequently involves small changes to current programs. Changes are easier, quicker, and more likely to be error-free if exactly that function or task that requires change has been localized as a program function.

Traverse adheres to two important elements of programming style.

1. High-level descriptions and programs should be as independent of the details of data abstraction implementation and of the application as possible.

2. High-level descriptions and programs should be functionally modular so that special lower-level functions or tasks carried out within the high-level description or program may be easily isolated.

To illustrate the use of traverse, and the effect of these principles, this section presents four examples. Although each could be solved in isolation, from scratch, a different approach is taken here. In each case it should be easy to see that traverse may be adapted to provide an almost immediate solution. This will be done by writing specific versions of traverse's functions for each application, so that these functions turn traverse into a solution. This means that it will then do the required task when executed. Of course, the functions, when invoked by traverse, will do exactly what the programmer specifies in their definition.

Example 3.2

A sentence is stored in a list, with each record storing one character. Thus the sentence, THIS SENTENCE HAS EXACTLY 60 CHARACTERS COUNTING BLANKS AND., is stored in a list with 60 records. For simplicity, assume the period character "." does not occur within a sentence (as it does in this one). The task is to write a function to print the length of the sentence. n

The solution can be achieved by traversing the list and counting the number of records. Initialize can set a counter, length, to zero, and process can increment it by 1 each time it is invoked. Finalize can do the printing. The functions are readily defined.

>Comment

initialize(listname,plength)

listpointer listname;

moreparameters *plength;

{

*plength = 0;

}

>Comment

process(listname,recordpointer,plength)

listpointer listname,recordpointer;

moreparameters *plength;

{

(*plength)++;

}

>Comment

finalize(listname,length)

listpointer lastname;

moreparameters length;

{

if(length != 0)

printf ("\n The sentence has length %d \n",length);

else

printf("\n There is no sentence \n");

}

Either anotherrecord and next must be supplied to the programmer, or the details of the list implementation must be specified such that the programmer can write them. The task of the example is then carried out by the invocation traverse (sentence). In this example traverse must be modified to the following function.

#define TRUE 1

#define FALSE 0

typedef int moreparameters;

traverse(listname)

/* Prints the length of the sentence

stored in the list, listname.

*/

listpointer listname;

{

listpointer recordpointer,next();

moreparameters other;

int done;

>Comment

initialize(listname,&other)

recordpointer = listname;

done = FALSE;

while(!done&&anotherrecord(listname,recordpointer))

{

>Comment

process(listname,recordpointer,&other);

recordpointer = next(recordpointer);

}

finalize(listname,other);

}

There are two ways to view traverse. One is as a program that can be used but not modified in any way. This would require that the functions be written as they appear and the type moreparameters be declared prior to traverse. The second is as a program that may be used or changed in any desirable way. In this case, for clarity, the function names can be changed: traverse to countcharacters, initialize to zerocounter, process to incrementcounter, finalize to printcounter, and anotherrecord to anothercharacter, for example. It may be desirable to remove parameters that are not needed. Since listname is not needed by initialize, process, or finalize, and recordpointer is not needed by process they may be omitted from the definitions and invocations of these functions. Other may be changed to length. Finally, done may be eliminated, since it is not needed. Having made this distinction, the programmer is free to take either view, or a view that falls between the two. The one chosen should be clear from the context.

Suppose the sentence were stored in the list with three characters per record instead of just one per record. The solution would require a new version of process to reflect this change, but initialize and finalize remain as is. Next might have to reflect the new record format. The new process is

>Comment

process(listname,recordpointer,plength)

listpointer listname,recordpointer;

moreparameters *plength;

{

listpointer next();

int lastrecord;

char char1(),char2();

lastrecord = !anotherrecord(listname,next(recordpointer));

>Comment

if(!lastrecord)

*plength = *plength + 3;

>Comment

else if(char1(recordpointer) == '.')

(*plength)++;

else if(char2(recordpointer) == '.')

>Comment

*plength = *plength + 2;

else

>Comment

*plength = *plength + 3;

}

where char1 returns a copy of the first character in the record pointed to by its parameters, and char2 returns a copy of the second character in the record pointed to by its parameters. Like next and anotherrecord, they must be supplied, or the programmer must write them given list implementation details.

Finally, suppose the list is implemented as a circular list (Figure 3.10). In circular lists, the null pointer of the last record is replaced by a pointer that points to the first record. To illustrate the difference in the implementations between a standard list and a circular list, the two distinct versions required for anotherrecord are presented.

Figure 3.10 A Circular List

Standard List

anotherrecord(listname,recordpointer)

listpointer listname,recordpointer;

{

listpointer setnull();

>Comment

return(recordpointer != setnull());

}

Circular List

anotherrecord(listname,recordpointer)

listpointer listname,recordpointer;

{

>Comment

return(listname != recordpointer);

}

Actually, the solution is not as general as possible. Suppose the list were implemented using a dummy header record. Then process must recognize when it is processing this record (the first) and not change length, since no characters are stored in the header record. You should modify process to account for this possibility. It is necessary to assume that the header may be distinguished from the other records in some way.

Example 3.3

Earlier in the chapter a way to reverse a list was developed from scratch. We now build a program to reverse a list utilizing traverse. Traverse may be turned into a solution for the list reversal by defining initialize, process, and finalize, as follows:

>Comment

initialize(listname,psave,ppredecessor)

listpointer listname,*psave,*ppredecessor;

{

listpointer setnull();

*psave = setnull();

*ppredecessor = setnull();

}

>Comment

process(plistname,recordpointer,psave,

ppredecessor)

listpointer *plistname,recordpointer,*psave,

*ppredecessor;

{

listpointer setnull();

if(*ppredecessor != setnull())

setlink(*ppredecessor,*psave);

*psave = *ppredecessor;

*ppredecessor = recordpointer:

}

>Comment

finalize(plistname,save,predecessor)

listpointer *plistname,save,predecessor;

{

listpointer setnull();

if(predecessor != setnull())

{

setlink(predecessor,save);

*plistname = predecessor;

}

}

>Comment

traverse(plistname)

/*Reverses the list listname.*/

listpointer *plistname;

{

listpointer recordpointer,*psave,*ppredecessor,next();

initialize(listname,&psave,&ppredecessor);

recordpointer = *plistname;

while(anotherrecord(*plistname,recordpointer))

{

process(*plistname,recordpointer,&psave,&ppredecessor);

recordpointer = next(recordpointer);

}

finalize(&plistname,*psave,*ppredecessor);

}

Notice that the parameter of traverse is now a pointer to the listname. This is necessary since listname may need to be changed by traverse. Here process works on the record preceding the record pointed to by recordpointer, while the original solution worked on the record pointed to by recordpointer. This was necessary because that solution changed recordpointer's link field before updating recordpointer. n

Example 3.4

Insert a new record into a list stocks, which is kept in alphabetical order by name. Assume the data for the new record may be accessed by a function getnextrecord, which returns a pointer to the new record. n

To turn traverse into a solution requires simply that process compare the new record's name field value with that of the current record. If it precedes the current record's name field value, it must be inserted before the current record and done set to true. To make the insertion conveniently, a pointer, predecessor, to the predecessor of the current record will be kept by process and updated each time process is invoked. Initialize must allocate storage for the new record, set its data field values, and set predecessor to null. Assume that a function avail is given, returning a pointer to a storage element that may be used to store the new record. Finalize must insert the new record in the event that the list is null. The solution for these functions follows:

>Comment

initialize(pnewpointer,ppredecessor)

listpointer *pnewpointer,*ppredecessor;

{

listpointer avail(),setnull(),getnextrecord();

*pnewpointer = avail();

setinfo(*pnewpointer,getnextrecord());

*ppredecessor = setnull();

}

where setinfo copies the contents of the record pointed to by its second parameter into the information field of the record pointed to by its first parameter, so it depends on the list implementation details.

>Comment

finalize(plistname,predecessor,newpointer)

listpointer *plistname,predecessor,newpointer;

{

listpointer setnull();

if(*plistname == setnull())

insert(plistname,predecessor,newpointer);

}

>Comment

process(plistname,recordpointer,newpointer,ppredecessor,

pdone)

listpointer *plistname,recordpointer,newpointer,

*ppredecessor;

int *pdone;

{

listpointer setnull(),next();

if(precedes(newpointer,recordpointer))

{

>Comment

insert(plistname,*ppredecessor,newpointer);

*pdone = TRUE;

}

else if(next(recordpointer) == setnull())

{

>Comment

insert(plistname,recordpointer,newpointer);

*pdone = TRUE;

}

>Comment

else

*ppredecessor = recordpointer;

}

where precedes returns true if its first parameter points to a record whose name precedes, in alphabetical order, the name in the record pointed to by its second parameter. To insert a new record, invoke traverse (&stocks). However, traverse must be modified in a way similar to Example 3.2 as follows. A better name for this modified traverse would be orderedinsert, so we use it.

>Comment

orderedinsert(plistname)

/*Inputs and inserts a new record

in the list listname in alphabetical

order.

*/

listpointer *plistname;

{

listpointer recordpointer,newpointer,predecessor,next();

int done;

initialize(&newpointer,&predecessor);

recordpointer = *plistname;

done = FALSE;

while(!done&&anotherrecord(*plistname,recordpointer))

{

process(plistname,recordpointer,newpointer,

&predecessor,&done);

recordpointer = next(recordpointer);

}

finalize(plistname,predecessor,newpointer);

}

Suppose you wanted to insert the new record into a list of stocks kept in order by date bought, instead of by name. Rather than keep another list distinct from stocks, you could add another link field to its records. Call it the datelink field, and assume each record's datelink field points to the correct successor as in Figure 3.11. Stockdate is a new head, pointing to the first record of that list when date bought is used as the criterion for ordering.

Figure 3.11 Two Orders for a List Using Two Heads and Two Link Fields

To solve this problem: 1) define precedes so that it compares dates instead of names; 2) replace each reference in insert to the setlink function by a reference to the setdatebought function and define it to work on the datelink field instead of the link field; and 3) redefine next to return a copy of the datelink field of the record pointed to by its parameter. A call to orderedinsert(&stocksdate) then carries out the task.

Example 3.5

Create a list stocks, to store a portfolio of stock records. n

To solve this problem, assume the data are already stored on some input medium and getnextrecord gives access to each record in turn, as it is invoked. The desired list may be created by traversing the records stored on the input medium. The job of process is to fill in the information field of the storage allocated for the new record, and fill in the link field of the new record with a pointer to storage allocated for the next new record. However, it is assumed that the last input data is a sentinel value that indicates there are no more records. When the sentinel is input, getnextrecord returns a null pointer value. Consequently, process must first check for this case and, when it occurs, simply return after setting done to true and the link field of the predecessor of the new record to null, unless the list is null. If it is null, process must set done to true and listname to null. Initialize must allocate storage for the first record and set listname to it. Finalize is not needed. We have

>Comment

initialize(plistname)

listpointer *plistname;

{

listpointer avail();

*plistname = avail();

}

>Comment

process(plistname,recordpointer,pdone)

listpointer *plistname,recordpointer;

int *pdone;

{

static listpointer predecessor;

listpointer setnull(),avail(),getnextrecord(),

pointer;

pointer = getnextrecord();

if(pointer != SENTINEL)

{

setinfo(recordpointer,pointer);

setlink(recordpointer,avail());

predecessor = recordpointer;

}

>Comment

else if (*plistname != recordpointer)

{

setlink(predecessor,setnull());

*pdone = TRUE;

}

else

{

>Comment

*plistname = setnull();

*pdone = TRUE;

}

}

Invoking a correctly modified traverse(&stocks) creates the list. Notice that this traverse will copy a list whenever getnextrecord obtains its information from the next record of the list to be copied. A better name for this function would be readlist or copylist. At this point you may want to see a complete program that creates the stocks list and also prints it. The program is in Section 3.6.1.

Suppose the records are given in arbitrary order, but the stocks list must be created with the records appearing in alphabetical order. To turn traverse into a solution to this problem, initialize, finalize, and anotherrecord are not needed; neither are the variables recordpointer and other. This problem is solved by the following version of traverse, which we call expand. The name expand was chosen because, when called to work on an existing ordered list, it simply expands the list by adding the new inputs to the list in the proper places. When the call expand(&listname) is made with listname set to null, it creates the ordered list.

>Comment

expand (plistname)

/*Inputs a series of records and

inserts them in alphabetical

order in the ordered list listname.

*/

listpointer *plistname;

{

int done;

done = FALSE;

while(!done)

>Comment

processrecord(plistname,&done);

}

>Comment

processrecord(plistname,pdone)

listpointer *plistname;

int *pdone;

{

listpointer pointer,getnextrecord();

pointer = getnextrecord();

if(pointer != SENTINEL)

>Comment

insertinorder(plistname,pointer);

else

*pdone = TRUE;

}

Notice that expand has no need for the functions initialize, finalize, and anotherrecord, nor for the variables recordpointer and other.

Processrecord must obtain the next input record and insert it in the list at the correct place. It invokes insertinorder, which has the task of creating and inserting the new record into its proper place in listname; pointer points to the record whose content is to be placed in the new record's information field. Insertinorder itself requires a traversal of listname. The version below is a modification of orderedinsert, obtained by adding a second parameter, pointer. Orderedinsert uses getnextrecord to obtain the next input record and then inserts it, while insertinorder is given a pointer to the new record and needs only insert it. The additional task of obtaining the new input record is handled outside of insertinorder. Consequently its process and finalize functions can be used directly in insertinorder. Only its initialize function needs changing, but all are given below for easy reference.

>Comment

insertinorder(plistname,pointer)

/*Inserts the record pointed to by pointer

in the ordered list listname.

*/

listpointer *plistname,pointer;

{

listpointer recordpointer,predecessor,newpointer,

next();

int done;

>Comment

initialize(&newpointer,&predecessor,pointer);

recordpointer = *plistname;

done = FALSE;

while(!done&&anotherrecord(*plistname,

recordpointer))

{

>Comment

process(plistname,recordpointer,newpointer,

&predecessor,&done);

recordpointer = next(recordpointer);

}

>Comment

finalize(plistname,predecessor,pointer);

}

>Comment

initialize(pnewpointer,ppredecessor,pointer)

listpointer *pnewpointer,*ppredecessor,pointer;

{

listpointer setnull(),avail();

*pnewpointer = avail();

setinfo(*pnewpointer,pointer);

*ppredecessor = setnull();

}

>Comment

process(plistname,recordpointer,newpointer,

ppredecessor,pdone)

listpointer *plistname,recordpointer,

newpointer,*ppredecessor;

int *pdone;

{

listpointer setnull(),next();

if(precedes(newpointer,recordpointer))

{

>Comment

insert(plistname,*ppredecessor,newpointer);

*pdone = TRUE;

}

else if(next(recordpointer) == setnull())

{

>Comment

insert(plistname,recordpointer,newpointer);

*pdone = TRUE;

}

else

>Comment

*ppredecessor = recordpointer;

}

>Comment

finalize(plistname,predecessor,newpointer)

listpointer *plistname,predecessor,newpointer;

{

listpointer setnull();

if(*plistname == setnull())

insert(plistname,predecessor,newpointer);

}

3.5.1 Why Traverse Was Useful