#ifndef MAIN_SAVITCH_NODE2_H #define MAIN_SAVITCH_NODE2_H #include <cstdlib> //

Question

#ifndef MAIN_SAVITCH_NODE2_H  

#define MAIN_SAVITCH_NODE2_H

#include <cstdlib> // Provides NULL and size_t

#include <iterator> // Provides iterator and forward_iterator_tag

namespace main_savitch_6B

{

template <class Item>

class node

{

public:

// TYPEDEF

typedef Item value_type;

// CONSTRUCTOR

node(const Item& init_data=Item( ), node* init_link=NULL)

{ data_field = init_data; link_field = init_link; }

// MODIFICATION MEMBER FUNCTIONS

Item& data( ) { return data_field; }

node* link( ) { return link_field; }

void set_data(const Item& new_data) { data_field = new_data; }

void set_link(node* new_link) { link_field = new_link; }

// CONST MEMBER FUNCTIONS

const Item& data( ) const { return data_field; }

const node* link( ) const { return link_field; }

private:

Item data_field;

node *link_field;

};

// FUNCTIONS to manipulate a linked list:

template <class Item>

void list_clear(node<Item>*& head_ptr);

template <class Item>

void list_copy

(const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr);

template <class Item>

void list_head_insert(node<Item>*& head_ptr, const Item& entry);

template <class Item>

void list_head_remove(node<Item>*& head_ptr);

template <class Item>

void list_insert(node<Item>* previous_ptr, const Item& entry);

template <class Item>

std::size_t list_length(const node<Item>* head_ptr);

template <class NodePtr, class SizeType>

NodePtr list_locate(NodePtr head_ptr, SizeType position);

template <class Item>

void list_remove(node<Item>* previous_ptr);

template <class NodePtr, class Item>

NodePtr list_search(NodePtr head_ptr, const Item& target);

// FORWARD ITERATORS to step through the nodes of a linked list

// A node_iterator of can change the underlying linked list through the

// * operator, so it may not be used with a const node. The

// node_const_iterator cannot change the underlying linked list

// through the * operator, so it may be used with a const node.

// WARNING:

// This classes use std::iterator as its base class;

// Older compilers that do not support the std::iterator class can

// delete everything after the word iterator in the second line:

template <class Item>

class node_iterator

: public std::iterator<std::forward_iterator_tag, Item>

{

public:

node_iterator(node<Item>* initial = NULL)

{ current = initial; }

Item& operator *( ) const

{ return current->data( ); }

node_iterator& operator ++( ) // Prefix ++

{

current = current->link( );

return *this;

}

node_iterator operator ++(int) // Postfix ++

{

node_iterator original(current);

current = current->link( );

return original;   

}

bool operator ==(const node_iterator other) const

{ return current == other.current; }

bool operator !=(const node_iterator other) const

{ return current != other.current; }

private:

node<Item>* current;

};

template <class Item>

class const_node_iterator

: public std::iterator<std::forward_iterator_tag, const Item>

{

public:

const_node_iterator(const node<Item>* initial = NULL)

{ current = initial; }

const Item& operator *( ) const

{ return current->data( ); }

const_node_iterator& operator ++( ) // Prefix ++

{

current = current->link( );

return *this;

}

const_node_iterator operator ++(int) // Postfix ++

{

const_node_iterator original(current);

current = current->link( );

return original;

}

bool operator ==(const const_node_iterator other) const

{ return current == other.current; }

bool operator !=(const const_node_iterator other) const

{ return current != other.current; }

private:

const node<Item>* current;

};

}

#include "node2.template"

#endif

#ifndef _DEQUE_H_
#define _DEQUE_H_

#include <iostream>
#include <cstdlib>
#include "node2.h"

using namespace main_savitch_6B;

