CS140 -- Lab 1

Purpose

The purpose of this lab is to give you practice with several C constructs, including:

  1. C-style strings
  2. structs
  3. printf
  4. malloc and pointers

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.

Where To Find Things

The ~cs140/www-home/spring-2005/labs/lab1 directory contains the following useful files:

  1. Two executable files, array_sort and list_sort. If you have any questions about what your output should look like or how your program should behave, try executing these programs.

  2. Two sample files, named names_file and grades_file, that you can use to test your array_sort program and list_sort program respectively. These files are only samples and do not exhaust all the cases we might test. Therefore you should also come up with your own test files.

  3. A makefile that you can use to create your executables. If you copy this makefile to your directory you can compile your .c files into executables by typing make.

Array Sort

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
sue
then 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:

  1. Write a program that reads the input into an array and doubles the size of the array as necessary. You may want to start by reading integers rather than strings. Do not worry about sorting the input at this step. Print out the input 4 words to a line when you have finished reading the input.

  2. Modify the program so that it uses insertion sort to insert the integers into the array as it reads each integer.

  3. Modify the program so that it reads strings rather than integers. Remember that you have to use strcmp rather than the < operator to compare two strings. Also remember to modify your printf statement to handle strings.
At each step save your program so that if you cannot get the next step to work you can hand in the program from the previous step to receive partial credit. Feel free to skip any of these steps if you are comfortable skipping them. For example, if you are comfortable with strings then you can skip using integers.

List Sort

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 81
then your output should be: 
fred             67.33
barthowlomew     74.33
joe              82.67
mary             93.33
The program has the following requirements:

  1. You must use a struct to store the nodes of the list. Each node should contain a pointer to the next item on the list, a name, and an average exam score.
  2. Each input line will consist of a name of no more than 15 characters and three integer exam scores.
  3. Each line of output should contain a left-justified name that occupies 15 spaces, then a space, and finally a right-justified floating point exam average that contains 3 leading digits, a decimal point, and two fractional digits for a total of 6 spaces.
  4. You may assume that the input is correct so your program does not have to do any error-checking.

What to Submit

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.