- In Preparation For Our Up Coming Unit On Trees Where Recursive Functions Are The Only Option We Will Prac Tice Writin 1 (128.07 KiB) Viewed 41 times
In preparation for our up-coming unit on trees, where recursive functions are the only option, we will prac- tice writing recursive functions using node chains. Note that the node ADT is recursively defined, since the next field refers to another node-chain (possibly empty). We are practicing recursion in using a familiar ADT, so that when we change to a new ADT, we will have some experience. Below are three exercises that ask for recursive functions that work on node-chains (not Linked Lists). You MUST implement them using the node ADT, and you MUST use recursion (even though there are other ways). We will impose very strict rules on implementing these functions which will hopefully show you new ways to think about recursion. For one of the
questions you are not allowed to use any data collections (lists, stacks, queues). Instead, re- cursively pass any needed information as arguments. Do not add any extra parameters. None are needed. You will implement the following three functions: (a) to_string(node_chain): For this function, you are going to re-implement the to_string() operation from Assignment 5 using recursion. Recall, the function does not do any console output. It should return a string that represents the node-chain (e.g. [1] * -]-->[ 2 | * -]-->[ 31/ ]). Addi- tionally, for a completely empty chain, the to_string() should return the string EMPTY. To test this function, create the following test cases: An empty chain. • A chain with one node. • A chain with several nodes. (b) copy (node_chain): A new node-chain is created, with the same values, in the same order, but it's a separate distinct chain. Adding or removing something from the copy must not affect the original chain. Your function should copy the node chain, and return the reference to the first node in the new chain. To test this function, create the following test cases: • An empty chain. • A chain with one node. • A chain with one several nodes. Be sure to check that you have two distinct chains with the same values! Note: Only a shallow clone is required; if data stored in the original node chain is mutable, it does not also need to be copied.
(c) replace(node_chain, target, replacement): Replace every occurrence of the data target in node_chain with replacement. Your function should return the reference to the first node in the chain. To test this function, create the following test cases: • An empty chain. • A chain with no replacements A chain with several replacements. What to Hand In • A Python program named a8q3.py containing your recursive functions for to_string().copy ().replace(). • A Python script named a8q3_testing.py: include the cases above and tests you consider important Be sure to include your name, NSID. student number, course number and laboratory section at the top of all documents. Evaluation • (3 marks each) Your to_string(). copy (), replace() functions are recursive, and correctly implement the intended behaviour. . (3 marks) You implemented the test cases given above.
class node(object): def __init__(self, data, next=None): Create a new node for the given data. Pre-conditions: data: Any data value to be stored in the node next: Another node (or None, by default) self.__data = data self.__next = next def get_data(self): Retrieve the contents of the data field. Return the data value stored previously in the node return self.__data def get next(self): Retrieve the contents of the next field. Return the value stored previously in the next field return self.__next def...set_data(self.val): Set the contents of the data field to val. Pre-conditions: val: a data value to be stored Post-conditions: stores a new data value, replacing existing value Return none self.__data = val def set next selfval): IT IF II Set the contents of the next field to val. Pre-conditions: val: a node, or the value None Post-conditions: stores a new next value, replacing existing value Return none self.__next = val