Skip to main content

CS223 Exercises

Section 1.13 Homework 13 -- Recursive Lists

Exercises Exercises

1.

    In a recursive list implementation, the nodes (Rec_node class) are "smart" and "dual-natured".  Each Rec_node considers itself to be the first node of a list consisting of a) itself and b) all the rest of the nodes that follow. As such, Rec_nodes have list functionality (append, retrieve, etc.).
    🔗
    In addition:
    • Rec_node methods are implemented RECURSIVELY whenever possible.
      🔗
    • Rec_nodes store strings as their data.
      🔗
    🔗
    Constructors for the Rec_node class:
    🔗
    // Default constructor creates a Rec_Node with data = "" and rest_ptr = NULL
Rec_node();

// Constructor with 1 or 2 arguments
Rec_node(string val, Rec_node* rest_ptr = NULL);
    Private section for the Rec_node class:
    🔗
    private:

   // Instance variables
   string data;       // value stored in this node
   Rec_node * rest;   // pointer to first node of the rest of this list

   /*
   *  Rec_node assignment operator is disabled by making it private.
   *  DO NOT IMPLEMENT.  DO NOT USE.
   */
   Rec_node& operator=(const Rec_node &other);

  • True.

  • False.

🔗

2.

Implement the append member function for the Rec_node class.
🔗
/*
*  append
*  Postcondition: `val` is the new last item of the list; the list is not
*     changed in any other way.
*
*  Note: MUST be implemented with recursion.
*/
void Rec_node::append(string val)
🔗

3.

Implement the retrieve member function for the Rec_node class.
🔗
/*
*  retrieve
*  Precondition:  0 <= n < length of the list starting from this node
*  Postcondition: string object at index `n` is returned, where indexing
*     is relative to the current node.
*  Example:  myNode.retrieve(0) will return the data in `myNode`, while
*     myNode.retrieve(1) will return the data in the node that immediately
*     follows `myNode`.
*  Note: MUST be implemented with recursion.
*/
string Rec_node::retrieve(int n) const
🔗

4.

Implement the insertAt member function for the Rec_node class.
🔗
/*
*  insertAt
*  Insert a new node containing `val` at index `n` relative to this node.
*  Precondition: 1 <= n <= length
*
*  For example, if n is 1, a new node containing val will be inserted 
*  immediately after this node.
*/
void Rec_node::insertAt(int n, string val)
🔗

5.

Implement the removeFrom member function for the Rec_node class.
🔗
/*
*  removeFrom
*  Delete a node at a given index and return its data.
*  Precondition: 1 <= n < length
*  Postcondition: The list is one node shorter; the node that had index
*     `n` relative to this node is now deleted and its data returned.
*     The list is not changed in any other way.
*
*  Note: Rec_node.removeFrom will NOT handle the case n == 0; it is handled in the List class.
*
*  Note: MUST be implemented with recursion.
*/
string Rec_node::removeFrom(int n)
🔗

6.

Implement the size member function for the Rec_node class.
🔗
/*
*  size
*  Postcondition: Return the number of nodes in the list headed by this node.
*
*  Note: MUST be implemented with recursion.
*/
int Rec_node::size() const
🔗

7.

Implement the equivalence (operator==) and inequivalence (operator!=) non-member functions for the Rec_node class.
🔗
/*
*  operator==
*     The lists headed by n1 and n2 are equivalent if n1 and n2 have the same data and
*     the list at the head of n1's rest is equivalent to the list at the head of n2's rest.      
*     
*  Postcondition: Return true if the lists headed by n1 and n2 are equivalent. 
*
*  Note: MUST be implemented with recursion.
*/
bool operator== (const Rec_node &n1, const Rec_node &n2);


/*
*  operator!=
*     The lists headed by n1 and n2 not equivalent if n1 and n2 have different data or 
*     the list at the head of n1's rest is not equivalent to the list at the head of n2's rest.        
*     
*  Postcondition: Return true if the lists headed by n1 and n2 are not equivalent.
*
*  Note: DO NOT IMPLEMENT WITH RECURSION; implement by calling ==.
*/
bool operator!= (const Rec_node &n1, const Rec_node &n2);
🔗

8.

    The List class for this implementation has a single instance variable, head_ptr, which is a pointer to a Rec_node.
    🔗
    .
    🔗
    private:

   // Instance variables
   Rec_node * head_ptr;   // pointer to head of the list

   /*
   *  List assignment operator is disabled by making it private.
   *  DO NOT IMPLEMENT.  DO NOT USE.
   */
   List& operator=(const List &other);
    Most functions for this List implementation are very straightforward: simply call the corresponding function on the Rec_node being pointed to by head_ptr.  Just be sure to handle the special case when the list is empty.
    🔗
    For reference, here are the getters and setters for the Rec_node class:
    🔗
    // *** Getters and Setters, Defined HERE In-Line *** //      string getData() const { return data; }      Rec_node * getRest() const { return rest; }      void setData(string val) { data = val; }      void setRest(Rec_node * rest_ptr) { rest = rest_ptr; }
    🔗

  • True.

  • False.

🔗

9.

Implement the isEmpty, append , and retrieve member functions for the recursive List class.  The Rec_node::size() method has been disabled.
🔗
/*
*  isEmpty
*   Postcondition: Returns true if this is an empty list; otherwise,
*     returns false.
*/
bool isEmpty() const;


/*
*  append
*   Postcondition: A new item, `val`, is added to the end of the list.
*
*   Note: Do NOT use a for loop or a while loop. Instead, use the recursive
*      nature of of Rec_nodes to accomplish any iteration.
*/
void append(string val);


/*
*  retrieve
*   Precondition: 0 <= n < length of list
*   Postcondition: Item at index `n` (counting from 0 at the head node)
*     is returned.
*
*   Note 1: Do not worry about invalid values for `n`.
*   Note 2: Do NOT use a for loop or a while loop. Instead, use the recursive
*      nature of of Rec_nodes to accomplish any iteration.
*/
string retrieve(int n) const;
🔗

10.

Implement the size function for the recursive List class without using a "for" or a "while" loop.
🔗
/*
*  size
*   Postcondition: Returns the number of items in the list.
*/
int size() const;
🔗

11.

Implement the insertAt and removeFrom member functions for the recursive List class.  The Rec_node::size() method has been disabled.
🔗
/*
*  insertAt
*   Inserts a new item at a given index `n` in the list.
*   Precondition: 0 <= n <= length of this list
*   Postcondition: The length of the list has increased by one.
*   Postcondition: The item at index `n` in the list is now `val`.
*   Postcondition: The relative positions of the previously-existing
*     items are unchanged.
*   
*   Note 1: Do not worry about invalid values for `n`.
*   Note 2: Do NOT use a for loop or a while loop. Instead, use the recursive
*      nature of of Rec_nodes to accomplish any iteration.
*/
void insertAt(int n, string val);


/*
*  removeFrom
*   Delete a node at a given index `n` and return its data.
*   Precondition: 0 <= n < length
*   Postcondition: The list is now one item shorter. The node at position
*     `n` has been deleted.  The relative positions of the other items
*     are unchanged.

*   Note 1: Do not worry about invalid values for `n`.
*   Note 2: Do NOT use a for loop or a while loop. Instead, use the recursive
*      nature of of Rec_nodes to accomplish any iteration.
*/
string removeFrom(int n);
🔗
🔗
You have attempted of activities on this page.
🔗
PrevTopNext