template <typename T>
class deque
{
public:
typedef std::size_t size_type;
  
//postcondition: empty deque has been created
deque();
  
// postcondition: all resouroces allocated to the deque
// have been deallocated
~deque();
  
// postcondition: newly created deque is a copy of dq
deque(const deque<T>& dq);
  
// postcondition: current deque is a copy of dq
deque<T>& operator = (const deque<T>& dq);
  
  
//precondition: deque is not empty
// postcondition: reference to element at front of deque
// has been returned
T& front();
  
// precondition: deque is not empty
// postcondition: copy of element at front of deque
// has been returned
T front() const;
  
// precondition: deque is not empty
// postcondition: reference to element at front of deque
// has been returned
T& back();
  
// precondition: deque is not empty
// postcondition: copy of element at back of deque
// has been returned
T back() const;
  
// postcondition: entry has been inserted at the front
// of the deque
void push_front (const T& entry);
  
// postcondition: entry has been inserted at the back
// of the deque
void push_back (const T& entry);
  
// precondition: deque is not empty
// postcondition: element at front of deque has been removed
void pop_front();
  
// precondition: deque is not empty
// postcondition: element at back of deque has been removed
void pop_back();
  
// postcondition: number of elements in deque has been returned
size_type size() const;
  
// postcondition: whether deque is empty has been returned
bool empty() const;
  
// postcondition: returned whether 2 deques are equal - equal is defined
// as the deques have the same number of elements &
// corresponding elements are equal
template <typename U>
friend bool operator == (const deque<U>& dq1, const deque<U>& dq2);

// postcondition: dq has been display from front to rear on out
template <typename U>
friend std::ostream& operator<< (std::ostream& out, const deque<U>& dq);

private:
size_type count; // Total number of items in the queue
node<T>* first;
node<T>* last;
};

#include "deque.template"

#endif

Using the above node header and dequeue header, I need to construct a dequeue class.

Explanation / Answer

package com;
public class DList<T> {
private DNode<T> header, trailer;
private int size;
public DList() {
size = 0;
header = new DNode<T>(null, null, null);
trailer = new DNode<T>(null, header, null);
header.setNext(trailer);
}
// utility methods
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
// give clients access to nodes, but not to the header or trailer
public DNode<T> getFirst() throws Exception {
if (isEmpty())
throw new Exception("Empty");
return header.getNext();
}
public DNode<T> getLast() throws Exception {
if (isEmpty())
throw new Exception("Empty");
return trailer.getPrev();
}
public DNode<T> getNext(DNode<T> v) throws Exception {
DNode<T> ans = v.getNext();
if (ans == null || ans == trailer)
throw new Exception("No such node");
return ans;
}
public DNode<T> getPrev(DNode<T> v) throws Exception {
DNode<T> ans = v.getPrev();
if (ans == null || ans == header)
throw new Exception("No such node");
return ans;
}
// methods to change the list
public void addBefore(T d, DNode<T> v) {
DNode<T> u = v.getPrev();
DNode<T> x = new DNode<T>(d, u, v);
u.setNext(x);
v.setPrev(x);
size++;
}
public void addAfter(T d, DNode<T> v) {
DNode<T> w = v.getNext();
DNode<T> x = new DNode<T>(d, v, w);
v.setNext(x);
w.setPrev(x);
size++;
}
public void addFirst(T d) {
addAfter(d, header);
}
public void addLast(T d) {
addBefore(d, trailer);
}
public T remove(DNode<T> v) throws Exception {
if (v == header || v == trailer)
throw new Exception("Sentinel");
DNode<T> u = v.getPrev();
DNode<T> w = v.getNext();
w.setPrev(u);
u.setNext(w);
size--;
return v.getData();
}
// LinkedList testing methods:
public String toString() {
String ans = "";
DNode<T> n = header;
ans += "(H)<-->";
do {
n = n.getNext();
if (n == trailer)
ans += "(T)";
else
ans += (n.getData() + "<-->");
} while (n != trailer);
return ans;
}
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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