Coursework: Week 9, Lists
The coursework this week counts 25% towards your credit for the unit. The main purpose is to practice using pointers.
If you are still using Windows, you will be at a big disadvantage because (a) it will be very difficult for you to track down segfaults and (b) your program may work for you, but bugs may show up when we use the advanced debugging options, so you may lose marks.
understand the task and header
Your task is to write a reusable library module for doubly linked lists. You are provided with these files:
list.h file is the API
list.c file has no skeletons
The program does not compile
The list stores items
The header doesn’t say ‘doubly linked’
Camel case is used
The module isn’t thread safe
Modules are a good way of handling pointers
create a skeleton
Your first task is to turn
lists.c into a full skeleton program that compiles. You can do this without fully understanding the assignment.
Define two structures
Define dummy functions
At this point, check that the program compiles.
There are not many programmers who can program with pointers without using pictures. There is usually nothing better than scribbling on paper or a whiteboard to sort out the ideas. Here are some pictures to help with this assignment:
Picture a node
Picture a node more simply
You need an end node
A pre node
understand the tests
The tests are a bit unusual. One reason is that you haven’t been given a skeleton which includes the structures. That means the tests can’t check the structure fields, which could be different for each of you. Instead, they have to be based around calls to the list functions, and nothing else, as if the module were being tested from the outside.
Legality checks are tested
There is a default item
Strings are used to describe lists
The tests are the detailed specifications
The tests have supporting functions
There are preliminary tests
The approach taken here to testing is one I use quite commonly. It has the advantage that the tests don’t depend too heavily on the implementation choices being made, and therefore the tests are easy to maintain when programs are refactored. I hope you think that the tests and testing strategy are well designed. I am trying to illustrate that, in any project, design effort and ingenuity and creativity needs to go into the testing as well as the program.
design the data and functions
Programming with pointers can be difficult, partly because it is impossible to create all the desirable types of test, partly because it is difficult to debug programs when things go wrong, and partly because it can be difficult to maintain an accurate mental model of what is going on. Programmers used to dread segfaults. That’s where the new debugging options come in. If you misuse a pointer, there is a good chance that your program will be stopped, and you will get an error message with a line number to say where the problem is. This has made C a much more tolerable language. It is a pity that the options haven’t fully made it onto Windows yet. Here’s some practical advice:
Keep functions tiny
Keep the code uniform
Avoid multiple arrows
write an extra program
If you do extra work this week, it is recommended that you do something else with pointers, preferably involving trees. Implementing a search tree module, or a tree-based map module, or a linked hash map module (look for descriptions of Java’s
LinkedHashMap class), or writing a Huffman encoding algorithm would be good examples.
The minimum is to submit
lists.c. Marking will not just be by how many tests you pass. Instead, if the tests don’t all pass or the compiler options show problems you haven’t found, I will judge what your program is worth by hand. So it would be quite helpful for you to submit a readme file to explain your ideas. As always, also submit all the source code (including any headers) and a readme for any extra work you have done.