QuestionQuestion

1 Introduction
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 into and deleting an object 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 negative value if the first object is smaller, 0 if the two objects are equal, and a positive value 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.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

#include <stdlib.h>
#include "sorted-list.h"

/*
* When your sorted list is used to store objects of some type, since the
* type is opaque to you, you will need a comparator function to order
* the objects in your sorted list.
*
* You can expect a comparator function to return a negative value if the
* first object is smaller, 0 if the two objects are equal, and a positive
* value if the second object is smaller.
*
* Note that you are not expected to implement any comparator or destruct
* functions. You will be given a comparator function and a destruct
* function when a new sorted list is created.
*/

typedef int (*CompareFuncT)(void *, void *);
typedef void (*DestructFuncT)(void *);

/*
* SLCreate creates a new, empty sorted list. The caller must provide
* a comparator function that can be used to order objects that will be
* kept in the list, and a destruct function that gets rid of the objects
* once they are no longer in the list or referred to in an iterator.
*
* If the function succeeds, it returns a (non-NULL) SortedListT object.
* otherwise, it returns NULL.
*
* You need to fill in this function as part of your implementation.
*/

SortedListPtr SLCreate(CompareFuncT cf, DestructFuncT df) {
    // init the pointer, allocate memory
    SortedListPtr sl = malloc(sizeof (struct SortedList));
    // step all data
    sl->cmp = cf;
    sl->des = df;
    sl->head = NULL;
    sl->head_real = NULL;
    return sl;
}

/*
* SLDestroy destroys a list, freeing all dynamically allocated memory.
*
* You need to fill in this function as part of your implementation.
*/
void SLDestroy(SortedListPtr list) {
    // set up all required pointer
    NodePtr prev;
    NodePtr curr = list->head_real;   
    // move the the last one
    while (curr != NULL) {
       // destroy data
       list->des(curr->data);
       // next move
       prev = curr;
       curr = curr->next_real;
       // free the node
       free(prev);
    }
    list->head = NULL;
}...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$50.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available C-Family Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats