For this problem, using C, you will implement the Deque ADT with a Circularly-Do

Question

For this problem, using C, 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 meaningful 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. Implement all functions with the // FIXME... comments in circularList.c .

circularList.h

#ifndef CIRCULAR_LIST_H
#define CIRCULAR_LIST_H

#ifndef TYPE
#define TYPE double
#endif

#ifndef LT
#define LT(A, B) ((A) < (B))
#endif

#ifndef EQ
#define EQ(A, B) ((A) == (B))
#endif

struct CircularList;

struct CircularList* circularListCreate();
void circularListDestroy(struct CircularList* list);
void circularListPrint(struct CircularList* list);
void circularListReverse(struct CircularList* list);

// Deque interface

void circularListAddFront(struct CircularList* list, TYPE value);
void circularListAddBack(struct CircularList* list, TYPE value);
TYPE circularListFront(struct CircularList* list);
TYPE circularListBack(struct CircularList* list);
void circularListRemoveFront(struct CircularList* list);
void circularListRemoveBack(struct CircularList* list);
int circularListIsEmpty(struct CircularList* list);

#endif

circularListMain.c

#include "circularList.h"
#include <stdio.h>

int main()
{
struct CircularList* deque = circularListCreate();
circularListAddBack(deque, (TYPE)1);
circularListAddBack(deque, (TYPE)2);
circularListAddBack(deque, (TYPE)3);
circularListAddFront(deque, (TYPE)4);
circularListAddFront(deque, (TYPE)5);
circularListAddFront(deque, (TYPE)6);
circularListPrint(deque);
printf("%g ", circularListFront(deque));
printf("%g ", circularListBack(deque));

circularListRemoveFront(deque);
circularListRemoveBack(deque);
circularListPrint(deque);

circularListReverse(deque);
circularListPrint(deque);

circularListDestroy(deque);

return 0;
}

circularList.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "circularList.h"

// Double link
struct Link
{
TYPE value;
struct Link * next;
struct Link * prev;
};

struct CircularList
{
int size;
struct Link* sentinel;
};

/**
* Allocates the list's sentinel and sets the size to 0.
* The sentinel's next and prev should point to the sentinel itself.
*/
static void init(struct CircularList* list)
{
// FIXME: you must write this
}

/**
* Creates a link with the given value and NULL next and prev pointers.
*/
static struct Link* createLink(TYPE value)
{
// FIXME: you must write this
return NULL;
}

/**
* Adds a new link with the given value after the given link and
* increments the list's size.
*/
static void addLinkAfter(struct CircularList* list, struct Link* link, TYPE value)
{
// FIXME: you must write this
}

/**
* Removes the given link from the list and
* decrements the list's size.
*/
static void removeLink(struct CircularList* list, struct Link* link)
{
// FIXME: you must write this
}

/**
* Allocates and initializes a list.
*/
struct CircularList* circularListCreate()
{
struct CircularList* list = malloc(sizeof(struct CircularList));
init(list);
return list;
}

/**
* Deallocates every link in the list and frees the list pointer.
*/
void circularListDestroy(struct CircularList* list)
{
// FIXME: you must write this
}

/**
* Adds a new link with the given value to the front of the deque.
*/
void circularListAddFront(struct CircularList* list, TYPE value)
{
// FIXME: you must write this
}

/**
* Adds a new link with the given value to the back of the deque.
*/
void circularListAddBack(struct CircularList* list, TYPE value)
{
// FIXME: you must write this
}

/**
* Returns the value of the link at the front of the deque.
*/
TYPE circularListFront(struct CircularList* list)
{
// FIXME: you must write this
return 0;
}

/**
* Returns the value of the link at the back of the deque.
*/
TYPE circularListBack(struct CircularList* list)
{
// FIXME: you must write this
return 0;
}

/**
* Removes the link at the front of the deque.
*/
void circularListRemoveFront(struct CircularList* list)
{
// FIXME: you must write this
}

/**
* Removes the link at the back of the deque.
*/
void circularListRemoveBack(struct CircularList* list)
{
// FIXME: you must write this
}

/**
* Returns 1 if the deque is empty and 0 otherwise.
*/
int circularListIsEmpty(struct CircularList* list)
{
// FIXME: you must write this
return 0;
}

/**
* Prints the values of the links in the deque from front to back.
*/
void circularListPrint(struct CircularList* list)
{
// FIXME: you must write this
}

/**
* Reverses the deque.
*/
void circularListReverse(struct CircularList* list)
{
// FIXME: you must write this
}

Explanation / Answer

Ans.

#ifndef CIRCULAR_LIST_H
#define CIRCULAR_LIST_H
#ifndef TYPE
#define TYPE double
#endif
#ifndef LT
#define LT(A, B) ((A) < (B))
#endif
#ifndef EQ
#define EQ(A, B) ((A) == (B))
#endif
struct CircularList;
struct CircularList* circularListCreate();
void circularListDestroy(struct CircularList* list);
void circularListPrint(struct CircularList* list);
void circularListReverse(struct CircularList* list);
// Deque interface
void circularListAddFront(struct CircularList* list, TYPE value);
void circularListAddBack(struct CircularList* list, TYPE value);
TYPE circularListFront(struct CircularList* list);
TYPE circularListBack(struct CircularList* list);
void circularListRemoveFront(struct CircularList* list);
void circularListRemoveBack(struct CircularList* list);
int circularListIsEmpty(struct CircularList* list);
#endif

