|
|
|
|
|
|
|
new dynamic node and copy the component value from the original node into the new node. However, we cannot yet fill in the link member of the new node. We must wait until we have cloned the second node so that we can store its address into the link member of the first node. Likewise, the cloning of the second node cannot complete until we have finished cloning the third node. Eventually, we clone the last node of the original list and set the link member of the cloned node to NULL. At this point, the last node returns its address to the next-to-last node, which stores the address into its link member. The next-to-last node returns its address to the node before it, and so forth. The process completes when the first node returns its address to the first (nonrecursive) call, yielding an external pointer to the new linked list. |
|
|
|
|
|
|
|
|
PtrToClone (In: fromPtr) // Recursive algorithm Out: Function value |
|
|
|
|
|
|
|
|
IF fromPtr is NULL
Return NULL
ELSE
Set toPtr = new NodeType
Set toPtr->component = fromPtr->component
Set toPtr->link = PtrToClone(fromPtr->link)
Return toPtr |
|
|
|
|
|
|
|
|
|
Like the solution to the Towers of Hanoi problem, this looks too simple; yet, it is the algorithm. Because the actual parameter that is passed to each recursive call is fromPtr->link, the number of nodes left in the original list gets smaller with each call. The base case occurs when the pointer into the original list becomes NULL. Below is the C++ function that implements the algorithm. |
|
|
|
|
|
|
|
|
NodePtr PtrToClone( /* in */ NodePtr fromPtr )
// Precondition:
// fromPtr points to a list node (or == NULL)
// Postcondition:
// IF fromPtr != NULL
// A clone of the entire sublist starting with *fromPtr
// is on the free store
// && Function value == pointer to front of this sublist
// ELSE
// Function value == NULL
{
NodePtr toPtr; // Pointer to newly created node |
|
|
|
|
|