Assignment Version 1 Solution

Introduction




For your first programming assignment, you are to build the beginnings of a library of elementary data structures. This initial library will consist of a singly-linked list class (with a tail pointer), a doubly-linked list class (circular or with a tail pointer), a stack class, and a queue class. In addition, the linked list classes will each need to implement a private node class, suitable for that particular type of linked list. The stack class is to be built upon the doubly-linked list class, while the queue class is to be built upon the singly-linked list class. The language of implementation is Portable C99. Each of the four classes need to be implemented in its own module.




The classes need to be generic. That is, the type of the value stored in a node object will not be specified by the any of the classes. The user of your linked list, stack, and queue classes will determine the type of value stored in these data structures.




Specifications




The specifications for your classes can be found here:




singly-linked lists



doubly-linked lists



stacks



queues



You must program these data structures using the style outlined in http://beastie.cs.ua.edu/C-objects.html.




Generic data pointers




Generic values in C are stored in void * pointers. Any data pointer can be stored in a void * pointer with no cast:




void *p = newInteger(5);




Assigning a void pointer to a specific type also does not require a cast:




void *p = newInteger(5);




integer *q = p;




It is a grave error to cast a void * pointer to a type that does not reflect the original value stored in the void * pointer.




Function pointers




You can pass a function to another function in C by using a function pointer. Suppose you wish to pass a function with this signature:




int plus(int,int);




to a function named accumulate, in addition to an array of integers. The signature of accumulate would be:




int accumulate(int *array,int size,int (*combine)(int,int));




That third argument is a function pointer. To derive the proper function pointer type, simply take the signature of the function to be passed and perform the following transformations:




int plus(int,int);
//original signature


int plus(int,int)
//remove the semicolon


int (plus)(int,int)
//wrap the
function
name
in parens
int (*plus)(int,int)
//place an
asterisk
immediately before the function name
int (*combine)(int,int)
//change the name of the
function to the name of the formal parameter



Inside the accumulate function, the combine function pointer can be called like a regular function:




total = combine(total,array[i]);

Programming style




You must implement your data structures in C99. You must follow the C programming style guide for this project:




http://beastie.cs.ua.edu/cs201/cstyle.html.




Makefiles




You should provide a makefile which responds to the commands:




make



make test



make valgrind



make clean



All compilations should proceed cleanly with no warnings or errors at the highest level of error checking (the -Wall and -Wextra options). Failure to compile cleanly will be considered a failed test.




The make command should compile all your modules, if they have not already been compiled. A second call to make in two consecutive calls to make should never result in a module being compiled or linked.




The make test command runs all your tests on your implementations. You should provide sufficient testing, especially testing the boundaries of your data structures. Examples of boundary testing are:




displaying an empty stack



printing the size of an empty stack



having a stack go non-empty, then empty, and then non-empty again



put a large number of values into a stack and then removing most of them



The make valgrind command should run valgrind on all your executables. There should be no memory errors or leaks detected. Failure to properly implement this makefile rule will be considered a failed test. If your executable is named mytest, then your valgrind rule might look like:




valgrind: mytest




valgrind ./mytest




The make clean command should remove all object files and any executables. Failure to remove such files will be considered a failed test




Warnings




Depending on where you develop your code, uninitialized variables may have a tendency to start with a value of zero. Thus, a program with uninitialized variables may work on your system but fail when I run it. I won’t care, as you are mature enough not to have uninitialized variables. You may have other errors as well that do not reveal themselves until run on my system. Again, that’s not my problem.




At any time, you may submit your project to the compile drop box, which will send you a report on how well the compilation went. Use this command to submit to this drop box:




submit cs201 lusth compile




Submissions to the drop box will be automatically compiled, on the order of every 10 minutes.




You can automatically test your programs by submitting them to the test0 dropbox:




submit cs201 lusth test0




This dropbox will run make clean, make, and make test in that order.




You will need a password in order to submit. Do not ask for the password on any public forum.




Documentation




All code you hand in must be attributed to its authors. Comment sparingly but well. Do explain the purpose of your program. Do not explain obvious code. If code is not obvious, consider rewriting the code rather than explaining what is going on through comments.







2
Grading




The output of your programs and modules will be tested using the diff utility. Your ouput and the expected output must match exactly. A single extra space or a space in the wrong place will cause a test to fail, leading to a resubmission with an accompanying deduction.




Submission




To submit assignments, you need to install the submit system.




linux, windows 10 bash



mac instructions



You will hand in (electronically) your code for final testing with the command:




submit cs201 lusth assign0




Make sure you are in the same directory as your makefile when submitting. The submit program will bundle up all the files in your current directory and ship them to me. Thus it is very important that only the source code and any testing files be in your directory. This includes subdirectories as well since all the files in any subdirectories will also be shipped to me. You may submit as many times as you want before the deadline; new submissions replace old submissions. Old submissions are stored and can be used for backup.




You will need a password in order to submit. Do not ask for the password on any public forum.

















































































































































3