CS19 Fall 2016
Assignment 5 (Care of Magical Creatures)
Computer game programs are full of monsters, but what happens to them when the game is over? What is a discarded (o)rc, (C)entaur, or (T)roll to do? You are the newly hired Chief Technology Wizard for the Monster Protection and Imaginary Creature Tracking (MPICT) organization. You have been tasked with coding a singly linked list data structure to track the creatures under the care of the society. Since not all creatures get along, during the day the monsters are divided into two different outdoor areas. At night the monsters are all kept together indoors. (Yes, even the Vampires!)
Define a class called MonsterList that implements a Singly-Linked List (by serving as the "list class" as described durring lecture) that stores MonsterNodes (your "link node class.") a MonsterNode has a pointer named "next" and a char named "id". Valid ids are an upper or lowercase letter. Due to the Regulation of Magical Creatures Act, you are not allowed to use a string to store the id. Your MonsterList class must support at a minimum, the following functions:
- A constructor that initializes the list to empty
- A public function named int getPopulation() that returns the length (number of MonsterNodes) of the list.
- A public function named void insertMonster(char) that receives a character, and inserts that character (if it is a legal id) into a new MonsterNode at the start of the list. If the id is invalid, this function should do nothing.
- A public function named void printList() that prints the size of the list in parenthesis, followed by a space seperated list of the characters in the list, all on one line of text.
- A function named int removeMonsterType(char) that takes a character, does nothing (unless you've implemented the extra credit—see below), and returns zero.
- A function named void merge(MonsterList &, MonsterList &) that takes two MonsterLists by reference as parameters. This function will remove all of the MonsterNodes from the two parameter lists and place them (alternating nodes from the two lists -- so the first node from the first parameter list, then the first node from the second parameter list, then the second node from the first parameter list and so on.) into the MonsterList on which the function is invoked. This function may not create or dispose of any nodes (or indirectly cause that to happen) instead it must move the already existing MonsterNodes from a list to another list. In the case that the target/third list has initial data or in the "self assignment" case, your merge function should do nothing.
- Other functions as needed.
- Remember that list traversals take time—do your best to minimize the number of traversals needed in your functions/program!
Main and program data files
Write a main function that reads its input from STDIN. Your proram will read in zero or more lines of input. Every line of input will contain a '0' or a '1', followed by a single lowercase or uppercase letter, followed by exactly one of the following two strings: "add" or "remove" (see the example input file provided.)
Your main function should create three MonsterLists. Your program will input a list of creatures, storing each one in either one of the first two lists (depending on the initial integer being a '0' or a '1'.) if the action is "add." (note that entries of either case can go in either list.) If the action is "remove" then you will call the removeMonsterType function on the appropraite list. (Note that this function will do nothing unless you have implemented the extra credit—see below.) After you have completed processing all of the input, show the contents of the first two lists. Next, call merge on the third list with the first two lists as parameters. The original two lists should both be empty at this point, and the third list should should contain every node that originated from either of the other two. Finally, show the contents of all three lists. See the sample runs for example output. Please format your output in exactly the same manner as the sample output to facilitate the evaluation of your program. (Change the first two lines of output to contain your information.)
What to "Turn-In"
Since this is a multi-file project, I will collect the directory 19-5 and all of its contents. You are required to ensure that only the necessary project files and your optional readme.txt file are present. Please don't include other code files or subdirectories.
[steveh@pengo CS19]$ cat inputTest 0 A add 1 a add 0 B add 1 b add 0 A add 1 c add 0 C add 0 A remove 0 A add [steveh@pengo CS19]$
[steveh@pengo MonsterList]$ ./p5 < inputTest CS19 MonsterList Sample Solution Steve J. Hodges firstname.lastname@example.org After reading all input... list 0:(5)A C A B A list 1:(3)c b a After merge... list 0:(0) list 1:(0) combined list:(8)A c C b A a B A [steveh@pengo MonsterList]$
Output with Extra Credit
[steveh@pengo MonsterList]$ ./p5 < inputTest CS19 MonsterList Sample Solution Steve J. Hodges email@example.com After reading all input... list 0:(3)A C B list 1:(3)c b a After merge... list 0:(0) list 1:(0) combined list:(6)A c C b B a [steveh@pengo MonsterList]$
This is a tricky assignment, in particular, the merge function is more difficult than functions you have coded previously. Make sure that the rest of the program is coded and throughly tested before you begin to code merge. You will also want to plan the merge function on paper first. Make sure to allow plenty of time for testing/debugging merge. My usual tips (make sure that your project is always compiling, only add new code to a program that is already compiling/tested, give yourself plenty of time to finish the assignment, being careful with references etc.) also apply!
For extra credit, you may code the removeMonsterType function accoring to the following specification. Note that this is extra credit, not alternative credit. You will receive no points for attempting the extra credit if your other functions are not working properly. Do not attempt the extra credit until after you have throughly tested and verified your program. Completion of the extra credit is worth up to twenty extra points, depending on the efficency and correctness of your code.
Alter the removeMonsterType(char) so that it properly deletes from the list all nodes that match the parameter character in a case-insensitive manner. (So a parameter of 'a' would result in the removal of all nodes with an id of 'A' and all nodes with an id of 'a'.) If the parameter is not a valid letter, this function should do nothing, and then return zero. This function then returns a count of the number of nodes that were deleted.