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.

Google Online Preview   Download