Linked lists
This is a project to get you familiarized with the tools we will make use of this semester.
You will write a C program, along with associated Makefile, that inserts and deletes strings to a linked list. The insert will keep the linked list in alphabetical order.
The file linkedlist.c will have the linked list code. The main routine will be in the file ll-main.c. The file linkedlist.h will describe the functions and data types shared between linkedlist.c and ll-main.c. The program ll-main will take instructions from standard-in to insert and remove strings, as well as print and destroy the linked list, and will make the necessary calls into linkedlist.c to carry out the operation.
The output that ll-main will generate will be compared against a standard output to see if the program is working correctly. For this reason, it is important to adhere closely to the input/output formats.
The Makefile
The Makefile provided is pretty much what you will need. You might add to it if you wish, but it has the important "make ; make test" targets that I or the grader will need to build and run your project. There is also a "make clean" target. This target is more important than you might think.
I want only the source material checked in. Make clean defines what are the source materials and what are derived materials. Make clean will leave only the source materials, and this way I know what those are. Typically they are .c's, .h's, the Makefile, test case files, and perhaps some notes to the grader.There is also a submit target. Don't take that too seriously, as it omits the svn add's you will need to do, and I hope you don't wait until you are done to submit your code. What that target reminds you is that I would like a -m notation when you do submit for a grade. What this is about is that you might continue to develop after submission and I can ignore those "improvements" until you are ready to make them officially part of an improved submission.
The main program
The main program, ll-test.c includes the use of fgets, the decoding of the input
commands, as well as a demonstration of the use of getopt. The getopt demonstrated
provides for a single command line switch, -d n, where n is a positive integer, and
will turn on debugging. This is not particularly necessary, but later on I will encourage
the use of getopt as a way of helping code development. So I am introducing it right now.
The code demonstrates also the use of a global, g_debug. The global is
set by the command line switch. It can be used in ll-test.c and also in linkedlist.c,
where it is shared.
The prefix g_ lets all users of g_debug know it's a global.
This is a common technique among programmers.
Linkedlist.h and the data structure
Also provided is a pretty complete linkedlist.h, which names and gives the arguments for the linked list functions. Also just a bit of code in linkedlist.c.
Note that I am suggesting a doubly-linked list, with a next and prev pointer. The results are what count, so if you wish to use a singly linked list, you can. If you have done singly-linked lists but not a doubly-linked list, this might be an excuse to try one.
I am using the technique of a dummy element at the start of the linked list. An empty list in fact contains one element, although it is hidden from the user of the API. You may have been introduced to this technique elsewhere. It allows that even an empty list is of the same type as a non-empty list, and simplifies the logic of transitioning from an empty to non-empty list.
Note also the use of strdup to create a private data object for the linked list. This is a conservative choice. If I did not use strdup it might be possible for the string to be modified, and the modification would apply to the string in the linked list. To prevent this, I copy the string; and when freeing the node in the linked list, I free this string as well.
Without dup'ing the string, there would also be a question of "who frees?" the string. The string cannot be freed until both the linked list and the caller that presented the string have both surrendered references to the string. There is no way that these two codes can coordinate those events. The only option that I can see is that the caller to the insert itself make a copy, and in giving over the string to the linked list, it essentially gives over the responsibility to free to the string. That might save a strdup, but often it just moves the strdup from the linked list code to the caller code.
Test driven development
The ll-main.c and the Makefile show the use of the file test1.tdd to propose a series of actions on the linked list, and the output is captured and compared against what should be output. Test driven development is an idea from Agile Development, also known as extreme programming. For what we need from this, and also applicable to more traditional development methodologies, is that there is a way to automate the test cases.
The simple system, as you can figure out by looking at the templates, is the input file will have a single character to signify the operation, followed without space by any data. The output will be the single character repeated, a colon, and then a standard format for the response to the operation.
Read over the code in the templates to figure out the specifics.
Author: Burton Rosenberg
Created: September 7, 2014
Last Update: September 7, 2014