Use the header and other files listed below for problems 1 and 2. Each problem h
ID: 3858166 • Letter: U
Question
Use the header and other files listed below for problems 1 and 2. Each problem has 3 files that correspond to the problem.
Problem 1, linked list deque and bag implementations.
First, complete the linked list implementation of the deque and bag ADTs in C language. To do this, implement all functions with the // FIXME... comments in linkedList.c (File included below). These functions listed are the ones that need to be fixed.
init
addLinkBefore
removeLink
linkedListAddFront
linkedListAddBack
linkedListFront
linkedListBack
linkedListRemoveFront
linkedListRemoveBack
linkedListIsEmpty
linkedListPrint
linkedListContains
linkedListRemove
Problem 2: Circularly Linked List Deque implementation
Using the circularList.c (listed below) for this problem, you will implement the Deque ADT with a CircularlyDoublyLinked 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.
init
createLink
addLinkAfter
removeLink
circularListAddBack
circularListAddFront
circularListFront
circularListBack
circularListRemoveFront
circularListRemoveBack
circularListDestroy
circularListIsEmpty
circularListPrint
circularListReverse 6 pts
As usual do not make any modifications to the header files or include any additional headers, and make sure everything compiles and runs.
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
circularList.c
#include
#include
#include
#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
}
circularListMain.c
#include "circularList.h"
#include
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;
}
linkedList.h
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#ifndef TYPE
#define TYPE int
#endif
#ifndef LT
#define LT(A, B) ((A) < (B))
#endif
#ifndef EQ
#define EQ(A, B) ((A) == (B))
#endif
struct LinkedList;
struct LinkedList* linkedListCreate();
void linkedListDestroy(struct LinkedList* list);
void linkedListPrint(struct LinkedList* list);
// Deque interface
int linkedListIsEmpty(struct LinkedList* list);
void linkedListAddFront(struct LinkedList* list, TYPE value);
void linkedListAddBack(struct LinkedList* list, TYPE value);
TYPE linkedListFront(struct LinkedList* list);
TYPE linkedListBack(struct LinkedList* list);
void linkedListRemoveFront(struct LinkedList* list);
void linkedListRemoveBack(struct LinkedList* list);
// Bag interface
void linkedListAdd(struct LinkedList* list, TYPE value);
int linkedListContains(struct LinkedList* list, TYPE value);
void linkedListRemove(struct LinkedList* list, TYPE value);
#endif
linkedList.c
#include "linkedList.h"
#include
#include
#include
// Double link
struct Link
{
TYPE value;
struct Link* next;
struct Link* prev;
};
// Double linked list with front and back sentinels
struct LinkedList
{
int size;
struct Link* frontSentinel;
struct Link* backSentinel;
};
/**
* Allocates the list's sentinel and sets the size to 0.
* The sentinels' next and prev should point to eachother or NULL
* as appropriate.
*/
static void init(struct LinkedList* list) {
// FIXME: you must write this
}
/**
* Adds a new link with the given value before the given link and
* increments the list's size.
*/
static void addLinkBefore(struct LinkedList* 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 LinkedList* list, struct Link* link)
{
// FIXME: you must write this
}
/**
* Allocates and initializes a list.
*/
struct LinkedList* linkedListCreate()
{
struct LinkedList* newDeque = malloc(sizeof(struct LinkedList));
init(newDeque);
return newDeque;
}
/**
* Deallocates every link in the list including the sentinels,
* and frees the list itself.
*/
void linkedListDestroy(struct LinkedList* list)
{
while (!linkedListIsEmpty(list))
{
linkedListRemoveFront(list);
}
free(list->frontSentinel);
free(list->backSentinel);
free(list);
}
/**
* Adds a new link with the given value to the front of the deque.
*/
void linkedListAddFront(struct LinkedList* list, TYPE value)
{
// FIXME: you must write this
}
/**
* Adds a new link with the given value to the back of the deque.
*/
void linkedListAddBack(struct LinkedList* list, TYPE value)
{
// FIXME: you must write this
}
/**
* Returns the value of the link at the front of the deque.
*/
TYPE linkedListFront(struct LinkedList* list)
{
// FIXME: you must write this
}
/**
* Returns the value of the link at the back of the deque.
*/
TYPE linkedListBack(struct LinkedList* list)
{
// FIXME: you must write this
}
/**
* Removes the link at the front of the deque.
*/
void linkedListRemoveFront(struct LinkedList* list)
{
// FIXME: you must write this
}
/**
* Removes the link at the back of the deque.
*/
void linkedListRemoveBack(struct LinkedList* list)
{
// FIXME: you must write this
}
/**
* Returns 1 if the deque is empty and 0 otherwise.
*/
int linkedListIsEmpty(struct LinkedList* list)
{
// FIXME: you must write this
}
/**
* Prints the values of the links in the deque from front to back.
*/
void linkedListPrint(struct LinkedList* list)
{
// FIXME: you must write this
}
/**
* Adds a link with the given value to the bag.
*/
void linkedListAdd(struct LinkedList* list, TYPE value)
{
// FIXME: you must write this
}
/**
* Returns 1 if a link with the value is in the bag and 0 otherwise.
*/
int linkedListContains(struct LinkedList* list, TYPE value)
{
// FIXME: you must write this
}
/**
* Removes the first occurrence of a link with the given value.
*/
void linkedListRemove(struct LinkedList* list, TYPE value)
{
// FIXME: you must write this
}
linkedListMain.c
#include "linkedList.h"
#include
int main(){
struct LinkedList* l = linkedListCreate();
linkedListAddFront(l, (TYPE)1);
linkedListAddBack(l, (TYPE)2);
linkedListAddBack(l, (TYPE)3);
linkedListAddFront(l, (TYPE)4);
linkedListAddFront(l, (TYPE)5);
linkedListAddBack(l, (TYPE)6);
linkedListPrint(l);
printf("%i ", linkedListFront(l));
printf("%i ", linkedListBack(l));
linkedListRemoveFront(l);
linkedListRemoveBack(l);
linkedListPrint(l);
/* BAG */
struct LinkedList* k = linkedListCreate();
linkedListAdd (k, (TYPE)10);
linkedListAdd (k, (TYPE)11);
linkedListAdd (k, (TYPE)13);
linkedListAdd(k, (TYPE)14);
linkedListRemove(k, (TYPE)11);
linkedListPrint(k);
return 0;
}
Explanation / Answer
Given below is the completed implementation of linkedList.c and circularList.c. Except the circularListReverse() function all of the other required methods are done. Please rate the answer if it helped. Thank you.
linkedList.c
#include "linkedList.h"
#include <stdlib.h>
#include <stdio.h>
//#include
// Double link
struct Link
{
TYPE value;
struct Link* next;
struct Link* prev;
};
// Double linked list with front and back sentinels
struct LinkedList
{
int size;
struct Link* frontSentinel;
struct Link* backSentinel;
};
/**
* Allocates the list's sentinel and sets the size to 0.
* The sentinels' next and prev should point to eachother or NULL
* as appropriate.
*/
static void init(struct LinkedList* list) {
list->frontSentinel = (struct Link *) malloc(sizeof(struct Link));
list->backSentinel = (struct Link *) malloc(sizeof(struct Link));
list->backSentinel->value = 0;
list->frontSentinel->value = 0;
list->frontSentinel->prev = NULL;
list->frontSentinel->next = list->backSentinel;
list->backSentinel->prev = list->frontSentinel;
list->backSentinel->next = NULL;
list->size = 0;
}
/**
* Adds a new link with the given value before the given link and
* increments the list's size.
*/
static void addLinkBefore(struct LinkedList* list, struct Link* link, TYPE value)
{
struct Link* newl = (struct Link *) malloc(sizeof(struct Link));
newl->value = value;
newl->next = link;
newl->prev = link->prev;
newl->prev->next = newl;
link->prev = newl;
list->size++;
}
/**
* Removes the given link from the list and
* decrements the list's size.
*/
static void removeLink(struct LinkedList* list, struct Link* link)
{
if(link == NULL) return;
struct Link *prev = link->prev , *next = link->next;
prev->next = next;
free(link);
list->size--;
}
/**
* Allocates and initializes a list.
*/
struct LinkedList* linkedListCreate()
{
struct LinkedList* newDeque = malloc(sizeof(struct LinkedList));
init(newDeque);
return newDeque;
}
/**
* Deallocates every link in the list including the sentinels,
* and frees the list itself.
*/
void linkedListDestroy(struct LinkedList* list)
{
while (!linkedListIsEmpty(list))
{
linkedListRemoveFront(list);
}
free(list->frontSentinel);
free(list->backSentinel);
free(list);
}
/**
* Adds a new link with the given value to the front of the deque.
*/
void linkedListAddFront(struct LinkedList* list, TYPE value)
{
addLinkBefore(list, list->frontSentinel->next, value);
}
/**
* Adds a new link with the given value to the back of the deque.
*/
void linkedListAddBack(struct LinkedList* list, TYPE value)
{
addLinkBefore(list, list->backSentinel, value);
}
/**
* Returns the value of the link at the front of the deque.
*/
TYPE linkedListFront(struct LinkedList* list)
{
return list->frontSentinel->next->value;
}
/**
* Returns the value of the link at the back of the deque.
*/
TYPE linkedListBack(struct LinkedList* list)
{
return list->backSentinel->prev->value;
}
/**
* Removes the link at the front of the deque.
*/
void linkedListRemoveFront(struct LinkedList* list)
{
if(list->size > 0)
removeLink(list, list->frontSentinel->next);
}
/**
* Removes the link at the back of the deque.
*/
void linkedListRemoveBack(struct LinkedList* list)
{
if(list->size > 0)
removeLink(list, list->backSentinel->prev);
}
/**
* Returns 1 if the deque is empty and 0 otherwise.
*/
int linkedListIsEmpty(struct LinkedList* list)
{
if(list->size == 0)
return 1;
else
return 0;
}
/**
* Prints the values of the links in the deque from front to back.
*/
void linkedListPrint(struct LinkedList* list)
{
struct Link *p = list->frontSentinel->next;
printf(" ");
while(p != list->backSentinel)
{
printf("%d ", p->value);
p = p->next;
}
printf(" ");
}
/**
* Adds a link with the given value to the bag.
*/
void linkedListAdd(struct LinkedList* list, TYPE value)
{
addLinkBefore(list, list->backSentinel, value);
}
/**
* Returns 1 if a link with the value is in the bag and 0 otherwise.
*/
int linkedListContains(struct LinkedList* list, TYPE value)
{
struct Link *p = list->frontSentinel->next;
while(p != list->backSentinel)
{
if(p->value == value)
return 1;
p = p->next;
}
return 0;
}
/**
* Removes the first occurrence of a link with the given value.
*/
void linkedListRemove(struct LinkedList* list, TYPE value)
{
struct Link *p = list->frontSentinel->next;
while(p != list->backSentinel)
{
if(p->value == value)
removeLink(list, p);
p = p->next;
}
}
output of linkedListMain.c
5 4 1 2 3 6
5
6
4 1 2 3
10 13 14
circularList.c
#include <stdlib.h>
#include <stdio.h>
//#include
#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));
list->sentinel->next = list->sentinel;
list->sentinel->prev = list->sentinel;
list->sentinel->value = 0;
list->size = 0;
}
/**
* Creates a link with the given value and NULL next and prev pointers.
*/
static struct Link* createLink(TYPE value)
{
struct Link *p = (struct Link *) malloc(sizeof(struct Link));
p->value = value;
p->next = NULL;
p->prev = NULL;
return p;
}
/**
* 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* p = createLink(value);
p->next = link->next;
link->next = p;
p->next->prev = p;
p->prev = link;
list->size++;
}
/**
* Removes the given link from the list and
* decrements the list's size.
*/
static void removeLink(struct CircularList* list, struct Link* link)
{
link->prev->next = link->next;
link->next->prev = link->prev;
free(link);
list->size--;
}
/**
* 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 (!circularListIsEmpty(list))
{
circularListRemoveFront(list);
}
free(list->sentinel);
free(list);
}
/**
* Adds a new link with the given value to the front of the deque.
*/
void circularListAddFront(struct CircularList* list, TYPE value)
{
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)
{
addLinkAfter(list, list->sentinel->prev, value);
}
/**
* Returns the value of the link at the front of the deque.
*/
TYPE circularListFront(struct CircularList* list)
{
return list->sentinel->next->value;
}
/**
* Returns the value of the link at the back of the deque.
*/
TYPE circularListBack(struct CircularList* list)
{
return list->sentinel->prev->value;
}
/**
* Removes the link at the front of the deque.
*/
void circularListRemoveFront(struct CircularList* list)
{
if(!circularListIsEmpty(list))
removeLink(list, list->sentinel->next);
}
/**
* Removes the link at the back of the deque.
*/
void circularListRemoveBack(struct CircularList* list)
{
if(!circularListIsEmpty(list))
removeLink(list, list->sentinel->prev);
}
/**
* Returns 1 if the deque is empty and 0 otherwise.
*/
int circularListIsEmpty(struct CircularList* list)
{
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 *p = list->sentinel->next;
printf(" ");
while(p != list->sentinel)
{
printf("%lf ", p->value);
p = p->next;
}
printf(" ");
}
/**
* Reverses the deque.
*/
void circularListReverse(struct CircularList* list)
{
//complete this method
}
output
6.000000 5.000000 4.000000 1.000000 2.000000 3.000000
6
3
5.000000 4.000000 1.000000 2.000000
5.000000 4.000000 1.000000 2.000000
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.