Objectives: Implement a linked list Use structures to create nodes for a linked list Use pointers to manipulate a linked list Problem: Doc Brown has configured the DeLorean to go back to the days of the Roman Empire. Unfortunately, the Roman Empire does not use Arabic numerals which is going to make it difficult for Doc to do the proper calculations he needs to get back home. Before he heads back in time, he wants you to create a Roman numeral converter for him.

Roman numerals are as follows: o 1 = I o 5 = V o 10 = X o 50 = L o 100 = C o 500 = D o 1000 = M Determine if the input given is Roman numeral or Arabic. Convert from given type to the missing type. All numbers will be in the range of 1 4999. Store the file contents in a linked list. o Add the node to the beginning of the list All manipulation of the data will happen in the linked list. o Convert each piece of data to its unlisted counterpart Write the contents of the linked list back to the file at the end of the program. The file may contain invalid data. o If invalid data is identified, ignore the entry in the file. Invalid data: o Arabic numeral outside the given rage. o Invalid characters in Roman numeral. o Invalid characters in Arabic numeral. User will be able to search and sort the data. Use a linear search o Search can be for Arabic or Roman numeral o Do not ask user what type of numeral to search for (-5 points if user is asked) User can type in Arabic or Roman numeral You have to figure out what they typed Implement sorting algorithm of your choice o Sorting algorithm will move nodes (-10 points) o Do not exchange node data o All sorts will sort in ascending order Arabic: smallest to largest number Roman: alphabetical Comment your code generously. Refer to the grading rubric for more details. Use as few variables as possible. Dont waste memory holding a calculation just so you can print it out one time. User Interface and Input: Create a simple menu interface allowing the user to search and sort the data. The menu will consist of 3 options: 1. Search 2. Sort 3. Exit If the user selects the sort option, provide a sub menu: 1. Sort by Roman numeral 2. Sort by Arabic numeral All user input will be valid. Remember that the file input may not be valid. File Structure: The file will contain an unknown quantity of numbers to convert. Each number will be on a separate line. The number will be either Arabic or Roman Each line of the file will have the same format o Roman numeral field 16 characters Fixes the 4888 issue Arabic numeral field 4 characters The last line may or may not have a new line at the end Only one of the fields will hold a value on each line o If a field does not hold a value, it will contain all spaces. o If the Roman numeral field contains a space as the first character, you know that the line contains an Arabic numeral Output: If the user enters the option to search, state whether the item was found or not found ( ) in the console window. If the user enters the option to sort, display the sorted values to the console window. Only display the values for the type of data sorted. For example, if Roman numerals are sorted, only display the Roman numerals in alphabetic order. At the end of the program, write the linked list back to the file used for input.