Week 01 Lab Exercise

Linked Lists

Objectives

To re-acquaint you with C programming and ADTs
To manipulate a linked list data structure
To learn about COMP2521 programming style
To learn about shell scripts to automate repetitive tasks

Admin

Marks: 5 (see the Assessment section for more details)
Demo: in the Week 01 or Week 02 lab session
Submit: see the Submission section
Deadline to submit to give: 5pm Monday of Week 02
Late penalty: No late submissions

Background

At the end of COMP1511, you dealt with linked lists. Over the break, you haven't forgotten linked lists (have you?), but a bit of revision never hurts, especially when many of the data structures we'll deal with later are based on linked lists. So... on with this simple linked list exercise...

Setting Up

To keep your files manageable, it's worth doing each lab exercise in a separate directory (folder). We suggest creating a subdirectory in your home directory called "COMP2521" or "cs2521", and then creating a subdirectory under that called "labs", and then subdirectories "lab01", "lab02", etc.

Create a directory for this lab, change into it, and run the following command:

unzip /web/cs2521/22T1/labs/week01/downloads/lab.zip

If you're working at home, download lab.zip by clicking on the above link and then run the unzip command on the downloaded file.

In the example interactions, we assume that you are typing at a terminal emulator running a shell, and the shell is giving you a $ prompt. All the text that you type is in monospace bold; and all the text that is printed to you is in monospace.

If you've done the above correctly, you should now have the following files:

Makefile: a set of dependencies used to control compilation
IntList.h: interface definition for the IntList ADT
IntList.c: implementation of the IntList ADT (incomplete)
testIntList.c: a program for testing the IntList ADT
sortIntList.c: a program that uses the IntList ADT to sort a list of numbers

Before you start using these programs, it's worth looking at the code. Are there any constructs that you don't understand? Try to work them out with your lab partner, or ask your tutor.

Once you've understood the programs, the next thing to do is to run the command:

make

Don't worry if you don't understand the Makefile; we'll be taking a closer look at make in lectures. Note: you will need to run make to recompile the program each time you make changes to the code.

The make command will produce messages which show the commands it is running, and will eventually leave two executable files in your working directory (along with some .o files):

testIntList

This is the executable for the testIntList.c program. It reads a sorted list of integers from standard input, then reads another integer and tries to insert it into the list (while keeping the list ordered), and then prints out the resulting list. It doesn't work at the moment because the code to insert the integer is incomplete. Here is an example interaction with the program:

./testIntList
Enter some numbers (must be in ascending order): 2 3 5 7
Enter number to insert: 4
Original list:
2
3
5
7
After inserting 4:
2
3
5
7

Note that the program in its current state does not actually insert the number. Once you've got the program working, it should behave like so:

./testIntList
Enter some numbers (must be in ascending order): 2 3 5 7
Enter number to insert: 4
Original list:
2
3
5
7
After inserting 4:
2
3
4
5
7

sortIntList

This is the executable for the sortIntList.c program. It reads a list of integers (which can be unordered) from standard input, then prints that list, then attempts to make a sorted (in ascending order) copy of the list, and then prints the sorted list. It doesn't work at the moment because the code to produce the sorted list is incomplete. Here is an example interaction with the program (once it is implemented correctly):

./sortIntList -v
3 7 2 5

Original:
3
7
2
5
Sorted:
2
3
5
7

If you omit the -v command-line parameter, the useIntList program will only display the final sorted list.

./sortIntList
3 7 2 5

2
3
5
7

Task 1

