Question

For this assignment you will be creating a multi-file project in which you implement your own templated linked list and use it to create a simple list of composers. When doing this assignment, take small, incremental steps; trying to complete the lab in one go will make the lab more difficult. This means that any time you finish part of the lab, such as a linked list method, you should immediately test and debug it if necessary. Part 1: Creating your Linked List Create a header file, Node.h, that has a templated class called ‘Node’. This class should be able to hold both a data value and a pointer to another node. Once your node class is complete, create a new header file, LinkedList.h, that has a templated class called ‘LinkedList’. The class should have two member variables: a pointer to the first element of the linked list and a pointer to the last element of the linked list. Additionally, the class will need to have the following methods (do not define them inline). Some methods may only have a few lines while others are more complicated and will require a bit more thought. Make sure you test all cases for each method and appropriately update the pointers to the first and last nodes if needed. 1. LinkedList(); Constructor for linked list. You decide what needs to be done here 2. ~LinkedList(); Destructor for linked list. You decide what needs to be done here 3. void printList() const; Displays all elements in linked list. This is one of the most important methods because it gives you a way to test your code! For example, once you write the append() method, you should test it using printList(). 4. void append(const T data); Adds a node to the end of the list. For example: list = 1 → 2 → 3 list.append(4) list = 1 → 2 → 3 → 4 5. void prepend(const T data); Adds a node to the front of the list. For example: list = 1 → 2 → 3 list.append(0) list = 0 → 1 → 2 → 3 6. bool removeFront(); Removes the front node. For example: list = 1 → 2 → 3 list.removeFront() list = 2 → 3 7. void insert(const T data); Accepts a value and will insert the value into the linked list in the correct order. list = 1 → 2 → 4 list.insert(0) list = 0 → 1 → 2 → 4 list.insert(5) list = 0 → 1 → 2 → 4 → 5 list.insert(3) list = 0 → 1 → 2 → 3 → 4 → 5 8. bool remove(const T data); Accepts a value and will remove the node with that value from the list. Return true if the node was found and removed and return false otherwise. list = 1 → 2 → 3 list.remove(2) //returns true list = 1 → 3 list.remove(2) //returns false list = 1 → 3 9. bool find(const T data); Accepts a value and will search for that value in the linked list. Return true if the value is in the list and false otherwise 10. bool isEmpty() const; Returns true if list is empty and false otherwise 11. T getFirst() const; Returns the value stored in the first node of the list (not a pointer to the node). 12. T getLast() const; Returns the value stored in the last node of the list. For example: list = 1 → 2 → 3 list.getFirst() //returns 1 list.getLast() //return 3 Note: Remember that your linked list needs to have both a pointer to the first node and a pointer to the last node (The book has code for a templated linked list, but it only has a head pointer. You will not be able to directly copy out of the book). Keep this in mind when writing your methods. For example, what is different about the remove() method if we remove a node from the front vs. a node at the end vs. a node in the middle? What about if the list is empty? Part 2: Using your linked list You will now test your linked list by creating a simple list of composers using the input below. composers.txt Ludwig van Beethoven, 1827 Wolfgang Amadeus Mozart, 1791 Johann Sebastian Bach, 1750 Frederic Chopin, 1849 George Frideric Handel, 1759 Franz Liszt, 1886 Johannes Brahms, 1897 Igor Stravinsky, 1971 Pyotr Ilyich Tchaikovsky, 1893 Claude Debussy, 1918 Joseph Haydn, 1809 Gustav Mahler, 1911 Sergei Prokofiev, 1953 Richard Wagner, 1883 Giacomo Puccini, 1924 Felix Mendelssohn, 1847 Aaron Copland, 1990 Franz Schubert, 1828 Giuseppe Verdi, 1901 Maurice Ravel, 1937 Dmitri Shostakovich, 1975 Sergei Rachmaninoff, 1943 Arnold Schoenberg, 1951 George Gershwin, 1937 Robert Schumann, 1856 Leonard Bernstein, 1990 Bela Bartok, 1945 Antonin Dvorak, 1904 Antonio Vivaldi, 1741 Edvard Grieg, 1907 Camille Saint-Saens, 1921 Henry Purcell, 1695 Claudio Monteverdi, 1643 Hector Berlioz, 1869 Each entry in the file consists of two data fields: the composer’s name and the date of death. Instead of creating two separate linked lists, we will take advantage of the fact that our linked list is a template and can hold any generic type. Our generic type will be a new class. First create a new header file, Composer.h; the class should have two member variables to hold the composer’s name and the date of their death. It is up to you to decide what methods to add to the class, but any methods you have must be defined in a separate file: Composer.cpp . You will not need a lot of methods, but keep in mind that some linked list methods may not immediately work with your ‘Composer’ class. You may need to overload some operators. Once your class is complete, created a Linked List of ‘Composer’ objects in main(). Your main() should go through each line in the file, parse the line to create a ‘Composer’ object, and then add the object to the list. When adding an object to the list, it should be inserted in order by the year of death (see sample run); this is something to keep in mind when overloading operators. Now that the list has been populated, you should give the user 4 options: ● search through the linked list by entering the composer’s name. If the composer is found in the list, display a message saying that they are in the list; if the composer is not in the list, display an error message ● remove a composer from the linked list by entering the composer’s name. If the composer is not found, display an error message; otherwise, say that the composer was successfully removed ● display the contents of the list ● exit the program You may not need to use all the methods in your linked list, but still ensure that any unused methods work correctly Remember: Your linked list class is a template and should work with any type. When trying to create a list of ‘Composer’ objects, you may be tempted to go back and change parts of your linked list class so that they work with your ‘Composer’ class, but do not do this! Once you finish your assignment, go back and try to create a linked list of integers. If you find that any methods are not able to work with this list, then you need to go back and generalize your code. Submitting your Assignment In total, you should have 5 files. ● Node.h ● LinkedList.h ● Composer.h ● Composer.cpp ● Main.cpp When you finish your assignment, zip the entire project and upload it to canvas. If you did not use Visual Studio, use the school computers to create a VS project with your code. To zip your project, right click on the folder, click on “Send To”, and then “Compressed (zipped) folder”.

