Begin this lab by copying the main.cc from my directory to your own lab6 directory.
cp ~jdolan/cs2401/labs/lab7/main.cc .
Remember that the dot at the end is part of the command.
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 is a number between 1 and 500, entered by the user. The function then 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 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.)
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 to your lab instructor, according to his instructions.
