The purpose of this program is to help reinforce container class concepts and linked list concepts in C++. Specifically, the task is to implement the sequence class using a linked list. You need to use the author's file sequence3.h to create your implementation file named sequence3.cpp. Please make your code as efficient and reusable as possible.

Please make sure code can pass any tests.

node1.h

//File: node1.h //This program provides the node class used in 5.2

// FILE: node1.h (part of the namespace main_savitch_5) // PROVIDES: A class for a node in a linked list and a collection of functions for // manipulating linked lists // // TYPEDEF for the node class: // Each node of the list contains a piece of data and a pointer to the next node. The // type of the data is defined as node::value_type in a typedef statement. The value_type // may be any of the C++ built-in types (int, char, etc.), or a class with a default constructor, // a copy constructor, an assignment operator, and a test for equality. // // CONSTRUCTOR for the node class: // node(const value_type& init_data, node* init_link) // Postcondition: The node contains the specified data and link. // NOTE: The init_data parameter has a default value that is obtained from the default // constructor of the value_type. In the ANSI/ISO Standard, this notation is also allowed // for the built-in types, providing a default value of zero. The init_link has a default // value of NULL. // NOTE: // Some of the functions have a return value that is a pointer to a node. Each of these // functions comes in two versions: a non-const version (where the return value is ) // and a const version (where the return value is ). // EXAMPLES: // const node *c; // c->link( ) activates the const version of link // list_search(c, ... calls the const version of list_search // node *p; // p->link( ) activates the non-const version of link // list_search(p, ... calls the non-const version of list_search // // MEMBER FUNCTIONS for the node class: // void set_data(const value_type& new_data // Postcondition: The node now contains the specified new data. // // void set_link(node* new_link) // Postcondition: The node now contains the specified new link. // // value_type data() const // Postcondition: The return value is the data from this node. // // <----- const version // and // <----- non-const version // See the previous note about the const version and non-const versions. // Postcondition: The return value is the link from this node. // // FUNCTIONS in the linked-list toolkit: // size_t list_length(const node* head_ptr) // Precondition: head_ptr is the head pointer of a linked list. // Postcondition: The value returned is the number of nodes in the linked list. // // void list_head_insert(node*& head_ptr, const node:: value_type& entry) // Precondition: head_ptr is the head pointer of a linked list. // Postcondition: A new node containing the given entry has been added at the head of // the linked list; head_ptr now points to the head of the new, longer linked list. // // void list_insert(node* previous_ptr, const node:: value_type& entry) // Precondition: previous_ptr points to a node in a linked list. // Postcondition: A new node containing the given entry has been added after the node // that previous_ptr points to. // // const node* list_search (const node* head_ptr, const node::value_type& target) // and // node* list_search(node* head_ptr, const node::value_type& target) // See the previous note about the const version and non-const versions. // Precondition: head_ptr is the head pointer of a linked list. // Postcondition: The pointer returned points to the first node containing the specified // target in its data field. If there is no such node, the null pointer is returned. // // const node* list_locate(const node* head_ptr, size_t position) // and // node* list_locate(node* head_ptr, size_t position) // See the previous note about the const version and non-const versions. // Precondition: head_ptr is the head pointer of a linked list, and position > 0. // Postcondition: The pointer returned points to the node at the specified position in the // list. (The head node is position 1, the next node is position 2, and so on.) If there is no // such position, then the null pointer is returned. // // void list_head_remove(node*& head_ptr) // Precondition: head_ptr is the head pointer of a linked list, with at least one node. // Postcondition: The head node has been removed and returned to the heap; // head_ptr is now the head pointer of the new, shorter linked list. // // void list_remove(node* previous_ptr) // Precondition: previous_ptr points to a node in a linked list, and this is not the tail node of // the list. // Postcondition: The node after previous_ptr has been removed from the linked list. // // void list_clear(node*& head_ptr) // Precondition: head_ptr is the head pointer of a linked list. // Postcondition: All nodes of the list have been returned to the heap, and the head_ptr is // now NULL. // // void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr) // Precondition: source_ptr is the head pointer of a linked list. // Postcondition: head_ptr and tail_ptr are the head and tail pointers for a new list that // contains the same items as the list pointed to by source_ptr. // // DYNAMIC MEMORY usage by the functions: // If there is insufficient dynamic memory, then the following functions throw bad_alloc: // the node constructor, list_head_insert, list_insert, list_copy.

#ifndef MAIN_SAVITCH_NODE1_H #define MAIN_SAVITCH_NODE1_H #include // Provides size_t and NULL