Answer 1

//Node.h

class Node{

public:

int data;

Node *next;

Node(int val){

data = val;

}

};

//LinkedList.h

#include <iostream>

#include "Node.h"

using namespace std;

class LinkedList

{

public:

Node *head;

LinkedList() {}

~LinkedList() {}

void printList()

{

Node *temp = head;

cout << "List = ";

while (temp != NULL)

{

cout << temp->data << " ";

temp = temp->next;

}

cout << endl;

}

void append(int data)

{

Node *temp = head;

while (temp->next != NULL)

{

temp = temp->next;

}

temp->next = new Node(data);

}

void prepend(int data)

{

Node *temp = new Node(data);

temp->next = head;

head = temp;

}

bool removeFront()

{

head = head->next;

}

void insert(int data)

{

Node *temp = head, *prev;

if (head == NULL)

{

head = new Node(data);

head->next = temp;

}

else

{

while (temp != NULL && temp->data < data)

{

prev = temp;

temp = temp->next;

}

if (temp == NULL)

{

prev->next = new Node(data);

}

else

{

Node *n = new Node(data);

n->next = temp;

if (prev == NULL)

{

head = new Node(data);

head->next = temp;

}

else

{

prev->next = n;

}

}

}

}

bool remove(int data)

{

Node *temp = head, *prev;

while (temp->data != data)

{

prev = temp;

temp = temp->next;

}

prev->next = temp->next;

}

bool find(int data)

{

Node *temp = head;

while (temp != NULL)

{

if (temp->data == data)

return true;

temp = temp->next;

}

return false;

}

bool isEmpty()

{

if (head == NULL)

return true;

return false;

}

int getFirst()

{

if (isEmpty())

{

return -1;

}

return head->data;

}

int getLast()

{

if (isEmpty())

{

return -1;

}

Node *temp = head;

while (temp->next != NULL)

{

temp = temp->next;

}

return temp->data;

}

};

