Google Answers Logo
View Question
 
Q: Intermediate C++ Troubleshooting - Linked List Function Implementation ( Answered 5 out of 5 stars,   2 Comments )
Question  
Subject: Intermediate C++ Troubleshooting - Linked List Function Implementation
Category: Computers > Programming
Asked by: martim07-ga
List Price: $30.00
Posted: 28 Feb 2003 07:39 PST
Expires: 30 Mar 2003 07:39 PST
Question ID: 168353
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 it’s 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
Answer  
Subject: Re: Intermediate C++ Troubleshooting - Linked List Function Implementation
Answered By: studboy-ga on 28 Feb 2003 10:50 PST
Rated:5 out of 5 stars
 
Please give this a try:
Hi, your answers look fine.  Here's the solution you can compare to--
please try to compile these once:

void list_piece(Node* start_ptr, 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;
    }
}

size_t list_occurrences(Node* head_ptr, const Node::Item& target)
{
    size_t answer = 0;

    for (head_ptr = list_search(head_ptr, target);
	 head_ptr != NULL;
	 head_ptr = list_search(head_ptr->link, target))
	answer++;
    
    return answer;
}

void list_insert_at(Node*& head_ptr, const Node::Item& entry, size_t
position)
{
    assert(position > 0);
    Node *precursor;
    
    if (position == 1)
	list_head_insert(head_ptr, entry);
    else
    {
	precursor = list_locate(head_ptr, position-1);
	assert(precursor != NULL);
	list_insert(precursor, entry);
    }
}

Node::value_type list_remove_at(Node*& head_ptr, size_t position)
{
    assert(position > 0);
    Node *precursor;
    Node::value_type answer;
    
    if (position == 1)
    {
	assert(head_ptr != NULL);
	answer = head_ptr->data;
	list_head_remove(head_ptr);
    }
    else
    {
	precursor = list_locate(head_ptr, position-1);
	assert(precursor != NULL);
	assert(precursor->link != NULL);
	answer = precursor->link->data;
	list_remove(precursor);
    }
    return answer;
}

Node* list_copy_segment(Node* head_ptr, size_t start, size_t finish)
{
    Node *start_ptr;
    Node *finish_ptr;
    Node *new_head;
    Node *new_tail;
    
    assert(start <= finish);
    start_ptr = list_locate(head_ptr, start);
    assert(start_ptr != NULL);
    finish_ptr = list_locate(start_ptr, finish-start+1);
    assert(finish_ptr != NULL);
    list_piece(start_ptr, finish_ptr, new_head, new_tail);
    return new_head;
}

Const Node* list_copy_segment(Node* head_ptr, size_t start, size_t
finish)
{
    Node *start_ptr;
    Node *finish_ptr;
    Node *new_head;
    Node *new_tail;
    
    assert(start <= finish);
    start_ptr = list_locate(head_ptr, start);
    assert(start_ptr != NULL);
    finish_ptr = list_locate(start_ptr, finish-start+1);
    assert(finish_ptr != NULL);
    list_piece(start_ptr, finish_ptr, new_head, new_tail);
    return new_head;
}

Request for Answer Clarification by martim07-ga on 01 Mar 2003 11:59 PST
Hi, thanks for the tips. It looks good, but there are some errors that
I've encountered:

in list_remove_at, line answer=head_ptr->data; returns error: C2440
'=' cannot convert from double(_thiscall node::*)(void) const to
double

in list_remove_at line answer=precursor->link->data returns error
C2227: left of data must point to class/struct union

in const node* list_copy segment line
start_ptr=list_locate(head_ptr,start) returns error C2440 cannot
convert from const class node* to class node*

in const node* list_copy_segment line calling list_piece returns error
C2664 'list_piece' cannot convert parameter 3 from 'const class node*'
to 'class node*&'

Any ideas on these would be appreciated.

Clarification of Answer by studboy-ga on 01 Mar 2003 12:29 PST
Hi

Can you give me the entire package so I can compile it?

try casting:

Node::value_type list_remove_at(Node*& head_ptr, size_t position) 
{ 
    assert(position > 0); 
    Node *precursor; 
    Node::value_type answer; 
     
    if (position == 1) 
    { 
 assert(head_ptr != NULL); 
 answer = head_ptr->data; 
 list_head_remove(head_ptr); 
    } 
    else 
    { 
 precursor = list_locate(head_ptr, position-1); 
 assert(precursor != NULL); 
 assert(precursor->link != NULL); 
 answer = (Node::value_type)precursor->link->data; 
 list_remove(precursor); 
    } 
    return answer; 
} 



Const Node* list_copy_segment(Const Node* head_ptr, size_t start, size_t 
finish) 
{  
    Node *start_ptr;  
    Node *finish_ptr;  
    Const Node *new_head;  
    Node *new_tail;  
      
    assert(start <= finish);  
    start_ptr = list_locate(head_ptr, start);  
    assert(start_ptr != NULL);  
    finish_ptr = list_locate(start_ptr, finish-start+1);  
    assert(finish_ptr != NULL);  
    list_piece(start_ptr, finish_ptr, new_head, new_tail);  
    return new_head;  
}

Request for Answer Clarification by martim07-ga on 02 Mar 2003 11:03 PST
Here is cpp file:


#include <cassert>    // Provides assert
#include <cstdlib>    // Provides NULL and size_t
#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*& 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;
    }
}


