Review of C++ Input and Output
Node -- a dynamically allocated structure containing one or more
• data elements
• pointers to other nodes
Head & tail pointers
pointers within the class which contain the address of the first (head)
or the last (tail) node.
node * head_ptr;
node * tail_ptr;
NULL value in a pointer
indicates there is no node.
• The head_ptr and tail_ptr contain a null value, when the list is empty.
• The node pointer in the last node contains null to indicate the end of the list
Node Constructors
must initialize data and pointer fields.
Using pointers to reference node class functions.
method 1 -- dereference pointer.
(*head_ptr).data()
method 2 -- member selection operator.
*head_ptr->data()
const member functions
do not alter data.
const keyword and node pointers
node *p; // can point to different nodes and
// retrieve or alter node contents
// p-> data( ); p-> set_data(value);
const node *q; // can point to different nodes and
// only activate constant member functions
// q-> data( );
// it cannot be used to alter node contents
// q-> set_data(value) NOT ALLOWED
member functions returning a node pointer
provide a means of changing class contents
node * link() const { return link_field;}
returns an ordinary pointer which can later
be used to alter the node
node *p = head_ptr->link();
p->set_data(93.3);
const node pointers should only activate constant member functions.
Thus may need another version that returns a const *
const node * link() const { return link_field;}
system converts link_field to const node*
which cannot be later used to alter the node
const node *q = head_ptr->link();
node *r = q->link();
r->set_data(93.3); NOT ALLOWED
//-----------------------------------------------------------------------------------------------------
// node1.h (modified to work with Microsoft Visual C++ 6.0)
#ifndef NODESPACE
#define NODESPACE
#include // Provides size_t and NULL
namespace NodeSpace
{
class node
{
public:
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; }
// Member functions to set the data and link fields:
void set_data(const value_type& new_data) { data_field = new_data; }
void set_link(node* new_link) { link_field = new_link; }
// Constant member function to retrieve the current data:
value_type data( ) const { return data_field; }
// Two member functions to retreive the current link:
const node* link( ) const { return link_field; }
node* link( ) { return link_field; }
private:
value_type data_field;
node* link_field;
};
// FUNCTIONS for 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);
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, 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);
}
#endif
//-------------------------------------------------------------------------------------------------------
// FILE: node1.cpp
// linked list toolkit (see node1.h for documentation).
// INVARIANT for the node class:
// The data of a node is stored in data_field, and the link in link_field.
#include "node1.h"
#include // Provides assert
#include // Provides NULL and size_t
namespace NodeSpace
{
size_t list_length(const node* head_ptr)
// Library facilities used: cstdlib
{
const 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(entry, previous_ptr->link( ));
previous_ptr->set_link(insert_ptr);
}
node* list_search(node* head_ptr, const node::value_type& target)
// Library facilities used: cstdlib
{
node *cursor;
for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
if (target == cursor->data( ))
return cursor;
return NULL;
}
const node* list_search(const node* head_ptr,
const node::value_type& target)
// Library facilities used: cstdlib
{
const 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: cassert, cstdlib
{
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: cassert, cstdlib
{
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: cstdlib
{
while (head_ptr != NULL)
list_head_remove(head_ptr);
}
void list_copy(const node* source_ptr, node*& head_ptr, node*& 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 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( );
}
}
}
//-----------------------------------------------------------------------------
A Bag class implemented with linked lists, does not require
default capacity
reserve( ) function
// FILE: bag3.h
//
// bag::size_type keeps track of how many items are in a bag
//
#ifndef BAG3_H
#define BAG3_H
#include // Provides size_t and NULL
#include "node1.h" // Provides node class
namespace NodeSpace
{
class bag
{
public:
// TYPEDEFS
typedef size_t size_type;
// Bag value type will match node value type
typedef node::value_type value_type;
// CONSTRUCTORS and DESTRUCTOR
bag( );
bag(const bag& source);
~bag( );
// MODIFICATION MEMBER FUNCTIONS
size_type erase(const value_type& target);
bool erase_one(const value_type& target);
void insert(const value_type& entry);
void operator +=(const bag& addend);
void operator =(const bag& source);
// CONSTANT MEMBER FUNCTIONS
size_type size( ) const { return many_nodes; }
size_type count(const value_type& target) const;
value_type grab( ) const;
private:
node *head_ptr; // List head pointer
size_type many_nodes; // Number of nodes on the list
};
// NONMEMBER FUNCTIONS for the bag class:
bag operator +(const bag& b1, const bag& b2);
}
#endif
------------------------------------------------------------------------
// FILE: bag3.cpp
//
// INVARIANT for the bag ADT:
// 1. The items in the bag are stored on a linked list;
// 2. The head pointer of the list is stored in the member variable head_ptr;
// 3. The total number of items in the list is stored in the member variable
// many_nodes.
#include // Provides assert
#include // Provides NULL, rand, size_t
#include "node1.h" // Provides node and the linked list functions
#include "bag3.h"
namespace NodeSpace
{
bag::bag( )
// Library facilities used: cstdlib
{
head_ptr = NULL;
many_nodes = 0;
}
bag::bag(const bag& source)
// Library facilities used: node1.h
{
node *tail_ptr; // Needed for argument of list_copy
list_copy(source.head_ptr, head_ptr, tail_ptr);
many_nodes = source.many_nodes;
}
bag::~bag( )
// Library facilities used: node1.h
{
list_clear(head_ptr);
many_nodes = 0;
}
bag::size_type bag::count(const value_type& target) const
// Library facilities used: cstdlib, node1.h
{
size_type answer;
const node *cursor; // Use const node* since we don't change the nodes.
answer = 0;
cursor = list_search(head_ptr, target);
while (cursor != NULL)
{
// Each time that cursor is not NULL, we have another occurrence of
// target, so we add one to answer, and move cursor to the next
// occurrence of the target.
++answer;
cursor = cursor->link( );
cursor = list_search(cursor, target);
}
return answer;
}
bag::size_type bag::erase(const value_type& target)
// Library facilities used: cstdlib, node1.h
{
size_type answer = 0;
node *target_ptr;
target_ptr = list_search(head_ptr, target);
while (target_ptr != NULL)
{
// Each time target_ptr is not NULL, we have another occurrence
// of target. We remove this target using the same technique that
// was used in erase_one.
target_ptr->set_data( head_ptr->data( ) );
target_ptr = target_ptr->link( );
target_ptr = list_search(target_ptr, target);
list_head_remove(head_ptr);
--many_nodes;
++answer;
}
return answer;
}
bool bag::erase_one(const value_type& target)
// Library facilities used: cstdlib, node1.h
{
node *target_ptr;
target_ptr = list_search(head_ptr, target);
if (target_ptr == NULL)
return false; // target isn't in the bag, so no work to do
target_ptr->set_data( head_ptr->data( ) );
list_head_remove(head_ptr);
--many_nodes;
return true;
}
bag::value_type bag::grab( ) const
// Library facilities used: cassert, cstdlib, node1.h
{
size_type i;
const node *cursor; // Use const node* since we don't change the nodes.
assert(size( ) > 0);
i = (rand( ) % size( )) + 1;
cursor = list_locate(head_ptr, i);
return cursor->data( );
}
void bag::insert(const value_type& entry)
// Library facilities used: node1.h
{
list_head_insert(head_ptr, entry);
++many_nodes;
}
void bag::operator +=(const bag& addend)
// Library facilities used: cstdlib, node1.h
{
node *copy_head_ptr;
node *copy_tail_ptr;
if (addend.many_nodes > 0)
{
list_copy(addend.head_ptr, copy_head_ptr, copy_tail_ptr);
copy_tail_ptr->set_link( head_ptr );
head_ptr = copy_head_ptr;
many_nodes += addend.many_nodes;
}
}
void bag::operator =(const bag& source)
// Library facilities used: node1.h
{
node *tail_ptr; // Needed for argument to list_copy
if (this == &source)
return;
list_clear(head_ptr);
many_nodes = 0;
list_copy(source.head_ptr, head_ptr, tail_ptr);
many_nodes = source.many_nodes;
}
bag operator +(const bag& b1, const bag& b2)
{
bag answer;
answer += b1;
answer += b2;
return answer;
}
}
---------------------------------------------------
// FILE: bag3demo.cpp
// Demonstration program for the 3rd version of the bag (bag3.h and bag3.cxx).
// This is a the same as the demonstration program for bag1,
// except that we no longer need to check whether the bag reaches its
// capacity.
#include // Provides cout and cin
#include // Provides EXIT_SUCCESS
#include "bag3.h" // With Item defined as an int
using namespace std;
using namespace NodeSpace;
// PROTOTYPES for functions used by this demonstration program:
void get_ages(bag& ages);
// Postcondition: The user has been prompted to type in the ages of family
// members. These ages have been read and placed in the ages bag, stopping
// when the user types a negative number.
void check_ages(bag& ages);
// Postcondition: The user has been prompted to type in the ages of family
// members once again. Each age is removed from the ages bag when it is typed,
// stopping when the bag is empty.
int main( )
{
bag ages;
get_ages(ages);
check_ages(ages);
cout user_input;
if (ages.erase_one(user_input))
cout ................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- austin community college district start here get there
- static vs university of central florida
- computer science courses
- review of c input and output
- examples and exercises on linked lists
- c pointer exercises
- university of washington
- binary trees university of babylon
- si202 week 1
- home department of computer science
Related searches
- input and output calculator
- input and output table calculator
- java input and output stream
- java input and output file
- input and output equations
- input and output function math
- input and output math solver
- input and output equation
- input and output in math
- input and output equation calculator
- input and output tables
- input and output in java