The goal of this assignment is to reinforce using linear data structures in C++.

ID: 3593043 • Letter: T

Question

The goal of this assignment is to reinforce using linear data structures in C++. Specifically, create a dynamic (linked list) implementation of a deque using the provided header file.

I have the code, but the stuff I would like to print in my main file is not printing. Can someone take a look and see why only my first two cout statements print, but none of the rest is printing? The code is below,

main.cpp
----------------------------------------------------------

#include "deque.h"
#include <iostream>
#include <cassert>

int main() {
 std::cout << "Will create two blank deques." << std::endl;
 deque<int>* di;
 std::cout << "Created a blank deque and performing a few basic tasks: ";
 deque<int>* di_empty;
 int i;
 int a[] = {8,7,6,21,28,35,42,49,56,63};
 int b[] = {0,1,4,9,16,25,36,49,64,81};
 di->push_front(7);
 di->push_back(6);
 di->push_front(8);
 for (i = 3; i < 10; i++)
 di->push_back(i * 7);
 assert(di->back() == a[9] && di->front() == a[0]);
 std::cout << "PASSED." << std::endl;

std::cout << "Will now create a new deque using default copy constructor and passing original deque as parameter: ";
 deque<int>* di2(di);
 assert(di2->back() == a[9] && di2->front() == a[0]);
 std::cout << "PASSED." << std::endl;
 std::cout << "Updating the new deque using pop_back: ";
 di2->pop_back();
 assert(di2->back() == a[8]);
 std::cout << "PASSED." << std::endl;
 std::cout << "Verifying original is unchanged: ";
 assert(di->back() == a[9]);
 std::cout << "PASSED." << std::endl;

std::cout << "Will now use default assignment operator to assign empty deque to original deque: ";
 di = di_empty;
 assert(di->empty());
 std::cout << "PASSED." << std::endl;
 std::cout << "Will now fill deque using push_back: ";
 for (i = 0; i < 10; i++)
 di->push_back(i * i);
 assert(di->front() == b[0] && di->back() == b[9]);
 std::cout << "PASSED." << std::endl;
 std::cout << "Removing two items using pop_front: ";
 di->pop_front();
 di->pop_front();
 assert(di->front() == b[2]);
 std::cout << "PASSED." << std::endl;

std::cout << "Creating a deque of doubles to verify template: ";
 deque<double> dd;
 assert(dd.empty());
 std::cout << "PASSED." << std::endl;
 std::cout << "Will now fill deque using push_front: ";
 for (i = 0; i < 10; i++)
 dd.push_back(i / 13);
 std::cout << "PASSED." << std::endl;
 return 0;
}
-----------------------------------------------------------------------------------
deque.template
----------------------------------------------
#include <cstdlib>
#include "node2.h"

template <typename T>
deque<T>::deque() {
 count = 0;
 first = NULL;
 last = NULL;
}

template <typename T>
deque<T>::~deque() {
list_clear(first);
}

template <typename T>
deque<T>::deque(const deque<T>& dq) {
list_copy(dq.first, first, last);
count = dq.count;
}

template <typename T>
deque<T>& deque<T>::operator = (const deque<T>& dq) {
 if (first == dq.first)
 return *this;
 list_clear(first);
 list_copy(dq.first, first, last);
 count = dq.count;
 return *this;
}

template <typename T>
T& deque<T>::front() {
assert(count != 0);
return first->data();
}

template <typename T>
T deque<T>::front() const {
assert(count != 0);
return first->data();
}

template <typename T>
T& deque<T>::back() {
assert(count != 0);
return last->data();
}

template <typename T>
T deque<T>::back() const {
assert(count != 0);
return last->data();
}

template <typename T>
void deque<T>::push_front(const T& entry) {
list_head_insert(first, entry);
count++;
}

template <typename T>
void deque<T>::push_back(const T& entry) {
 assert(!empty());
 node<T>* ptr;
 ptr = last;
 list_insert(ptr, entry);
 last = ptr->link();
 count++;
}

template <typename T>
void deque<T>::pop_front() {
 assert(!empty());
 list_head_remove(first);
 count--;
}

template <typename T>
void deque<T>::pop_back() {
 assert(!empty());
 node<T>* ptr;
 ptr = first;
 while (ptr->link() != last) {
 ptr = ptr->link();
 }
 list_remove(ptr);
 last = ptr;
 count--;
}