size_t list_occurrences(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; 

}

void list_insert_at(node*& head_ptr, const node::value_type& entry,
size_t position)
{
	 assert(position>0);
	 node* precursor;

	 if(position==1)
		 list_head_insert(head_ptr,entry);
	 else
	 {
		 precursor=list_locate(head_ptr, position-1);
		 assert(precursor!=NULL);
		 list_insert(precursor, entry);
	 }
}



node::value_type list_remove_at(node*& head_ptr, size_t position)
{
     assert(position>0);
	 node* precursor;
	 node::value_type answer;
	 

	 if(position==1)
	 {
		 assert(head_ptr!=NULL); 
		 answer=head_ptr->data;
		 list_head_remove(head_ptr);
	 }
	 else
	 {
		 precursor=list_locate(head_ptr, position-1);
		 assert(precursor!=NULL);
		 assert(precursor->link!=NULL);
		 answer=(node::value_type)precursor->link->data;
		 list_remove(precursor);
	 }
	 return answer;
}

node* list_copy_segment(node* head_ptr, size_t start, size_t finish)
{
	node* start_ptr;
	node* finish_ptr;
	const node* new_head;
	node* new_tail;

	assert(start<=finish);
	start_ptr=list_locate(head_ptr,start);
	assert(start_ptr!=NULL);
	finish_ptr=list_locate(start_ptr,(finish-start)+1);
	assert(finish_ptr!=NULL);
	list_piece(start_ptr,finish_ptr,new_head,new_tail);
	return new_head;
 
}

const node* list_copy_segment(const node* head_ptr, size_t start,
size_t finish)
{
	
    node* start_ptr;
	node* finish_ptr;
	const node* new_head;
	node* new_tail;

	assert(start<=finish);
	start_ptr=list_locate(head_ptr,start);
	assert(start_ptr!=NULL);
	finish_ptr=list_locate(start_ptr,(finish-start)+1);
	assert(finish_ptr!=NULL);
	list_piece(start_ptr,finish_ptr,new_head,new_tail);
	return new_head;
	
}

Here is .h:

#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); 
    const node* list_locate(const 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) ;
    
	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

Clarification of Answer by studboy-ga on 02 Mar 2003 22:43 PST
Thanks.  Here it is--this will compile:

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;
    }
}


size_t list_occurrences(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;

}

void list_insert_at(node*& head_ptr, const node::value_type& entry,
size_t position)
{
  assert(position>0);
  node* precursor;

  if(position==1)
   list_head_insert(head_ptr,entry);
  else
  {
   precursor=list_locate(head_ptr, position-1);
   assert(precursor!=NULL);
   list_insert(precursor, entry);
  }
}



node::value_type list_remove_at(node*& head_ptr, size_t position)
{
  assert(position>0);
  node* precursor;
  node::value_type answer;


  if(position==1)
  {
   assert(head_ptr!=NULL);
   answer=head_ptr->data();
   list_head_remove(head_ptr);
  }
  else
  {
   precursor=list_locate(head_ptr, position-1);
   assert(precursor!=NULL);
   assert(precursor->link() != NULL);
   answer=precursor->link()->data();
   list_remove(precursor);
  }
  return answer;
}

node* list_copy_segment(node* head_ptr, size_t start, size_t finish)
{
 const node* start_ptr;
 const node* finish_ptr;
 node* new_head;
 node* new_tail;

 assert(start<=finish);
 start_ptr=list_locate(head_ptr,start);
 assert(start_ptr!=NULL);
 finish_ptr=list_locate(start_ptr,(finish-start)+1);
 assert(finish_ptr!=NULL);
 list_piece(start_ptr,finish_ptr,new_head,new_tail);
 return new_head;

}

const node* list_copy_segment(const node* head_ptr, size_t start,
size_t finish)
{

 const node* start_ptr;
 const node* finish_ptr;
 node* new_head;
 node* new_tail;

 assert(start<=finish);
 start_ptr=list_locate(head_ptr,start);
 assert(start_ptr!=NULL);
 finish_ptr=list_locate(start_ptr,(finish-start)+1);
 assert(finish_ptr!=NULL);
 list_piece(start_ptr,finish_ptr,new_head,new_tail);
 return new_head;

}
martim07-ga rated this answer:5 out of 5 stars
Exceptional attention to detail and unsurpassed response time.

Comments  
Subject: Re: Intermediate C++ Troubleshooting - Linked List Function Implementation
From: studboy-ga on 28 Feb 2003 10:54 PST
 
Slight typo:

Const Node* list_copy_segment(Node* head_ptr, size_t start, size_t
finish)
{ 
    Node *start_ptr; 
    Node *finish_ptr; 
    Const Node *new_head; 
    Node *new_tail; 
     
    assert(start <= finish); 
    start_ptr = list_locate(head_ptr, start); 
    assert(start_ptr != NULL); 
    finish_ptr = list_locate(start_ptr, finish-start+1); 
    assert(finish_ptr != NULL); 
    list_piece(start_ptr, finish_ptr, new_head, new_tail); 
    return new_head; 
}
Subject: Re: Intermediate C++ Troubleshooting - Linked List Function Implementation
From: studboy-ga on 03 Mar 2003 17:13 PST
 
Thanks martim07-ga!  Glad I can help!

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy