This is a C++ project that I have mainly completed, but there are some
areas that I'm unsure on. I will be as detailed as possible.
My problems are with the five final functions I am implementing for
this linked list toolkit. The function definitions are all provided in
the header file that will follow below.
FILE: linkplus.h
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 value 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 from 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)
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 from start_ptr to
end_ptr. The original list is unaltered.
Size_t list_occurrences(const node* head_ptr, const node::value_type&
target)
Precondition: head_ptr is the head pointer of a linked list.
Postcondition: The return value is the count of the number of times
target appears as the data portion of a node on the linked list.
Void list_insert_at(node*& head_ptr,const node::value_type& entry,
size_t position)
Precondition: head_ptr is the head pointer of a linked list, and
position > 0 and position <= list_length(head_ptr)+1.
Postcondition: A new node has been added to the linked list with entry
as the data. The new node occurs at the specified position in the
list. (The head node is position 1, the next node is position 2, and
so on.) Any nodes that used to be after this specified position have
been shifted to make room for the one new node.
Node::value_type list_remove_at(node*& head_ptr, size_t position)
Precondition: head_ptr is the head pointer of a linked list, and
position > 0 and position <= list_length(head_ptr).
Postcondition: The node at the specified position has been removed
from the linked list and the function has returned a copy of the data
from the removed node. (The head node is position 1, the next node is
position 2, and so on).
Node* list_copy_segment(const node* head_ptr, size_t start, size_t
finish)
Const node* list_copy_segment(const node* head_ptr, size_t start,
size_t finish)
Precondition: head_ptr is the head pointer of a linked list, and (1 <=
start) and (start <= finish) and (finish <= list_length(head_ptr).
Postcondition: The value returned is the head pointer for a new list
that contains copies of the items from the start position to the
finish position in the list that head_ptr points to. (The head node is
position one, the next node is position two, and so on). The list
pointed to by head_ptr is unchanged.
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.
#ifnded LINK1_H
#define LINK1_H
#include <cstlib> //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);
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);
Size_t list_occurrences(const node* head_ptr, const node::value_type&
target);
Void list_insert_at(node*& head_ptr,const node::value_type& entry,
size_t position);
Node::value_type list_remove_at(node*& head_ptr, size_t position);
Node* list_copy_segment(node* head_ptr, size_t start, size_t finish);
Const node* list_copy_segment(const node* head_ptr, size_t start,
size_t finish);
#endif
FILE: linkplus.cpp
IMPLEMENTS: The 14 functions of the expanded linked list toolkit.
#include<cassert>
#include<cstdlib>
#include linkplus.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* previous_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* 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();
}
}
//PROBLEMS START HERE
//I HAVE FINALLY GOTTEN THE PIECE FUNCTION TO COMPILE, IT SEEMS TO BE
WORKING -// SEE WHAT YOU THINK
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 the 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;
}
}
//FOR THE OCCURENCES FUNCTION, THIS IS WHAT I HAVE. ALSO SEEMS TO BE
OKAY
size_t list_occurences(const node* head_ptr, const node::value_type&
target)
{
const node* cursor
size_t answer=0;
cursor=head_ptr;
if(cursor==NULL)
return 0;
for(cursor=head_ptr; cursor!=NULL; cursor=cursor->link())
{
if(target==cursor->data())
++answer;
}
return answer;
}
}
//FOR THE REST I HAVE RUN OUT OF TIME, PLEASE PROVIDE SOME TIPS ON
//HOW TO BEGIN IMPLEMENTATION
void list_insert_at(node*& head_ptr, const node::value_type& entry,
size_t position)
{
//TO BE IMPLEMENTED
}
node::value_type list_remove_at(node*& head_ptr, size_t position)
{
//TO BE IMPLEMENTED
}
node* list_copy_segment(node* head_ptr, size_t start, size_t finish)
{
//TO BE IMPLEMENTED
}
const node* list_copy_segment(const node* head_ptr, size_t start,
size_t finish)
{
//TO BE IMPLEMENTED
}
Thank You |