C programming:Linked lists Complete the linked list-based implementation of a de

Question

C programming:Linked lists

Complete the linked list-based implementation of a deque and a bag in ListDeque.c. The comments for each function will help you understand what each function should be doing. We have provided the header files for this assignment, DO NOT change the provided header files (ListDeque.h, type.h)

Functions you will need to complete:

initListDeque()

isEmptyListDeque()

addLinkAfterListDeque()

addLinkBeforeListDeque()

addBackListDeque()

addFrontListDeque()

frontListDeque()

backListDeque()

removeLinkListDeque()

removeFrontListDeque()

removeBackListDeque()

freeListDeque()

containsListDeque()

removeListDeque()

reverseListDeque()

the output should be a linked list.

Note that we have provided a _createLink() function which you can use to help implement your functions, as well as a printListDeque() function which you can use to help debug your code. Also, note thatprintListDeque() provides an example of iterating through a linked list.

//ListDeque.h

//ListDeque.c

//type.h

//main.c

Explanation / Answer

#ifndef LIST_DEQUE_H_INCLUDED
#define LIST_DEQUE_H_INCLUDED

#include "type.h"

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

struct ListDeque {
int size; /* number of links in the deque */
DLink* head; /* pointer to the front */
DLink* tail; /* pointer to the back */
};
typedef struct ListDeque ListDeque;

/* Basic Operations */
void initListDeque(ListDeque* q);
void freeListDeque(ListDeque* q);

int isEmptyListDeque(ListDeque *q);

TYPE frontListDeque(ListDeque* q);
TYPE backListDeque(ListDeque* q);

void addLinkAfterListDeque(ListDeque* q, DLink* addAfter, DLink* newLink);
void addLinkBeforeListDeque(ListDeque* q, DLink* addBefore, DLink* newLink);
DLink* removeLinkListDeque(ListDeque* q, DLink* toRemove);

/* Deque interface */
void addBackListDeque(ListDeque* q, TYPE val);
void addFrontListDeque(ListDeque* q, TYPE val);
void removeFrontListDeque(ListDeque* q);
void removeBackListDeque(ListDeque* q);

/* Bag Interface */   
int containsListDeque(ListDeque* q, TYPE val);
void removeListDeque(ListDeque* q, TYPE val);

/* Other functions */
void reverseListDeque(ListDeque* q);
void printListDeque(ListDeque* q);

#endif

//ListDeque.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "ListDeque.h"

DLink* _createLink(TYPE val)
{
DLink* lnk = (DLink*) malloc(sizeof(DLink));
assert(lnk != 0);
  
lnk->value = val;
return lnk;
}

void initListDeque(ListDeque* d)
{
d -> head = d -> tail = NULL ;
}

void freeListDeque(ListDeque* d)
{   
while (d-value > 0)
removeFrontListDeque(q);
free (d->head);
free (d->tail);
d->head = d->tail = null;
}

int isEmptyListDeque(ListDeque *d)
{

if((d->front)==NULL)
{
return 0;
}
else
{
return 1;
}
}

TYPE frontListDeque (ListDeque *d)
{
assert(!isEmptyListDeque(d));
return d->head->value;
}

TYPE backListDeque(ListDeque *d)
{
TYPE var;
assert(!isEmptyListDeque(d));
var= d->tail->value;
return var;
}

void addLinkAfterListDeque(ListDeque* d, DLink* addAfter, DLink* newLnk)
{
struct DLink * newLnk = (struct DLink *) malloc(sizeof(struct DLink));
assert(newLnk != 0);
newLnk->value = e;
newLnk->prev = addAfter->prev;
newLnk->next = addAfter;
addAfter->prev->next = newLnk;
addAfter->prev = newLnk;
q->size++;
}

void addLinkBeforeListDeque(ListDeque* d, DLink* addBefore, DLink* newLnk)
{
struct DLink * newLnk = (struct DLink *) malloc(sizeof(struct DLink));
assert(newLnk != 0);
newLnk->value = e;
newLnk->prev = addBefore->prev;
newLnk->next = addBefore;
addBefore->prev->next = newLnk;
addBefore->prev = newLnk;
q->size++;
}

