Programming Assignment #2: Sorted List Solution

In this assignment, you will practice with more complex data structures, as well as practice using function pointers (along with using data pointers as in the last assignment).

Your task is to write a set of types and functions that implement a sorted list. The sorted list will contain opaque objects.  That is, the objects will be given to you as void* pointers.  When a sorted list is first created, the caller will provide you with a pointer to a comparator function and a destruct function.  This comparator function will understand the actual type of the objects to be stored in the sorted  list,  and  given two  objects,  will return an  ordering  of the two  objects.   Subsequently, when new objects are inserted into the list, you will use the given comparator function to insert the new objects such that the list will remain  sorted in descending  order;  that is, objects are ordered from largest (front  of the list) to smallest (end  of the list).  The  destruct function will deallocate the object.

You will also implement an iterator to help users walk through lists.  This  iterator, together with returning pointers to your sorted list objects as void*, will help you practice information hiding. That is, your  implementation is similar  to a Java class, where the users  do not know about the implementation and so cannot access parts of the objects directly.  (In C, there are obviously ways to get around  your hiding; nevertheless, it is good programming practice because it requires effort to violate the hiding.)

 

 

2    Implementation

 

 

Your implementation needs to export the interface given in the attached sorted-list.h file. Specif- ically, you need to implement four functions for creating sorted lists, destroying sorted lists, and inserting and  deleting an object into/from a sorted list.  Your sorted-list data will be of the type void*, so that you can pass any type into data struct. Rather, this is a way in C for you to practice a bit of information hiding.  When  writing your code for the sorted list, you will need to define a type for your sorted list objects.  For example:

 

 

struct  SortedList  {

...

};

typedef  struct  SortedList*  SortedListPtr;

 

 

You should create a pointer to struct  SortedList object in SLCreate().

 

 

SortedListPtr  SLCreate(CompareFuncT  cf,  DestructFuncT  df)  {

SortedListPtr  sl;

 

... /*  do  what  is needed   to  create  the  sorted  list  object.  */

 

return  sl;

}

 

The comparator function must obey the following semantics: return a value less than 1 if the first object is smaller,  0 if the two objects are equal, and a value greater then 1 if the second object is smaller.

You will also need to define a helper iterator type together with three functions for creating sorted list  iterators,  destroying  sorted  list  iterators,  and  obtaining  the objects  in a sorted  list  one at a time. In this assignment, the iterator is just a wrapper  around  a sorted list that is used to help the caller walk through the list.  Again, data is returned as void* to hide your implementation.

One complication  that you must  deal with  is what  happens  if the sorted  list  is modified (e.g.,  a new object inserted or an existing object is removed)  while an iterator is being used.  You should explain how your implementation deals with this complication as a comment in your code.

As always, your code should be well-designed, well-organized,  and well-commented.

 

 

3    What to turn in

 

 

A sorted-list.c file containing all of your data structure code.  You should  also carefully comment all of your code.  Your grade  will be based  on how well your code is working as well as how well written your code is (including  comments) and  how carefully you tested your code.  A main.c  file should including  test cases and code to call the library.

A tarred gzipped file named  pa2.tgz that contains a directory called pa2 with the following files in it:

 

• An sorted-list.h  file containing  the interface  we gave you and  your  structure definition.

The function  definitions  must remain  unaltered!

 

• A sorted-list.c file containing your implementation of the sorted list.

 

• A main.c file containing a main function that exercises your sorted list implementation using the test plan outlined in testplan.txt.

 

• A Makefile  that is used  to compile  your  sorted  list  implementation  into  a  library  called

libsl.a and an executable called sl that runs the code in main.c.

 

• A file called  testplan.txt  that contains  a  test plan  for your  code,  including  input and expected output.

 

• A readme.pdf file that contains analyzes  of the running  time and  memory  usage of each of your sorted-list functions.  Use big-O notation to describe the end result of each analysis.

 

Suppose  that you  have  a directory called  pa2  in your  account (on  iLab),  containing the above required  files. Here’s how you create the required  tar file. (The ls commands  are just to help show you where you should be in relation to pa2.  The only necessary command  is the tar command.)

$  ls pa2

$  tar  cfz pa2.tgz  pa2

 

 

You can check your pa2.tgz by either untarring it or running  tar  tfz  pa2.tgz (see man  tar). Your grade will be based on:

 

• Correctness (how well your code is working),

 

• Quality of your design (did you use reasonable  algorithms),

 

• Quality of your code (how well-written your code is, including  modularity and comments),

 

• Efficiency (of your implementation), and

 

• Testing thoroughness (quality of your test cases).