template <typename T>
typename deque<T>::size_type deque<T>::size() const {
return count;
}

template <typename T>
bool deque<T>::empty() const {
return count == 0;
}

template <typename U>
bool operator == (const deque& dq1, const deque& dq2) {
 if (dq1.count != dq2.count || dq1.first != dq2.first || dq1.last != dq2.last)
 return false;
 else {
 typename deque::size_type i;
 node* ptr1, ptr2;
 ptr1 = dq1.first;
 ptr2 = dq2.first;
 for (i = 0; i < dq1.count; i++) {
 if (ptr1->data != ptr2->data())
 return false;
 else {
 ptr1 = ptr1->link();
 ptr2 = ptr2->link();
 }
 }
 }
 return true;
}

template <typename U>
std::ostream& operator<< (std::ostream& out, const deque& dq) {
 typename deque::size_type i;
 node* ptr;
 i = 0;
 ptr = dq.first;
 while (i < dq.count) {
 out << ptr->data() << " ";
 ptr = ptr->link();
 i++;
 }
 return out;
}
---------------------------------------------------------------------------------
deque.h
----------------------------------------------
#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& dq1, const deque& dq2);

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

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

#include "deque.template"

#endif
----------------------------------------------------------------------------------------------
node2.h
---------------------------------------------------
#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
---------------------------------------------------------------------------------------
node2.template
------------------------------------------------
#include <cassert> // Provides assert
#include <cstdlib> // Provides NULL and size_t

namespace main_savitch_6B
{
 template <class Item>
 void list_clear(node<Item>*& head_ptr)
 // Library facilities used: cstdlib
 {
 while (head_ptr != NULL)
 list_head_remove(head_ptr);
 }

 template <class Item>
 void list_copy(
 const node<Item>* source_ptr,
 node<Item>*& head_ptr,
 node<Item>*& tail_ptr
 )
 // Library facilities used: cstdlib
 {
 head_ptr = NULL;
 tail_ptr = NULL;

 // Handle the case of the empty list
 if (source_ptr == NULL)
 return;

 // Make the head node for the newly created list, and put data in it
 list_head_insert(head_ptr, source_ptr->data( ));
 tail_ptr = head_ptr;

 // Copy rest of the nodes one at a time, adding at the tail of new list
 source_ptr = source_ptr->link( );
 while (source_ptr != NULL)
 {
 list_insert(tail_ptr, source_ptr->data( ));
 tail_ptr = tail_ptr->link( );
 source_ptr = source_ptr->link( );
 }
 }

 template <class Item>
 void list_head_insert(node<Item>*& head_ptr, const Item& entry)
 {
 head_ptr = new node<Item>(entry, head_ptr);
 }

 template <class Item>
 void list_head_remove(node<Item>*& head_ptr)
 {
 node<Item> *remove_ptr;

 remove_ptr = head_ptr;
 head_ptr = head_ptr->link( );
 delete remove_ptr;
 }

 template <class Item>
 void list_insert(node<Item>* previous_ptr, const Item& entry)
 {
 node<Item> *insert_ptr;

 insert_ptr = new node<Item>(entry, previous_ptr->link( ));
 previous_ptr->set_link(insert_ptr);
 }

 template <class Item>
 std::size_t list_length(const node<Item>* head_ptr)
 // Library facilities used: cstdlib
 {
 const node<Item> *cursor;
 std::size_t answer;

 answer = 0;
 for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
 ++answer;

 return answer;
 }

 template <class NodePtr, class SizeType>
 NodePtr list_locate(NodePtr head_ptr, SizeType position)
 // Library facilities used: cassert, cstdlib
 {
 NodePtr cursor;
 SizeType i;

 assert(0 < position);
 cursor = head_ptr;
 for (i = 1; (i < position) && (cursor != NULL); ++i)
 cursor = cursor->link( );
 return cursor;
 }

 template <class Item>
 void list_remove(node<Item>* previous_ptr)
 {
 node<Item> *remove_ptr;

 remove_ptr = previous_ptr->link( );
 previous_ptr->set_link(remove_ptr->link( ));
 delete remove_ptr;
 }

 template <class NodePtr, class Item>
 NodePtr list_search(NodePtr head_ptr, const Item& target)
 // Library facilities used: cstdlib
 {
 NodePtr cursor;

 for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
 if (target == cursor->data( ))
 return cursor;
 return NULL;
 }
}

Explanation / Answer