Implement the IntListInsertInOrder() function in IntList.c, which takes an IntList and an integer and inserts the integer into the appropriate place in the list, so that the list remains sorted (in ascending order). The function can assume that the given list is sorted (and you don't need to check that it is sorted). The function should accept and insert duplicate values. You'll need to handle a number of different cases, such as: (a) empty list, (b) smallest value, (c) largest value, (d) value somewhere in the middle. Discuss with your classmates and propose test cases that test these and any other cases that you can think of.

When you think you're done, use the make command to compile the testIntList program, and then run it to test your code. Run it multiple times to test different cases. For example, does it work when the original list is empty? (To test for an empty list, just press enter when you are prompted for the list.)

Here's an example test run:

./testIntList
Enter some numbers (must be in ascending order): 2 3 5
Enter number to insert: 4
Original list:
2
3
5
After inserting 4:
2
3
4
5

It's possible that you inserted the number in the right place, but didn't maintain the list correctly, as the IntListRep struct in IntList.c contains various fields that must be updated as the list is modified. In this case, the program will print an error message, and you should go back and fix your code.

./testIntList
Enter some numbers (must be in ascending order): 2 3 5
Enter number to insert: 4
Original list:
2
3
5
After inserting 4:
2
3
4
5
error: the list is not consistent - please make sure that you have correctly updated the fields of the IntListRep struct

Try to be thorough with your testing and test as many cases as you can think of, as the next task relies on IntListInsertInOrder working.

Task 2

Implement the IntListSortedCopy() function in IntList.c, which takes an IntList (which may be unordered), and returns an sorted copy of the list. You must use the IntListInsertInOrder() function that you implemented in Task 1.

Recall from Task 1 that IntListInsertInOrder() assumes that the given list is sorted, and ensures that the list remains sorted (if you've implemented it correctly).

When you think you're done, use the make command to recompile the sortIntList program, and then run it to test your code. Here's an example test run:

./sortIntList
3 7 2 5

2
3
5
7

We can make testing much less tedious by placing our test input in files (so that we don't have to manually enter the input each time). Make a directory called tests, and create files containing your test cases in that directory with one test case in each file. A useful naming strategy is to call the test files 01, 02, etc. Here's an example test file which corresponds to the test run above:

Now we can run tests by making the sortIntList program read from our test files instead of from the terminal. For example:

./sortIntList < tests/01
2
3
5
7

To check that your program is producing the correct results (without eyeballing the output every time), you can compare it to the output of a known correct sorting program. For example, you could run both your sortIntList and the built-in sort command on a test case, and then compare the results using the diff command (see man diff for details). If your program is correct, diff will produce no output, as there will be no difference. The following shows an example of how to do this:

sort -n < tests/01 > tests/01.expected          # generate correct result
./sortIntList < tests/01 > tests/01.observed    # generate *your* result
diff -Bb tests/01.expected tests/01.observed    # if correct, no output

If you produce a decent number of tests (10-20), as you should, then running tests one by one using the above is a bit tedious. You could simplify the testing by using this shell script:

#!/bin/sh

for t in 01 02 03 04 05 # TODO: add the rest of your test files to this list
do
	echo === Test $t ===
	sort -n < tests/$t > tests/$t.expected
	./sortIntList < tests/$t > tests/$t.observed 2>&1

	if diff -Bb tests/$t.expected tests/$t.observed > /dev/null 2>&1
	then
		echo "Passed"
	else
		echo "Failed - check differences between tests/$t.expected and tests/$t.observed"
	fi
done

If you put the above in a file called e.g. run_tests, and then run the command:

sh run_tests

The script will run all your test cases and tell you whether each test case passed or failed. If any of your tests fail, then you should go back and fix your code. Note that the issue could be in either IntListInsertInOrder or IntListSortedCopy - you'll need to check both functions.

Submission

You need to submit one file: IntList.c. You can submit via the command line using the give command:

give cs2521 lab01 IntList.c

or you can submit via WebCMS. You can submit multiple times. Only your last submission will be marked. You can check the files you have submitted here.

Assessment

Most of the marks for this lab will come from automarking. To receive the rest of the marks, you must show your work to your tutor during your Week 01 or Week 02 lab session. You will be marked based on the following criteria:

Code correctness (4 marks): These marks will come from automarking. Automarking will be run soon after the submission deadline. After automarking is run you will be able to view your results here.
Code style (1 mark): Code with good style will have these qualities: consistent indentation and spacing, no repetition of code, no overly complicated logic, no overly long functions (>30 lines not including comments), correct use of C constructs (such as if statements and while loops), and comments where appropriate. See the style guide.