The purpose of this lab is to give you practice with several C constructs, including:
It is also meant to help you review the list data structure. You will be walked through a number of programs where you use an array to store input from a file and then sort input from a file. Then you will write a program that reads students' names and exams scores from a file and stores the students in a linked list in ascending order based on their average exam score.
The ~cs140/www-home/spring-2005/labs/lab1 directory contains the following useful files:
In this part of the lab you will create a file called array_sort.c that reads strings from standard input and sorts them in alphabetical order using a technique called insertion sort. Insertion sort is implemented by searching through a list of sorted strings until you find the proper place to insert the current string. You will be using an array to store your strings so once you find the appropriate location for your string, you will need to move all the remaining strings down one entry in the array. For example, suppose your array currently consists of the following strings:
--- 0 |-|--> alfie 1 |-|--> brad 2 |-|--> peggy 3 |-|--> sue 4 |-|--> zorro 5 |-|--> 6 |-|--> 7 |-|--> ---You now want to insert "nancy" into this list. You can see by visually scanning the array that "nancy" should be placed after "brad" and before "peggy". Hence "nancy" should be inserted at location 2 in the array. In order to do so we must first move "peggy", "sue", and "zorro" down one location. The resulting array will look like:
--- 0 |-|--> alfie 1 |-|--> brad 2 |-|--> 3 |-|--> peggy 4 |-|--> sue 5 |-|--> zorro 6 |-|--> 7 |-|--> ---We can now insert "nancy" into the appropriate location in the array.
You may not assume in advance that there is an upper limit to the number of entries in the array. Hence you will need to start with an array of a certain size and then be prepared to enlarge the array if the input turns out to be bigger than the size of your current array. Since you will need to potentially create larger-sized arrays, you cannot start with a static array. Instead you will need to malloc an array with an arbitrary initial size. For this lab I want that initial size to be 4. If the input exceeds 4 items, then you will need to malloc a new array of size 8 and copy the string pointers from the old array to the new array. You can then safely delete the old array. You will repeat this process of doubling the array each time the array size is exceeded until you have read all the input.
Each time you read a string you should use the insertion sort algorithm described earlier to insert the string into the array. If the string has the same name as one or more existing strings in the array then insert the string after all strings with the same name. If the array is full you should first double the size of the array. Once you have read the input and sorted it, you should print out the input 4 words to a line, with each word occupying 15 spaces and one space between words. All words should be left-justified. You will need to use printf to format your output and scanf to read your input. You may assume that words are at most 15 characters long. For example, if your input is:
nancy joe shirley alfie zorro mark fred richard suethen your output should be:
alfie fred joe mark nancy richard shirley sue zorro
Normally printf right-justifies text but you can cause it to left justify text by putting a minus sign, (-), between the % sign and the size of your field. For example, %-10s will print a left-justified string with 10 spaces.
To make the job of writing your program more manageable, you may want to break it into the following steps:
In this part of the lab you are going to create a file called list_sort.c that reads lines containing a name and a set of exam scores from a file whose name is given on the command line. Your program will insert the lines into a list using insertion sort with the average exam score as a key. If a student has the same average exam score as one or more other students, insert the student after all other students with the same score. Once the input has been read your program will print the names in ascending order based on exam score. For example, if the input is:
mary 85 95 100 fred 67 82 53 joe 91 72 85 barthowlomew 84 58 81then your output should be:
fred 67.33 barthowlomew 74.33 joe 82.67 mary 93.33The program has the following requirements:
You should submit two files named array_sort.c and list_sort.c respectively. If you cannot complete the programs as described then also include a README file that describes what your program is able to accomplish.