This is a C++ problem that I have tried to complete, but there are
many areas that I'm not comfortable with. Please troubleshoot the
functions. I will be as detailed as possible.
The goal is to implement and test a class called List that uses a
linked list toolkit to create and manipulate a linked list. The
definitions are listed below. I will also show the linked list toolkit
that the implementation file must link to as well as what I have come
up with for the function implementations.
// FILE: list3.h //DEFINITIONS FOR FUNCTIONS TO BE IMPLEMENTED
// CLASS PROVIDED: List (a container class for a List of value_types,
// where each List may have a designated value_type called the current
value_type)
//
// TYPEDEF for the List class:
// typedef ____ value_type
// List::value_type is the data type of the value_types in the
List. 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.
//
// CONSTRUCTOR for the List class:
// List( )
// Postcondition: The List has been initialized as an empty List.
//
// MODIFICATION MEMBER FUNCTIONS for the List class:
// void start( )
// Postcondition: The first Item on the List becomes the current
Item
// (but if the List 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 on
the
// List, 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
List before
// the current Item. If there was no current Item, then the new
entry has
// been inserted at the front of the List. In either case, the
newly
// inserted Item is now the current Item of the List.
//
// void attach(const value_type& entry)
// Postcondition: A new copy of entry has been inserted in the
List after
// the current Item. If there was no current Item, then the new
entry has
// been attached to the end of the List. In either case, the newly
// inserted Item is now the current Item of the List.
//
// void remove_current( )
// Precondition: is_Item returns true.
// Postcondition: The current Item has been removed from the List,
and the
// Item after this (if there is one) is now the new current Item.
//
// CONSTANT MEMBER FUNCTIONS for the List class:
// size_t size( ) const
// Postcondition: The return value is the number of Item on the
List.
//
// 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 on the
List.
//
// VALUE SEMANTICS for the List class:
// Assignments and the copy constructor may be used with List
objects.
//
// DYNAMIC MEMORY USAGE by the List:
// If there is insufficient dynamic memory, then the following
functions call
// new_handler: The constructors, insert, attach, and the
// assignment operator.
#ifndef LIST3_H
#define LIST3_H
#include <stdlib.h> // Provides size_t
#include "link1.h" // Provides linked list toolkit
class List
{
public:
// TYPEDEF
typedef node::value_type value_type;
// CONSTRUCTORS and DESTRUCTOR
List( );
List(const List& source);
~List( );
// MODIFICATION MEMBER FUNCTIONS
void start( );
void advance( );
void insert(const value_type& entry);
void attach(const value_type& entry);
void remove_current( );
void operator =(const List& source);
// CONSTANT MEMBER FUNCTIONS
size_t size( ) const { return many_nodes; }
bool is_Item( ) const { return (cursor != NULL); }
value_type current( ) const;
private:
node *head_ptr;
node *tail_ptr;
size_t many_nodes;
node *cursor;
node *precursor;
};
#endif
//THIS IS WHAT NEEDS TO BE IMPLEMENTED. I’M HAVING SOME “ISSUES” WITH
//THESE.
/* FILE: list3.cpp
IMPLEMENTS: List class(see list3.h for documentation)
INVARIANT for the List class:
1. The items in the list are stored in a linked list.
2. The head pointer of the list is stored in the member variable
head_ptr.
3. The tail pointer of the list is stored in the member variable
tail_ptr.
4. The current item of the linked list is stored in the member
variable cursor.
5. The item before the current item of the linked list is stored in
the member variable precursor.
6. The total number of items in the list is stored in the member
variable many_nodes.
*/
#include <cassert> // Provides assert
#include <cstdlib> // Provides NULL and size_t
#include "list3.h"
#include "link1.cpp" //LINKED LIST TOOLKIT
//Constructors and destructor
List::List()
{
head_ptr=NULL;
tail_ptr=NULL;
many_nodes=0;
cursor=NULL;
precursor=NULL;
}
List::List(const List& source) //Copy constructor
{
if(source.cursor==NULL)
{
list_copy(source.head_ptr, head_ptr, tail_ptr);
precursor=NULL;
cursor=NULL;
}
if(source.cursor==source.head_ptr)
{
list_copy(source.head_ptr, head_ptr, tail_ptr);
precursor=NULL;
cursor=head_ptr;
}
//I’M NOT SURE HOW TO USE THE PIECE FUNCTION AT THIS POINT
}
List::~List() //Destructor
{
list_clear(head_ptr);
many_nodes=0;
}
//Modification member functions
void List::start()
{
cursor=head_ptr;
precursor=head_ptr;
tail_ptr=head_ptr;
}
void List::advance()
{
assert(is_Item());
if(head_ptr==NULL)
cursor=head_ptr;
cursor=cursor->link();
precursor=precursor->link();
}
void List::insert(const value_type& entry)
{
precursor=cursor;
cursor=cursor->link();
precursor->link()=cursor;
if(cursor->link()==NULL)
tail_ptr=cursor;
list_insert(precursor, entry);
}
void List::attach(const value_type& entry)
{
precursor=cursor;
cursor=cursor->link();
precursor->link()=cursor;
if(cursor->link()==NULL)
tail_ptr=cursor;
if(head_ptr==NULL)
cursor->link()=tail_ptr;
list_insert(cursor->link(), entry);
}
void List::remove_current()
{
assert(is_Item());
if(cursor==head_ptr)
{
list_head_remove(head_ptr);
tail_ptr=NULL;
}
else if(cursor!=head_ptr && cursor!=NULL)
{
list_remove(cursor);
cursor=cursor->link();
precursor=precursor->link();
}
else if(cursor==NULL)
{
size_t i=0;
cursor=precursor;
i=list_length(head_ptr);
//list_remove(i);
}
}
void List::operator =(const List& source)
{
if(source.cursor==NULL)
{
list_copy(source.head_ptr, head_ptr, tail_ptr);
precursor=NULL;
cursor=NULL;
}
if(source.cursor==source.head_ptr)
{
list_copy(source.head_ptr, head_ptr, tail_ptr);
precursor=NULL;
cursor=head_ptr;
}
//NOT SURE HOW TO USE PIECE FUNCTION HERE
}
//Constant member functions
List::value_type List::current() const
{
assert(is_Item());
return cursor->data();
}
I will provide the .h and .cpp files for the linked list toolkit that
is used in conjunction with the implementation of the new class:
H
// PROVIDES: A toolkit of 10 functions for manipulating linked lists.
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 complete type definitions used by the toolkit are:
//
//
// TYPEDEF for node class:
// value_type may be any of the C++ built-in types (int, char,
etc.), or a class with a default
// constructor, an assignment operator, and a test for equality (x ==
y).
// CONSTRUCTOR for node class:
// node(const value_type& init_data, node* init_link)
// Post: The node contains the specified data and link. NOTE: The
default value of the data is
// provided by default constructor of value_type, the default value of
init_link is 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-constant version (where the
return value is node*) and
// a const version (where the return valuse is const node*)
//
// MEMBER FUNCTIONS:
// void set_data(const value_type& new_data)
// post: The node now contains the specified new data
// void set_link(node* new_link)
// post: The node now contains the specified new link
//
// value_type data() const;
// post: The return value is the data frem this node
// const node* link() const
//
// node* link()
// post: 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)
// node* list_search(node* head_ptr, const node::value_type& target)
// 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 member. If there is no such
node, the
// null pointer is returned. The list itself is unaltered.
//
// const node* list_locate(const node* head_ptr, size_t position)
// const node* list_locate(const node* head_ptr, size_t position)
// 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
//
// void list_piece(
// const node* start_ptr, const node* end_ptr, Node*& head_ptr,
Node*& tail_ptr)
// Precondition: start_ptr and end_ptr are pointers to nodes on
the same
// linked list, with the start_ptr node at or before the end_ptr
node.
// Postcondition: head_ptr and tail_ptr are the head and tail
pointers for
// a new linked list that contains the items from start_ptr to
end_ptr.
// The original list is unaltered.
//
// DYNAMIC MEMORY usage by the toolkit:
// If there is insufficient dynamic memory, then the following
functions call
// new_handler before any changes are made to the list that head_ptr
points
// to : list_head_insert, list_insert, list_copy, list_piece,
list_insert_at,
// list_copy_segment.
#ifndef LINK1_H
#define LINK1_H
#include <cstdlib> // Provides size_t
class node{
public:
//TYPEDEF:
typedef double value_type;
node(const value_type& init_data = value_type(), node*
init_link=NULL);
// MEMBER FUNCTIONS:
void set_data(const value_type& new_data);
void set_link(node* new_link);
value_type data() const;
const node* link() const;
node* link();
private:
value_type data_field;
node* link_field;
};
// FUNCTIONS in the linked list toolkit:
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);
const node* list_search(const node* head_ptr, const
node::value_type& target) ;
node* list_search(node* head_ptr, const node::value_type& target);
node* list_locate(node* head_ptr, size_t position);
const node* list_locate(const node* head_ptr, 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) ;
void list_piece(
const node* start_ptr, const node* end_ptr, node*& head_ptr,
node*& tail_ptr) ;
#endif
CPP
#include <cassert> // Provides assert
#include <cstdlib> // Provides NULL and size_t
#include "link1.h"
node::node(const value_type& init_data, node* init_link)
{
data_field = init_data;
link_field = init_link;
}
void node::set_data(const value_type& new_data)
{
data_field = new_data;
}
void node::set_link(node* new_link)
{
link_field = new_link;
}
node::value_type node::data() const
{
return data_field;
}
const node* node::link() const
{
return link_field;
}
node* node::link()
{
return link_field;
}
size_t list_length(node* head_ptr)
// Library facilities used: stdlib.h
{
node *cursor;
size_t answer;
answer = 0;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link)
answer++;
return answer;
}
void list_head_insert(node*& head_ptr, const node::value_type& entry)
{
head_ptr = new node (entry, head_ptr);
}
void list_insert(node* previous_ptr, const node::value_type& entry)
{
node* insert_ptr;
insert_ptr = new node;
insert_ptr->set_data(entry);
insert_ptr->set_link(previous_ptr->link());
previous_ptr->set_link(insert_ptr);
}
node* list_search(node* head_ptr, const node::value_type& target)
// Library facilities used: stdlib.h
{
node *cursor;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link())
if (target == cursor->data())
return cursor;
return NULL;
}
node* list_locate(node* head_ptr, size_t position)
// Library facilities used: assert.h, stdlib.h
{
node *cursor;
size_t i;
assert (0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != NULL); i++)
cursor = cursor->link();
return cursor;
}
const node* list_locate(const node* head_ptr, size_t position)
// Library facilities used: assert.h, stdlib.h
{
const node *cursor;
size_t i;
assert (0 < position);
cursor = head_ptr;
for (i = 1; (i < position) && (cursor != NULL); i++)
cursor = cursor->link();
return cursor;
}
void list_head_remove(node*& head_ptr)
{
node *remove_ptr;
remove_ptr = head_ptr;
head_ptr = head_ptr->link();
delete remove_ptr;
}
void list_remove(node* previous_ptr)
{
node *remove_ptr;
remove_ptr = previous_ptr->link();
previous_ptr->set_link(remove_ptr->link());
delete remove_ptr;
}
void list_clear(node*& head_ptr)
// Library facilities used: stdlib.h
{
while (head_ptr != NULL)
list_head_remove(head_ptr);
}
void list_copy(node* source_ptr, node*& head_ptr, node*& tail_ptr)
// Library facilities used: stdlib.h
{
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 the 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();
}
}
void list_piece(const node* start_ptr, const node* end_ptr, node*&
head_ptr, node*& tail_ptr)
// Library facilities used: stdlib.h
{
head_ptr = NULL;
tail_ptr = NULL;
// Handle the case of the empty list
if (start_ptr == NULL)
return;
// Make the head node for the newly created list, and put data in
it
list_head_insert(head_ptr, start_ptr->data());
tail_ptr = head_ptr;
if (start_ptr == end_ptr)
return;
// Copy the rest of the nodes one at a time, adding at the tail of
new list
for (start_ptr = start_ptr->link(); start_ptr != NULL; start_ptr =
start_ptr->link())
{
list_insert(tail_ptr, start_ptr->data());
tail_ptr = tail_ptr->link();
if (start_ptr == end_ptr)
return;
}
}
Thanks. Feel free to follow up with any questions. Please give
reasoning behind major ideas. I want to understand the corrections. |
