Subject Computer Science Data Structures and Algorithms

Question

Implementation of the Deque ADT using a Circularly linked list.
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.

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <float.h>
#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
************************************************************************ */

/* Initialize deque.

param: q pointer to the deque
pre: q is not null
post: q->Sentinel is allocated and q->size equals zero
*/
void _initCirListDeque (struct cirListDeque *q)
{
/* FIXME: you must write this */
assert( q != NULL);
q->size = 0;
q->Sentinel = (struct DLink *) malloc(sizeof(struct DLink));
q->Sentinel->next = q->Sentinel;
q->Sentinel->prev = q->Sentinel;
}

/*
create a new circular list deque

*/

struct cirListDeque *createCirListDeque()
{
struct cirListDeque *newCL = malloc(sizeof(struct cirListDeque));
_initCirListDeque(newCL);
return(newCL);
}...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Assisting Tutor

Related Homework Solutions

Dynamic Programming Model for A Version of Job Scheduling Problem
Homework Solution
$30.00
Knapsack
Reduction
Algorithm
Complexity
Problem
Job
Scheduling
Dynamic
Programming
OPT
Optimal
Swapping
Exchange
Argument
Playful
Subset
Deadline
Value
Size
Profit
Function
Solution
Set
Array
Two
Dimensional
Selection
Reorder
M
Algorithms Assignment
Homework Solution
$1.00
Algorithm
Computer Science
Graphs
Programming Language
Programming
Analysis
Three Algorithm Design Questions with Full Steps
Homework Solution
$33.00
Algorithm
Design
Input
Question
Elementary
Operation
Size
Pseudocode
Big-O
Asymptotic
Complexity
Image
2-dimensional
Array
Pixel
Rotate
Clockwise
Set
Circle
Radius
Center
Intersect
Collection
Integer
Inversion
List
Get help from a qualified tutor
Live Chats