CMPS 12B Data Structures Assignment 2
The purpose of this assignment is to create the functions needed to perform doubly-linked list operations. The assignment will be written in C and you will turn in only the functions required. You will write your own “main” program to test and validate your linked list functions.
In this assignment, write all error messages to stderr instead of stdout. Printf() implicitly writes to standard out. To write to a different file, use the fprintf() function, as shown in this example:
if (ptr == NULL)
fprintf(stderr, ”bad input, null pointer not an acceptable input value\n”);
By default both stdout and stderr go to the console. Use the shell redirect operator to send either stderr or stdout to a file. You can test this by executing your program and redirecting output from stderr to a file using the shell. In example (1), the program listTest is invoked and the stderr output is redirected to the file “errors”, while stdout continues to be sent to the console. Example (2) redirects stdout to the file “output”, but stderr is still sent to the console.
-
(1) % listTest 2> errors
-
(2) % listTest > output
You will create files main.c (for your own use), list.c and list.h.
main.c – contains the tests and is the driver for your list function testing
listUtil.c – contain the printing and traversal routines to help you debug your code [supplied] listUtil.h – function prototypes for utility functions used by main to test your program [supplied] list.c – contain the list manipulation routines
list.h – contains the list node definition and list function prototypes [supplied]
You list.h file should contain this exact structure definition and function prototypes:
typedef struct NodeObj { int value;
struct NodeObj *prev; struct NodeObj *next;
} NodeObj;
NodeObj *create_new_node(int id);
void insert(NodeObj **list_head, NodeObj *to_be_inserted);
void ordered_insert(NodeObj **list_head, NodeObj *to_be_inserted); void delete_all(NodeObj *list_head);
void delete(NodeObj **list_head, NodeObj *to_be_deleted);
1
Your list.h file should also contain the function prototypes exactly as specified above. You may not change any of the definitions. If you do, then your code will not compile in the grading test suite and you will receive no credit for the assignment. You need to add comments that describe the contents of list.h.
Each function definition must include a comment block as a header that describes any requirements for using the function, any side effects, return values, any error conditions that can result and how you handle these error conditions. Any preconditions assumed by the function should be documented as well. In addition to the function header, you should include a file header comment block which describes the contents of the file. It is acceptable to use either “/* … */” or “//…” comments for your headers but you must be consistent or you will lose points.
In list.c you will implement the following list manipulation routines: NodeObj * create_new_node (int id);
Allocates the space for a new node and initializes the value field. Returns a pointer the node or NULL if memory allocation failed.
void insert(NodeObj **list_head, NodeObj *to_be_inserted);
Inserts the node at the end of the list.
void ordered_insert(NodeObj **list_head, NodeObj *to_be_inserted);
Inserts a node into the increasing value ordered linked list
void delete_all(NodeObj *list_head);
Removes all the nodes from the list and deallocates the memory allocated to the list.
void delete(NodeObj **list_head, NodeObj *to_be_deleted);
Deleted the node from the list and set the list head to null if the resulting list is empty.
What to turn in
You should turn in (using canvas) a .zip file that contains your Makefile, listUtil.c, listUtil.h, list.h and list.c. Do not turn in any file that contains “main()”. You will need to create your own main.c file that contains the main() function to test your assignment. The file listUtil.c contains the functions that print out the lists to that you use to debug your implementation. The file listUtil.h contains the list utility function prototypes and any other definitions required to use the utility functions. You are responsible for creating your own test cases to exercise the code and verify correct operation yourself; this is part of the assignment. You are not allowed to share test cases with students: You can talk about testing strategies and cases but you must not share code that exercises the list functions.
Your project will be evaluated with the weighting of 70% for code correctness and 30% for programming style, documentation and clarity. Please review the code examples shared from Lecture 4. This is only a starting point. Your file headers must include your name, date, and class information as well. Non- compiling programs will earn 0 points as they are impossible to evaluate. For partial credit, a program must
2
compile and successfully link with our grading environment main.c. Points will be given if some functions work and you follow the guidelines for programming style.
Some advice on getting started
Create your Makefile first. Edit list.h to add comments. Create a list.c file with only the create_new_node() function. Use listUtil.c file with printing functions that you will use to verify your implementation. Comment out any functions in list.h and list.c that you are not implementing yet. Compile a simple test program that only implements create_new_node(). Once you have this working them implement insert(), then delete. The concept here is to keep your code compiling and functioning while you continue to add functionality and test each improvement. Ordered_insert() is the most complex and difficult function, so start with the easy ones first.
3