namespace main_savitch_5 { class node { public: // TYPEDEF typedef double value_type; // CONSTRUCTOR node(const value_type& init_data=value_type( ), node* init_link=NULL) { data_field = init_data; link_field = init_link; } // MODIFICATION MEMBER FUNCTIONS node* link( ) { return link_field; } void set_data(const value_type& new_data) { data_field = new_data; } void set_link(node* new_link) { link_field = new_link; } // CONST MEMBER FUNCTIONS value_type data( ) const { return data_field; } const node* link( ) const { return link_field; } private: value_type data_field; node *link_field; }; // FUNCTIONS for the linked-list toolkit std::size_t list_length(const node* head_ptr); void list_head_insert(node*& head_ptr, const node::value_type& entry); void list_insert(node* previous_ptr, const node::value_type& entry); node* list_search(node* head_ptr, const node::value_type& target); const node* list_search (const node* head_ptr, const node::value_type& target); node* list_locate(node* head_ptr, std::size_t position); const node* list_locate(const node* head_ptr, std::size_t position); void list_head_remove(node*& head_ptr); void list_remove(node* previous_ptr); void list_clear(node*& head_ptr); void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr); }

#endif

sequence3.h

// FILE: sequence3.h // CLASS PROVIDED: sequence (part of the namespace main_savitch_5) // This is the header file for the project described in Section 5.4 // of "Data Structures and Other Objects Using C++" // This is called "sequence3" because some students already implemented // sequence1 (with a fixed array) and sequence2 (with a dynamic array). // // TYPEDEFS and MEMBER CONSTANTS for the sequence class: // typedef ____ value_type // sequence::value_type is the data type of the items in the sequence. It // may be any of the C++ built-in types (int, char, etc.), or a class with a // default constructor, an assignment operator, and a copy constructor. // // typedef ____ size_type // sequence::size_type is the data type of any variable that keeps track of // how many items are in a sequence. // // CONSTRUCTOR for the sequence class: // sequence( ) // Postcondition: The sequence has been initialized as an empty sequence. // // MODIFICATION MEMBER FUNCTIONS for the sequence class: // void start( ) // Postcondition: The first item on the sequence becomes the current item // (but if the sequence is empty, then there is no current item). // // void advance( ) // Precondition: is_item returns true. // Postcondition: If the current item was already the last item in the // sequence, then there is no longer any current item. Otherwise, the new // current item is the item immediately after the original current item. // // void insert(const value_type& entry) // Postcondition: A new copy of entry has been inserted in the sequence // before the current item. If there was no current item, then the new entry // has been inserted at the front of the sequence. In either case, the newly // inserted item is now the current item of the sequence. // // void attach(const value_type& entry) // Postcondition: A new copy of entry has been inserted in the sequence after // the current item. If there was no current item, then the new entry has // been attached to the end of the sequence. In either case, the newly // inserted item is now the current item of the sequence. // // void remove_current( ) // Precondition: is_item returns true. // Postcondition: The current item has been removed from the sequence, and // the item after this (if there is one) is now the new current item. // // CONSTANT MEMBER FUNCTIONS for the sequence class: // size_type size( ) const // Postcondition: The return value is the number of items in the sequence. // // bool is_item( ) const // Postcondition: A true return value indicates that there is a valid // "current" item that may be retrieved by activating the current // member function (listed below). A false return value indicates that // there is no valid current item. // // value_type current( ) const // Precondition: is_item( ) returns true. // Postcondition: The item returned is the current item in the sequence. // // VALUE SEMANTICS for the sequence class: // Assignments and the copy constructor may be used with sequence objects. #ifndef MAIN_SAVITCH_SEQUENCE3_H #define MAIN_SAVITCH_SEQUENCE3_H #include  // Provides size_t #include "node1.h" // Provides node class namespace main_savitch_5 { class sequence { public: // TYPEDEFS and MEMBER CONSTANTS typedef double value_type; typedef std::size_t size_type; // CONSTRUCTORS and DESTRUCTOR sequence( ); sequence(const sequence& source); ~sequence( ); // MODIFICATION MEMBER FUNCTIONS void start( ); void advance( ); void insert(const value_type& entry); void attach(const value_type& entry); void operator =(const sequence& source); void remove_current( ); // CONSTANT MEMBER FUNCTIONS size_type size( ) const { return many_nodes; } bool is_item( ) const { return (cursor != NULL); } value_type current( ) const; private: node *head_ptr; node *tail_ptr; node *cursor; node *precursor; size_type many_nodes; }; } #endif