SECTION M: WALKING A GENERAL LIST

One technique that is helpful for working through the maze of links of a general list is to mark processed nodes, as done in Rvisit (section 7.7). It is convenient to cycle through the paths generated by Link[1] ... Link[n] by making Mark an integer: Mark = 0 for an unprocessed node and Mark = i when the Link[i] path is being traced.

Marking the nodes prevents redundant wandering through the structure but does not provide the retracing of a path needed to return to a branchpoint in the traverse. The retracing can be done by reversing the links and using two pointers, Son and Father to bridge positions that temporarily lack a link between them.

The operation of the pointers is most easily seen when it is applied to a linear list, as shown in Figure M.1, (where NIL links have been left blank for clarity). This scheme can be carried out with the help of a temporary pointer Base:

Figure M.1

If Son .Mark = 0 then process Son and increment Son .Mark to indicate that the link is being followed.

If Son .Mark = 1 then examine Son .Link. If it is NIL then this route cannot be processed further; increment Son .Mark to indicate that Son is completely processed. If Son .Link is not NIL then shift pointers to follow Son .Link, as shown in Figure M.2 .

Figure M.2

If Son .Mark = 2 then the path leaving from Son is completely processed. The pointers are then shifted to retrace the path that led to Son, as illustrated in Figure M.3 .

Figure M.3

This schematic process can be generalized to nodes with n link fields by incrementing the Mark field each time one of the links leading from a node is followed. The retracing path is followed when Mark = n + 1. An abbreviated trace applied to the example of a general list given at the beginning of section 7.7 is shown in Figure M.4 .

Figure M.4

The SUE version of this scheme is:

procedure Visit(p)

Father  NIL

Son  p

repeat

k  Son  .Mark

case of k

0 : PROCESS(Son)

Son  .Mark  Son  .Mark + 1

1 .. n : if Son  .Mark[k] = NIL

then Son  .Mark  Son  .Mark + 1

else Base  Father

Father  Son

Son  Father  .Link[k]

Father  .Link[k]  Base

endif

n + 1 : k  Father  .Mark

Base  Father  .Link[k]

Father  .Link[k]  Son

Son  Father

Father  Base

Son  .Mark  Son  .Mark + 1

endcase

until Father = NIL

end  {Visit

Projects

Projects

Projects for fun; for serious students

PJM.1 Implement and test the general visitation algorithm of this section. One way to create a general list for testing is to first place a sparse number of 1's in an N by N table T, with none on the main diagonal T[k,k]. Create an array of N nodes, each of which has N Link fields. If T[i,j] = 1, then for pointer p to node i, set p .Link[i] to node [j].

PJM.2 A fundamental limitation of this algorithm is that the final value of p .Mark is n + 1, not 0. A change to modular arithmetic for the Mark field causes infinite loops. (Why?) One solution is to add a switch that causes the counting process to work with an initial mark of either 0 or n + 2. If the switch is global, it can be reset on exit from Visit so that it alternates between two values. Incorporate the necessary changes into Visit and run it. Hint: Let k | p .Mark - Switch | and update p .Mark with a displacement that may be 1 depending on Switch.