6.2.1 An Iterative Function

We will now develop a program traverse to traverse a list-structure ls. In applying the definition it became clear that such a traversal may be described by the following algorithm.

1. Initialize the current record.

2. Initialize the stack of postponed obligations to "empty."

3. While there is a current record or a postponed obligation,

if there is a current record, then

a. process the current record, and

b. update the current record to the next record to be processed

else

c. remove the top obligation from the stack and update the current record to it.

To update the current record, the loop task 3b needs to be specified in greater detail. If the record just processed was simple, then the next record to be processed is the successor of the current record. Otherwise梚f the record just processed was complex梚ts successor record represents a postponed obligation that must be placed on the stack. In that case the next record to be processed is the first record on the current record's sublist. This gives a refinement for task 3b that is incorporated in the revised algorithm.

1. Initialize the current record.

2. Initialize the stack of postponed obligations to "empty."

3. While there is a current record or a postponed obligation,

if there is a current record, then

a. process the current record, and

b. if the current record is complex, then

i. save an obligation to its successor record on the stack

ii. update the current record to the first record on its sublist,

else

update the current record to its successor record

else

c. remove the top obligation from the stack and update the current record to it.

A variable (call it ptr) is needed to contain a pointer to the current record. The stack can be treated as a data abstraction with the usual operations set-stack, empty, push, and pop as was done in Chapters 4 and 5. The details for implementing the stack are built into the routines implementing these operations.

Assume that during the traverse each record is processed by calling a routine process. It will clearly need the pointer to the record to be processed, ptr. It will also need access to the list name ls . For example, if its task involves deleting the first record of ls, then it must be able to change the contents of ls. To treat the list-structure as a data abstraction, we need the basic functions complex, next, and sublist, each with ptr as a parameter. Complex returns a value true if the record to which ptr points is complex, the value false otherwise. Next and sublist return, respectively, a copy of the link and sublist field value of the record pointed to by ptr.

A more detailed refinement of the algorithm can now be written.

1. Set ptr to ls

2. Setstack(s)

3. While ptr is not null or not empty(s)

if ptr is not null, then

a. Process(ls,ptr)

b. If complex(ptr), then

i. Push(next(ptr),s)

ii. Set ptr to sublist(ptr)

else

Set ptr to next(ptr)

else

c. Pop(s,ptr)

Notice that if all records of ls are simple, then tasks (i), (ii), and (c) will never be invoked. This procedure is then essentially the same as the list traversal of Chapter 3, as it should be. As written, it does not provide for partial traversal (done is not involved in the loop control) but could be easily modified when necessary.

Traverse may be implemented as in the following iterative (nonrecursive) function. This implementation uses data abstraction and has been written using functional modularly.

Nonrecursive Version

traverse (pls)

/* Accesses and processes each record

of the list-structure ls.

*/

liststructurepointer *pls;

{

liststructurepointer ptr,null,setnull(),next(),sublist();

>Comment

stack s;

null = setnull();

>Comment

ptr = *pls;

>Comment

setstack(&s);

>Comment

while((ptr ! = null) | | (!empty(&s)))

>Comment

if(ptr ! = null)

{

>Comment

process (pls, ptr);

>Comment

if (complex(ptr))

{

>Comment

push next(ptr),&s);

ptr = sublist(ptr);

}

else

>Comment

ptr = next(ptr);

}

else

>Comment

pop(&s,&ptr);

}

It is important to see that the program is functionally modular and independent of the implementation of the data abstractions to which it refers. Data abstractions for the stack with its operations, and for the list-structure and its operations (which must include complex, next, sublist, and setnull) are needed in order to use traverse. The programmer must either be given these or else must write them.