For this problem, you will implement the Deque ADT with a Circularly-Doubly-Linked List with a Sentinel. As you know, the sentinel is a special link, does not contain a value, and should not be removed. Using a sentinel makes some linked list operations easier and cleaner in implementation. This list is circular, meaning the end points back to the beginning, thus one sentinel suffices (the last item should point to the sentinel as its next, and the sentinel's prev should be the last item). This is a bit different than the two sentinel solution talked about in the class and the slides. The header file and the implementation file for this approach are cirListDeque.h and cirListDeque.c, respectively. Complete the functions in cirListDeque.c and write a test harness (main function) in testCirListDeque.c to test the functionality of your Circularly-Doubly-Linked List deque.

You are supposed to check the precondition listed in "pre: " for each function with an assert.

#include #include #include #include #include "cirListDeque.h"

/* Double Link Struture */ struct DLink { TYPE value;/* value of the link */ struct DLink * next;/* pointer to the next link */ struct DLink * prev;/* pointer to the previous link */ };

# define TYPE_SENTINEL_VALUE DBL_MAX

/* ************************************************************************ Deque ADT based on Circularly-Doubly-Linked List WITH Sentinel ************************************************************************ */

struct cirListDeque { int size;/* number of links in the deque */ struct DLink *Sentinel; /* pointer to the sentinel */ }; /* internal functions prototypes */ struct DLink* _createLink (TYPE val); void _addLinkAfter(struct cirListDeque *q, struct DLink *lnk, TYPE v); void _removeLink(struct cirListDeque *q, struct DLink *lnk);

/* ************************************************************************ Deque Functions ************************************************************************ */

/* create a new circular list deque pre: none post: returns pointer to allocated deque q, q->Sentinel is allocated and q->size equals zero */

struct cirListDeque *createCirListDeque() { /* FIXME: you must write this */ }

/* Create a link for a value.

param: val the value to create a link for pre: none post: a link to store the value */ struct DLink * _createLink (TYPE val) { /* FIXME: you must write this */

/*temporary return value..you may need to change it*/ return(0);

}

/* Adds a link after another link

param: q pointer to the deque param: lnk pointer to the existing link in the deque param: v value of the new link to be added after the existing link pre: q is not null pre: lnk is not null pre: lnk is in the deque post: the new link is added into the deque after the existing link */ void _addLinkAfter(struct cirListDeque *q, struct DLink *lnk, TYPE v) { /* FIXME: you must write this */

}

/* Adds a link to the back of the deque

param: q pointer to the deque param: val value for the link to be added pre: q is not null post: a link storing val is added to the back of the deque */ void addBackCirListDeque (struct cirListDeque *q, TYPE val) { /* FIXME: you must write this */

}

/* Adds a link to the front of the deque

param: q pointer to the deque param: val value for the link to be added pre: q is not null post: a link storing val is added to the front of the deque */ void addFrontCirListDeque(struct cirListDeque *q, TYPE val) { /* FIXME: you must write this */

}

/* Get the value of the front of the deque

param: q pointer to the deque pre: q is not null and q is not empty post: none ret: value of the front of the deque */ TYPE frontCirListDeque(struct cirListDeque *q) { /* FIXME: you must write this */ /*temporary return value..you may need to change it*/ return(1); }

/* Get the value of the back of the deque

param: q pointer to the deque pre: q is not null and q is not empty post: none ret: value of the back of the deque */ TYPE backCirListDeque(struct cirListDeque *q) { /* FIXME: you must write this */ /*temporary return value..you may need to change it*/ return(1); }

/* Remove a link from the deque

param: q pointer to the deque param: lnk pointer to the link to be removed pre: q is not null and q is not empty post: the link is removed from the deque */ void _removeLink(struct cirListDeque *q, struct DLink *lnk) { /* FIXME: you must write this */

}

/* Remove the front of the deque

param: q pointer to the deque pre: q is not null and q is not empty post: the front is removed from the deque */ void removeFrontCirListDeque (struct cirListDeque *q) { /* FIXME: you must write this */

}

/* Remove the back of the deque

param: q pointer to the deque pre: q is not null and q is not empty post: the back is removed from the deque */ void removeBackCirListDeque(struct cirListDeque *q) { /* FIXME: you must write this */ }

/* De-allocate all links of the deque, and the deque itself

param: q pointer to the deque pre: none post: All links (including Sentinel) are de-allocated */ void freeCirListDeque(struct cirListDeque *q) { /* FIXME: you must write this */ }

/* Check whether the deque is empty

param: q pointer to the deque pre: q is not null ret: 1 if the deque is empty. Otherwise, 0. */ int isEmptyCirListDeque(struct cirListDeque *q) { /* FIXME: you must write this */ /*temporary return value..you may need to change it*/ return(1); }

/* Print the links in the deque from front to back

param: q pointer to the deque pre: q is not null and q is not empty post: the links in the deque are printed from front to back */ void printCirListDeque(struct cirListDeque *q) { /* FIXME: you must write this */

}