You are provided with a data file reporting on top performing schools in Victoria with student results in VCE 2011 (year 12) above 40 marks for certain subjects. In the file, you are given, for each school, a list of scores between 40 and 50 and for each score, a tally of students who received that score. Your first task is to create a linked list of scores and tallies for a given subject for a school.
In the second stage of your assignment, using code developed in stage 1, you will create an linked list of schools containing the school name, number of student results at that school above 40, and a pointer to a separate linked list of scores for each school.
In the third stage of your assignment, you will create a simple hash table. You will organize the list of schools so that you have a separate school list for each letter of the alphabet, and so all schools beginning with ‘A’ are in the A list, all schools beginning with ‘B’ are in the B list etc. You will write a simple hashing formula to decide (based on the first letter of the school name) which list you will store each school in.
In order to test your program at each stage, you will create methods to print out values in your list of scores, your school and your school list. The output will be stored in a file named “StageNNNSXXXXX.out” where XXXXX represents your student number, NNN represents the stage number: One, Two, Three.
A sample of data from the input file “Accounting.txt” is shown below. The first line contains the name of the school and in brackets (), the total number of student scores above 30 for that school. The second line contains the pair of numbers in the format “score: tally;” Scores range from 55 to 31 all on one line. Data is provided for all schools in Victoria with students scoring above 40 in the study in 2011.
Create a list.h file in which you must use the code for list template class as provided in your text in Chapter 3. Understand how this class works by reading Chapter 3.
You will need to add further methods to this that are not in the text. The first two methods will be used in your testing and output, the second two methods will be used to create a list given one of your scoreData objects. These methods are: See image.
Design a ScoreData class. In this class you will have two data items – score and tally. You will need to write methods to overload the operators {= ,<,>,==} for this class as these are assumed in the binary tree class. You will use the list class to create a list of scores and tallys above 40 in a particular subject for a school e.g.
Design a School class. In this class, you will have the name of the school, a subject name, and a linked list of scores above 40 for students in that subject at that school.
In your main class, create a code to build a list of scoreData nodes for any one school, then when you have this working, create a new class School. In the School class, you will have data including: school name, scores, number of students. Write a method to add a score to a school. This addscores method will call the appropriate insert method in the linked list to insert the score. The insert method should insert scores in the correct position (insertion sort) so that the list is always sorted. Also, write a method to print the school details – including name, number of students, subject name and the scores/tally for each.
Test these abstract data types by creating a few made up school entries within your main method, insert test data into the schools and print out the resulting lists. Insert appropriate output messages in your code to test it. Save the output into a file: “StageOneSXXXXX.out” (XXXXX is your student number)
Before moving to stage two, you are asked to consider a linked list and its features. As your data file is already sorted, discuss whether or not you need to use the insertionsort algorithm to create your list. If you did not use insertionsort to create the list initially, then you need to write a separate method to insertinorder into the list later should the need arise. Explain. Provide an algorithmic description for the createlist method to create the list from the original sorted datafile and a separate algorithmic description for insertinorder method which would insert a new score later.
Write your method to insert a score in the correct (sorted) order in the list of scores. Test this code.
You are now asked to use file streams to read your input directly from the input file, so that you can use the abstract data types already defined and store data for 143 schools given in an input file. Create an array list of school objects. Each array entry should point to a school object. Open the given file “Accounting.txt”, read the schools data in for Accounting and create your list of schools.
Most of the stage 2 coding can be in your main program. You will need to create the linked list and read data until end of file. Create the appropriate school objects and insert all the scores for each school. Test stage 2, by writing output to a file. Ensure you have all the data in your output file for each school in the input file.
Save your stage 2 output to the file: “StageTwoSXXXXX.out” (XXXXX is your student number)
In stage 3, you are asked to create a new abstract data type, a school table. In this table (a 2 dimensional array is fine) you have potentially 26 lists, each of which is a linked list of schools . You will have See image.
Write a method to print a schooltable that will print out each school in turn.
In your main method, where you read in the school data, now you need a new calculation to decide on a simple hash value to choose which list, a new school will be added into. Your hash value is based on the first letter of the schoolname. The calculation : (firstletter – ‘A’ ) will give you an integer that you can use as a hash value to direct you to one of the lists. The expression: next = schoollistcount[hash]++ will tell you how many schools are already in that list, and update the count, so you can insert a pointer to your school into the schoollists[hash][next].
Now, you will have a list of school lists, each containing zero or more schools. The lists are sorted alphabetically groups, but within each school list, the ordering is based on the input data. This means that all the schools starting with ‘A’ are in the same list, but within this list, the schools are not sorted by name. They are in fact sorted by highest score (as this is the ordering in the original data input file).
Save your stage 3 output to the file: “StageThreeSXXXXX.out” (XXXXX is your student number)