Description
Begin this lab by copying the main.cc from my directory to your own lab3 directory.
cp ~jdolan/cs2401/labs/lab3/main.cc .
Remember that the dot at the end is part of the command. (Or you can download it from Blackboard.)
In this main you will see that I have created a linked list of random numbers. The numbers are 1 to 500, but there are 2000 of them in the list, so obviously there will be duplicates. You can also see that I am timing the code with time. (Although both of my functions are taking less than a second apiece.) Read through the code so that you see what it does.
For this lab you are to implement two functions, and I have given you the prototypes for the functions.
• The first function passes through the linked list and removes all duplicate items. You will need at least two, and most likely three, additional pointers to pull this off. Remember that to remove an item you will need to hold onto the node before the one you remove. Of course when you’re done the total size of the linked list should be <= 500. I have given you a size function so you can check that. You should have the main call the show_list function to print out this newer, smaller list.
• The second function takes the cleaned up list, and a split value, which for us the user will enter from the keyboard, and creates two new lists, one having only numbers greater than the split value and one having only numbers less than the split value. (The split value is not in either list.) The sum of the size of these two lists should be equal to or be one less than the cleaned up list you built with the first function. (The first function alters the original list and this function creates two new lists. Note neither function is ordering the list.)
You should then run a script file by type script output, running the program, and then
ctrl-d. There should be four lists output, as well as reporting on the size of the lists, and the time it has taken each of your functions to run.
Submit your source code and the script file on Blackboard.
