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 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 sll class
For your singly linked list class, the header file, sll.h, should look something like:
#ifndef __SLL_INCLUDED__
#define __SLL_INCLUDED__
typedef struct sllnode
{
void *value;
struct sllnode *next;
} sllnode;
typedef struct sll
{
sllnode *head;
sllnode *tail;
int size;
void (*display)(FILE *,void *);
} sll;
extern sll *newSLL(void (*d)(FILE *,void *)); //constructor
extern void insertSLL(sll *items,int index,void *value); //stores a generic value
extern void *removeSLL(sll *items,int index); //returns a generic value
extern void unionSLL(sll *recipient,sll *donor); //merge two lists into one
extern void *getSLL(sll *items,int index); //get the value at the index
extern int sizeSLL(sll *items);
extern void displaySLL(FILE *,sll *items);
#endif
You may define other methods in addition to those shown. The union method must run in constant time. The insert and remove methods must use zero-based indexing and must run in constant time for insertions at the end of the list and at a constant distance from the front. Deletions from a constant distance from the front must also run in constant time. The header file contains the function signatures of your public methods while the code module, sll.c, contains their implemen- tations. The newSLL method is passed a function that knows how to display the generic value stored in a linked list node. That
function is stored in the display field of the sll object:
sll *newSLL(void (*d)(FILE *,void *)) //d is the display function
{
sll *items = malloc(sizeof(sll));
if (items == 0)
{
fprintf(stderr,"out of memory");
exit(-1);
}
items->head = 0;
items->tail = 0;
items->size = 0;
items->display = d;
return items;
}
Here is a sample testing program that uses the displayInteger function found in the integer class. Note how it is passed to the
newSLL constructor.
#include
#include
#include "sll.h"
#include "integer.h"
static void showItems(sll *items)
{
printf("The items are ");
displaySLL(stdout,items);
printf(".\n");
}
int main(int argc,char **argv)
{
sll *items = newSLL(displayInteger);
showItems(items);
insertSLL(items,0,newInteger(3)); //insert at front
insertSLL(items,sizeSLL(items),newInteger(2)); //insert at back
insertSLL(items,1,newInteger(1)); //insert at middle
showItems(items);
printf("The value ");
displayInteger(stdout,removeSLL(items,0)); //remove from front
printf(" was removed.\n");
showItems(items);
int x = getInteger((integer *) getSLL(items,0)); //get the first item
printf("The first item is %d.\n",x);
return 0;
}
The output of this program should be:
The items are [].
The items are [3,1,2].
The value 3 was removed.
The items are [1,2].
The first item is 1.
The unionSLL method takes two lists and moves all the items in the donor list to the recipient list. If the recipient list has
the items [3,4,5] and the donor list has the items [1,2], then after the union the donor list will be empty and recipient list
will have the items [3,4,5,1,2].
The getSLL method retrieves the generic value at index given as the second argument.
You may download the integer class with these commands:
wget beastie.cs.ua.edu/cs201/integer/integer.c
wget beastie.cs.ua.edu/cs201/integer/integer.h
wget beastie.cs.ua.edu/cs201/integer/test-integer.c
The last command retrieves a program for testing the integer class. Compile and run this program with the commands:
gcc -Wall -Wextra test-integer.c integer.c -o test-integer
./test-integer
The superior student will test his or her singly-linked list class with other data types besides integers by implementing such classes as real and string.
The dll class
For your doubly-linked list class, provide (at a minimum) the following methods:
dll *newDLL(void (*d)(FILE *,void *)); //constructor
void insertDLL(dll *items,int index,void *value); //stores a generic value
void *removeDLL(dll *items,int index); //returns a generic value
void unionDLL(dll *recipient,dll *donor); //merge two lists into one
void *getDLL(dll *items,int index); //get the value at the index
int sizeDLL(dll *items);
void displayDLL(FILE *,dll *items);
Your methods must run with the same time bound as the analogous singly-linked list methods, with the additional requirement that deletions a constant distance from the end of the list must run in constant time. Indices are zero-based.
A testing program for this class would look similar to the one for the singly-linked list class. The items in a doubly-linked list are displayed exactly the same as shown in the singly-linked list example.
The stack class
For your stack class, provide implementations of the following methods:
stack *newStack(void (*d)(FILE *,void *)); //constructor
void push(stack *items,void *value); //stores a generic value
void *pop(stack *items); //returns a generic value
void *peekStack(stack *items); //returns a generic value
int sizeStack(stack *items);
void displayStack(FILE *,stack *items);
All operations, except displayStack, must run in constant time.
Here is a sample testing program for the stack class:
#include
#include
#include "stack.h"
#include "integer.h"
static void showStack(stack *s)
{
printf("The stack is ");
displayStack(stdout,s);
printf(".\n");
}
int main(int argc,char **argv)
{
stack *items = newStack(displayInteger);
showStack(items);
push(items,newInteger(3));
push(items,newInteger(2));
showStack(items);
printf("The value ");
displayInteger(stdout,pop(items));
printf(" was popped.\n");
showStack(items);
return 0;
}
The output of this program would be:
The stack is [].
The stack is [2,3].
The value 2 was popped.
The stack is [3].
The queue class
For your queue class, provide implementations of the following methods:
queue *newQueue(void (*d)(FILE *,void *)); //constructor
void enqueue(queue *items,void *value); //stores a generic value
void *dequeue(queue *items); //returns a generic value
void *peekQueue(queue *items); //returns a generic value
int sizeQueue(queue *items);
void displayQueue(FILE *fp,queue *items);
All operations, except displayQueue, must run in constant time.
After enqueueing the values 5, 7, and 13, in that order into an empty queue, the displayQueue method should output the following:
[5,7,13]
with no leading or following spaces or tabs.
Generics 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);
The reverse requires a cast:
void *p = newInteger(5);
integer *q = (integer *) 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 steps:
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 clean
• make test
The make command compiles your program, which should compile cleanly with no warnings or errors at the highest level of error checking (the -Wall and -Wextra option). the make clean command should remove object files and the executable.
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
• having a stack go non-empty, then empty, and then non-empty again
• printing the size of an empty queue
• put a large number of values in a linked-list
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 compiledrop 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 have me test your programs by submitting them to the test dropbox:
submit cs201 lusth test
I run your makefile about once a day. Send me a note if I forget to do it in a reasonable amount of time or you need more
immediate feedback.
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.
Grading
The output of your programs 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. A common mistake is not to end the last line of the output with a newline. This will cause diff to report a difference and the test will fail.
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 the preliminary assessment and 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. I will
deduct points if you submit object files or executables, so be careful. 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.