//Composer.h

#include<iostream>

using namespace std;

class Composer{

public:

string name;

int data;

Composer *next;

Composer *head;

Composer();

Composer(string, int);

void readFile();

bool insert(string, int);

bool isEmpty();

bool search(string s);

bool remove(string s);

void display();

};

//composer.cpp

#include <fstream>

#include <cstring>

#include <cstdlib>

#include "./Composer.h"

Composer::Composer() {}

Composer::Composer(string n, int d)

{

name = n;

data = d;

}

void Composer::readFile()

{

ifstream file;

file.open("data.txt");

if (file.is_open())

{

string str, name;

int data;

while (!file.eof())

{

getline(file, str);

int len = str.length();

char temp[len];

int i = 0;

while (i < len)

{

temp[i] = str[i];

i++;

}

temp[i] = '\0';

name = strtok(temp, ",");

data = atoi(strtok(NULL, ","));

insert(name, data);

}

}

}

bool Composer::insert(string name, int data)

{

Composer *temp = head, *prev;

if (head == NULL)

{

head = new Composer(name, data);

head->next = temp;

}

else

{

while (temp != NULL && temp->data < data)

{

prev = temp;

temp = temp->next;

}

if (temp == NULL)

{

prev->next = new Composer(name, data);

}

else

{

Composer *n = new Composer(name, data);

n->next = temp;

if (prev == NULL)

{

head = new Composer(name, data);

head->next = temp;

}

else

{

prev->next = n;

}

}

}

}

bool Composer::search(string s)

{

Composer *temp = head;

while (temp != NULL)

{

if (temp->name == s)

{

return true;

}

temp = temp->next;

}

return false;

}

bool Composer::remove(string s)

{

if (isEmpty())

{

return false;

}

Composer *temp = head, *prev;

while (temp != NULL)

{

if (temp->name == s)

{

if(head==temp){

head = head->next;

}

else{

prev->next = temp->next;

}

return true;

}

prev = temp;

temp = temp->next;

}

return false;

}

bool Composer::isEmpty()

{

return head == NULL;

}

void Composer::display()

{

Composer *temp = head;

while (temp != NULL)

{

cout << temp->name << ", " << temp->data << endl;

temp = temp->next;

}

}

//Main.cpp

#include <iostream>

#include <cstring>

#include "./LinkedList.h"

#include "Composer.cpp"

using namespace std;

int main()

{

cout<<"********************** PART-1 ******************"<<endl;

LinkedList *list = new LinkedList();

list->insert(1);

list->insert(2);

list->insert(4);

list->insert(5);

list->insert(3);

list->append(7);

list->prepend(10);

list->removeFront();

list->remove(3);

if(list->find(2))

cout<<"exists"<<endl;

list->printList();

cout<<list->getFirst()<<endl;

cout<<list->getLast()<<endl;

cout<<"********************** PART-2 ******************"<<endl;

Composer *c_list = new Composer();

c_list->readFile();

char choice;

do

{

string search;

cout << "Enter 's' to search, 'r' to remove, 'd' to display 'e' to exit: ";

cin >> choice;

switch (choice)

{

case 's':

{

cout << "Enter a composer's name to search for: ";

getline(cin, search);

getline(cin, search);

if (c_list->search(search))

cout << search << " was found in the list" << endl;

else

cout << search << " was not found in the list" << endl;

break;

}

case 'r':

{

cout << "Enter a composer's name to remove for: ";

getline(cin, search);

getline(cin, search);

if (c_list->remove(search))

cout << search << " was successfully removed from the list" << endl;

else

cout << search << " was not found in the list when attempting to remove" << endl;

break;

}

case 'd':

c_list->display();

break;

case 'e':

return 0;

break;

default:

cout << "Invalid choice";

}

} while (choice != 'e');

return 0;

}