Assignment #2 This assignment consists of writing, documenting, and submitting two separate, related programs. Instructions for how to name the files, package them, and submit are at the end. NOTE: As...

Assignment #2

This assignment consists of writing, documenting, and submitting two separate, related programs. Instructions for how to name the files, package them, and submit are at the end.

NOTE: As mentioned in class, any output of any program that begins with a pound sign (#) will be ignored. This way you can add debugging information or comments outside of the formatting requirements. You should remove these before you submit but, just in case something slips through, we will recognize it as 'not intended to be part of the output if starts with a #'.)

NOTE: The Canvas Wiki Page referenced in the rubric below can be foundhere (Coding Cannon). Canvas doesn't let us embedded links in the Rubric.

Program 2A: Basic Operations and I/O

Description

Use the basic Node class as described in lecture (and included below):

class Node {   public:     std::string     id ;     Node            *next ;     Node ( std::string id , Node *next=nullptr ) {         this->id = id ;         this->next = next ;     } } ;

To this definition, you are to also add the List class (again this one is the same as discussed in class) with the two operations (constructor and head), and a friend declaration that grants the >> operator protected access to a function outside the namespace defined by List.

class List {   public:   Node  *head ;
List() { head = nullptr ; }
Node  *first() { return head ; }
friend std::istream& operator>> ( std::istream& sin, List &lst ) ; } ;

One list operation which was demonstrated in class was to overload the "cin >> _" operator that reads a list from the standard input (keyboard) and builds the linked list. To this, you are to add a new List operation that overloads the "cout
append()andprepend(); both take an id as argument and add a node to the end or beginning of the list, respectively.

To demonstrate that the code is working, write a C++ main() function that creates a List,reads the initial list from the standard input, prepends the id "HEAD", appends the id "TAIL", and outputs the resulting list to standard output.

Requirements
: In addition to the usual grading rubric below, the assignment will be based on its functional correctness and adherence to the requirements below:

• the linked list declarations must be in a separate header file (list-a.h)


• the methods for <, append,="" and="" prepend="" must="" be="" written="" in="" a="" c++="" source="" file="" (list-a.cpp),="" for="" consistency="" you="" probably="" want="" to="" move="">> operator already defined into list-a.cpp as well


• add some formatting "syntax candy" to the output list; output '[' and ']' at the beginning and end of the list, respectively; also include a ',' between the elements of the list


• at bare minimum, output the node id or follow the example in the sample input/output


• and a C++ driver file that contains the main() function is a third file (hw2-a.cpp)

For reference, the C++ code presented in class for >> and main() are shown below. Note that the header filename should be changed from list.h to list-a.h for this assignment.

#include  #include  #include "list.h" using namespace std ;  // this version of the overloaded operator < reads="" a="" node="" id="" string="" from="" the="" stream="" and="" prepends="" nodes="" to="" the="" list="" istream&="" operator="">> ( istream& sin, List &lst ) {     Node            *tmp ;     std::string     id ;      sin >> id ;     while( sin ) {         tmp = new Node(id,lst.head) ;         lst.head = tmp ;         sin >> id ;     }     return sin ; }  int main ( ) {     List    a_list ;      cin >> a_list ;     cout

Sample Input and Output:

(coming soon)

Program 2B: List In-Place Reversal

Description

Further modify the code in Program 2A to add additional functionality. Start by copying a working version list-a.h to list-b.h and copy list-a.cpp to list-b.cpp. Do not destroy your original work! You must turn in both!

On your new copies of these files, add three more operators to your List class. (Note, we changed the file names but not the class names.)

The first new method: Add the ability to determine if the list is empty with a List method calledis_empty()that returns true if there are no elements on the list.

Second, write areverse()method. The new method as a function member of List that performs alist reversal. If the original list is [ "C", "B", "A" ] then after reversal, the list is ["A", "B", "C"]. Note that no new Nodes a new list are created and no new List is created. Instead, only the links are re-arranged so that when the

The third method to add to Program 2B is called ``has_id'' and this, like is_empty() in 2A, returns a boolean. The one argument to has_id is string andhas_id(s)returns true if a node with id s is found in the list; otherwise it returns false.

Requirements
: In addition to the usual grading rubric, be sure to...

• A general and efficient solution does not require an array or vector; use recursion!


• Create three new methods: is_empty(), reverse(), has_id()

Sample Input and Output:

(coming soon)

Questions:

In the README file, answer the following questions:

1. For Program A, what is the big-oh O() run-time of your append() method?


2. For Program A, what is the big-oh O() run-time of your prepend() method?


3. For Program A, if you were to use prepend() -- like we did in class -- what is the big-oh O() run-time of the cin
   


4. For Program A, if you were to use append() instead of prepend(), what is the big-oh O() run-time of the cin
   


5. Finally, for Program B, what is the space requirement (in big-oh O() notation) in for the loop reversal operation.