DLink* removeLinkListDeque(ListDeque *d, DLink *lnk)
{
lnk->prev->next = lnk->next;
lnk->next->prev = lnk->prev;
free(lnk);
d->size--;
return NULL;
}

void addBackListDeque (ListDeque *d, TYPE val)
{
DLink *p;
p=(DLink*)malloc(sizeof(DLink));
p->size=val;
p->next=NULL;
if(empty(d))
{
d->tail=p;
d->head=p;
}
else
{
p->next=d->head;
d->head=p;
}
}

void addFrontListDeque(ListDeque *d, TYPE val)
{
DLink *p;
p=(DLink*)malloc(sizeof(DLink));
p->size=val;
p->next=NULL;
if(empty(d))
{
d->tail=p;
d->head=p;
}
else
{
p->next=d->head;
d->head=p;
}
}

void removeFrontListDeque (ListDeque *d)
{
int x;
DLink *p;
p=d->head;
x=p->size;
if(d->head==d->tail) //deleting the last element
initialise(d);
else
d->head=p->next;
free(p);
return(x);
}

void removeBackListDeque(ListDeque *d)
{
int x;
DLink *p,*q;
p=d->tail;
x=p->size;
if(d->head==d->tail) //deleting the last element
initialise(d);
else
{ //locate the predecessor of rear node
q=d->head;
while(q->next != d->tail)
q=q->next;
q->next=NULL;
d->tail=q;
}
free(p);
return(x);
}

void printListDeque(ListDeque *q)
{
DLink* lnk;
lnk = q->head;
printf("Size = %d [ ", q->size);
while(lnk != NULL)
{
printf("%c ", lnk->value);
lnk = lnk->next;
}
printf("] ");
}

#ifndef __TYPE_H
#define __TYPE_H

# ifndef TYPE
# define TYPE char
# define TYPE_SIZE sizeof(char)
# endif

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

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

#endif
//main.c
#include <stdio.h>
#include <stdlib.h>
#include "ListDeque.h"

int main (int argc, const char * argv[])
{
ListDeque testDeque;
TYPE val1 = 'A';
TYPE val2 = 'B';
TYPE val3 = 'C';
int i;

initListDeque(&testDeque);
printListDeque(&testDeque);
  
addBackListDeque(&testDeque, val1); printListDeque(&testDeque);
addBackListDeque(&testDeque, val2); printListDeque(&testDeque);
addBackListDeque(&testDeque, val3); printListDeque(&testDeque);
  
printf("contains('A') = %d, contains('D') = %d ", containsListDeque(&testDeque, 'A'), containsListDeque(&testDeque, 'D'));
printf("front() = %c, back() = %c ", frontListDeque(&testDeque), backListDeque(&testDeque));
  
removeBackListDeque(&testDeque); printListDeque(&testDeque);
removeBackListDeque(&testDeque); printListDeque(&testDeque);
removeBackListDeque(&testDeque); printListDeque(&testDeque);

for(i = 0; i < 2; ++i)
{
addFrontListDeque(&testDeque, val3); printListDeque(&testDeque);
addFrontListDeque(&testDeque, val2); printListDeque(&testDeque);
addFrontListDeque(&testDeque, val1); printListDeque(&testDeque);
}
  
printf("contains('B') = %d, contains('R') = %d ", containsListDeque(&testDeque, 'B'), containsListDeque(&testDeque, 'R'));
printf("front() = %c, back() = %c ", frontListDeque(&testDeque), backListDeque(&testDeque));
  
reverseListDeque(&testDeque); printListDeque(&testDeque);
  
removeListDeque(&testDeque, 'B'); printListDeque(&testDeque);
removeListDeque(&testDeque, 'D'); printListDeque(&testDeque);
  
removeFrontListDeque(&testDeque); printListDeque(&testDeque);
removeFrontListDeque(&testDeque); printListDeque(&testDeque);
removeFrontListDeque(&testDeque); printListDeque(&testDeque);
removeFrontListDeque(&testDeque); printListDeque(&testDeque);
  
freeListDeque(&testDeque);
  
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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