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.