#include "circularList.h"
#include <stdio.h>
int main()
{
struct CircularList* deque = circularListCreate();
circularListAddBack(deque, (TYPE)1);
circularListAddBack(deque, (TYPE)2);
circularListAddBack(deque, (TYPE)3);
circularListAddFront(deque, (TYPE)4);
circularListAddFront(deque, (TYPE)5);
circularListAddFront(deque, (TYPE)6);
circularListPrint(deque);
printf("%g ", circularListFront(deque));
printf("%g ", circularListBack(deque));

circularListRemoveFront(deque);
circularListRemoveBack(deque);
circularListPrint(deque);

circularListReverse(deque);
circularListPrint(deque);

circularListDestroy(deque);

return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "circularList.h"
// Double link
struct Link
{
TYPE value;
struct Link * next;
struct Link * prev;
};
struct CircularList
{
int size;
struct Link* sentinel;
};
/**
* Allocates the list's sentinel and sets the size to 0.
* The sentinel's next and prev should point to the sentinel itself.
*/
static void init(struct CircularList* list)
{
   list->Sentinel = (struct Link*)malloc(sizeof(struct Link));
   assert( list->Sentinel != 0 );
   list->Sentinel->next = list->Sentinel;
   list->Sentinel->prev = list->Sentinel;
   list->size = 0;
}
/**
* Creates a link with the given value and NULL next and prev pointers.
*/
static struct Link* createLink(TYPE value)
{
   struct Link *newL = (struct Link *)malloc(sizeof( struct Link ));
   newL->value = val;
   /*temporary return value..you may need to change it*/
   return(newL);  
}
/**
* Adds a new link with the given value after the given link and
* increments the list's size.
*/
static void addLinkAfter(struct CircularList* list, struct Link* link, TYPE value)
{
   struct Link *nLink = createLink( value );
   assert( list != 0 );
   assert( link != 0 );
   nLink->next = link->next;
   nLink->prev = link;
   nLink->next->prev = nLink;
   link->next = nLink;
   list->size++;
}
/**
* Removes the given link from the list and
* decrements the list's size.
*/
static void removeLink(struct CircularList* list, struct Link* link)
{
   assert( list != 0 );
   assert( list->size != 0 );
   link->prev->next = link->next;
   link->next->prev = link->prev;
   list->size--;
   free(link);

}
/**
* Allocates and initializes a list.
*/
struct CircularList* circularListCreate()
{
struct CircularList* list = malloc(sizeof(struct CircularList));
init(list);
return list;
}
/**
* Deallocates every link in the list and frees the list pointer.
*/
void circularListDestroy(struct CircularList* list)
{
   while( list->size > 0 )
       removeFrontCirListDeque( list );
   free( list->Sentinel );
}
/**
* Adds a new link with the given value to the front of the deque.
*/
void circularListAddFront(struct CircularList* list, TYPE value)
{
   assert( list != 0 );
   addLinkAfter( list, list->Sentinel, value );
}
/**
* Adds a new link with the given value to the back of the deque.
*/
void circularListAddBack(struct CircularList* list, TYPE value)
{
   assert( list != 0 );
   assert( list->size != 0 );
   return( list->Sentinel->prev->value );
}
/**
* Returns the value of the link at the front of the deque.
*/
TYPE circularListFront(struct CircularList* list)
{
   assert( list != 0 );
   assert( list->size != 0 );
   return( list->Sentinel->next->value );

}
/**
* Returns the value of the link at the back of the deque.
*/
TYPE circularListBack(struct CircularList* list)
{
   assert( list != 0 );
   assert( list->size != 0 );
   return( list->Sentinel->prev->value );
}
/**
* Removes the link at the front of the deque.
*/
void circularListRemoveFront(struct CircularList* list)
{
   assert( list!= 0 );
   assert( list->size != 0 );
   removeLink( list, list->Sentinel->next );
}
/**
* Removes the link at the back of the deque.
*/
void circularListRemoveBack(struct CircularList* list)
{
   assert( list != 0 );
   assert( list->size != 0 );
   removeLink( list, list->Sentinel->prev );
}
/**
* Returns 1 if the deque is empty and 0 otherwise.
*/
int circularListIsEmpty(struct CircularList* list)
{
   assert( list != 0 );
   if( list->size == 0 )
       return(1);
   else
       return 0;
}
/**
* Prints the values of the links in the deque from front to back.
*/
void circularListPrint(struct CircularList* list)
{
   struct Link *temp = malloc( sizeof( struct Link ));
   assert( list != 0 );
   assert( list->size != 0 );

   temp = list->Sentinel->next;
   while( temp != list->Sentinel ) {
       printf( "%f ", temp->value );
       temp = temp->next;
   }

   free(temp);
}
/**
* Reverses the deque.
*/
void circularListReverse(struct CircularList* list)
{
   struct CircularList *newL = circularListCreate();
   assert( list != 0 );
   assert( list->size != 0 );
   while( !circularListIsEmpty( list)){
       circularListAddBack( newL, circularListBack(q));
       printf( "%f ", circularListBack(q));
       circularListRemoveBack(q);
   }

   list->Sentinel = newL->Sentinel->next;
   list->size = newL->size;

   free( newL );
}  

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.