C++

Overview

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.

File name: composers.txt

link list:

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 composers 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 composers 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 composers 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 composers 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.

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.

------------------------------------------------------------------------------------------------------------------------------------------------------------------

Sample Run:

Enter 's' to search, 'r' to remove, 'd' to display, or 'e' to exit: d

Claudio Monteverdi - 1643

Henry Purcell - 1695

Antonio Vivaldi - 1741

Johann Sebastian Bach - 1750

George Frideric Handel - 1759

nn - 1856 Hector Berlioz - 1869

Richard Wagner - 1883

Franz Liszt - 1886

Pyotr Ilyich Tchaikovsky - 1893

Johannes Brahms - 1897

Giuseppe Verdi - 1901

Antonin Dvorak - 1904

Edvard Grieg - 1907

Gustav Mahler - 1911

Claude Debussy - 1918

Camille Saint-Saens - 1921 ( This will be removed)

Giacomo Puccini - 1924

George Gershwin - 1937

Maurice Ravel - 1937

Sergei Rachmaninoff - 1943

Bela Bartok - 1945

Arnold Schoenberg - 1951

Sergei Prokofiev - 1953

Igor Stravinsky - 1971

Dmitri Shostakovich - 1975

Leonard Bernstein - 1990

Aaron Copland - 1990

Enter 's' to search, 'r' to remove, 'd' to display, or 'e' to exit: s

Enter a composer's name to search for: Franz Liszt

Franz Liszt was found in the list

Enter 's' to search, 'r' to remove, 'd' to display, or 'e' to exit: s

Enter a composer's name to search for: Hanz Zimmer

Hanz Zimmer was not found in the list

Enter 's' to search, 'r' to remove, 'd' to display, or 'e' to exit: r

Enter a composer's name to remove: Camille Saint-Saens

Camille Saint-Saens was successfully removed from the list

Enter 's' to search, 'r' to remove, 'd' to display, or 'e' to exit: r

Enter a composer's name to remove: CPE Bach

CPE Bach was not found in the list when attempting to remove

Enter 's' to search, 'r' to remove, 'd' to display, or 'e' to exit: d

Claudio Monteverdi - 1643

Henry Purcell - 1695

Antonio Vivaldi - 1741

Johann Sebastian Bach - 1750

George Frideric Handel - 1759

Wolfgang Amadeus Mozart - 1791

Joseph Haydn - 1809

Ludwig van Beethoven - 1827

Franz Schubert - 1828

Felix Mendelssohn - 1847

Frederic Chopin - 1849

Robert Schumann - 1856

Hector Berlioz - 1869

Richard Wagner - 1883

ebussy - 1918

Giacomo Puccini - 1924

George Gershwin - 1937

Maurice Ravel - 1937

Sergei Rachmaninoff - 1943

Bela Bartok - 1945

Arnold Schoenberg - 1951

Sergei Prokofiev - 1953

Igor Stravinsky - 1971

Dmitri Shostakovich - 1975

Leonard Bernstein - 1990

Aaron Copland - 1990

Enter 's' to search, 'r' to remove, 'd' to display, or 'e' to exit: e

Press any key to continue . . .

------------------------------------------------------------------------------------------------------------------------------------------------------