Objective: This assignment is designed to analyze and compare a variety of data structures for a set of operations. When choosing an abstract data structure for your programs, you should first determine the operations that must be performed by the structure. When you narrow down the data structures that support the operations needed, you can then determine which structure will allow for optimal performance. We are investigating the performance of these structures.
Problem: Your program, when it is complete, should use the following data structures:
1. Stack (array implementation)
2. Queue (array implementation)
3. Unsorted Linked List
To measure the plausibility and performance of the following operations:
1. Insert a record
2. Update a record
3. Delete a delete
Input: All input for this program should come from an input file of your own making. Your program should allow the user to enter the input file name, so the program can work with any data file of the format given below.
Step #1: Read n, an integer. This tells you how many elements are to be read into your data structure.
Step #2: Read in the n elements. (Insertion)
Each element (one per line) will consist of:
LastNamexxxx FirstNamexxx YearlyIncome
-LastName and FirstName can have up to 12 characters each. Use fixed length strings separated by one space.
-YearlyIncome is float.
-Each record will be inserted in each of the three data structures. While inserting the elements, count how many individual comparisons, moves, and assignments are needed to accomplish the insertion.
Step #3: Print out the following table, which contains the number of comparisons for insertion of each record into each structure. Find the average of each column.
Record Stack Queue Linked List
Step #4: Read m (an integer) (Last names should all be in the data structure)
Execute m commands of the following form:
Update LastName x
where x is a float and indicates that LastName’s yearly income should be changed to x. You are to update LastName’s record in each of the data structures. Your data must match a name in the list.
Step #5: Print out a table with the number of comparisons, moves, and assignments to update each record in the update list for each structure.
Find the average of each column.
Update Table Record Stack Queue Linked List LastName1 LastName2 LastName3 .. LastName m Average
Step #6: Perform steps 4 and 5 again, except this time it is possible that the update list will have LastNames that are not in the data structures. Assume that 50% of the names you try to update are not in the data structure. The point of this exercise is to show how attempting to update values that are not in the list affects the performance of each of the three data structures.
Step #7: Read m (an integer)
Process m instructions of the form on all structures:
Note: LastName may or may not be in the data structure.
Print out a table with the number of comparisons, moves, and assignments to delete each record in the deletion list for each structure.
Find the average of each column.
Delete Table Record Stack Queue Linked List LastName1 LastName2 LastName3 .. LastName Average
Step #8: Print the data in each of the three data structures in order from the beginning of the structure, with one entry per line. Stack LastName FirstLetterOfFirstName YearlyIncome Queue LastName FirstLetterOfFirstName YearlyIncome Linked List LastName FirstLetterOfFirstName YearlyIncome