Tonight, we came to grips with Homework #7. It's full description is as follows:
Create a template class list<T> to represent a generic list.
Modify the driver program from 4/11 to
accommodate linked lists of int, double, and string respectively. Of course, the averaging
code will apply
only to the int and double versions.
Solution 1. In this version, we established three separate, distinct classes to represent nodes, lists, and iterators, respectively. This solution requires that all three classes be templated.
//Header File: linked.h
#ifndef LINKED_H
#define LINKED_H
#include <iostream>
using namespace std;
//THIS VERSION DECLARES THREE DISTINCT CLASSES, node, myList, and ListIterator
//ALL OF THESE CLASSES MUST BE TEMPLATED
template <class T>
struct node
{
T data;
node *next;
};
//FORWARD DECLARATION IS NECESSARY
template <class T> class
ListIterator; //Forward declaration
template <class T>
class myList
{
friend class ListIterator<T>;
private:
node<T> *front;
node<T> *rear;
public:
myList();
//Constructor
myList(const myList &); //Copy Constructor
~myList();
//Destructor
// Mutators
myList & add_front (const T);
myList & remove_front ();
myList & add_rear (const T);
myList & remove_rear ();
// Accessor
bool empty() const;
};
// Companion to class list
template <class T>
class ListIterator
{
private:
node<T> *current;
public:
ListIterator(const myList<T> &);
//Constructor
ListIterator(const ListIterator<T> &);
//Copy Constructor
//"next" places data from current node into
//parameter and advances current pointer
//returns true if successful
//false if at end of list
bool next(T &);
};
/****************************************************************************/
//list IMPLEMENTATION
template <class T>
myList<T>::myList() //Constructor
: front(NULL), rear(NULL) //member initializer list
{
}
template <class T>
myList<T>::myList(const myList & L) //Copy Constructor
{
front=rear=NULL;
for (node<T> *temp = L.front; temp!=NULL;
temp=temp->next)
{
add_rear(temp->data);
}
}
template <class T>
myList<T>::~myList() //Destructor
{
node <T> *temp;
while (front!=NULL)
{
temp = front->next;
delete front;
front = temp;
}
}
template <class T>
myList<T> & myList<T>::add_front (const T number)
{
node <T> * temp=new node <T>;
temp->data=number;
temp->next=front;
front=temp;
if (rear==NULL) //list empty to
start
rear=front;
return *this;
}
//Pre-Condition: Non-empty list
template <class T>
myList<T> & myList<T>::remove_front ()
{
node <T> * temp=front;
front=front->next;
delete temp;
if (front==NULL) //list empty
rear=NULL;
return *this;
}
template <class T>
myList<T> & myList<T>::add_rear (const T number)
{
node <T> * temp = new node <T>;
temp->data=number;
temp->next=0;
if (rear!=NULL)
rear->next=temp;
rear=temp;
if (front==NULL) //list empty to
start
front=rear;
return *this;
}
//Pre-Condition: Non-empty list
template <class T>
myList<T> & myList<T>::remove_rear ()
{
node <T> *p, *followp=NULL;
for (p=front; p!=rear; p=p->next)
followp=p;
if (followp!=NULL)
followp->next=0;
delete p;
rear=followp;
if (rear==NULL) //list empty
front=NULL;
return *this;
}
template <class T>
bool myList<T>::empty() const
{
return (front==NULL);
}
/*************************************************************************/
// ListIterator IMPLEMENTATION
template <class T>
ListIterator<T>::ListIterator(const myList<T> & L)
//Constructor
: current(L.front)
{
}
template <class T>
ListIterator<T>::ListIterator(const ListIterator<T> & I)
//Copy Constructor
: current(I.current)
{
}
//"next" places data from current node <T> into
//parameter and advances current pointer
//returns true if successful
//false if at end of list
template <class T>
bool ListIterator<T>::next(T & number)
{
if (current==NULL)
return false;
number = current->data;
current = current->next;
return true;
}
/**********************************AUXILIARY FUNCTION *****************************/
template <class T>
ostream & operator<< (ostream & out, const myList<T>
& L)
{
T data;
ListIterator<T> i(L);
while (i.next(data))
{
out << data << endl;
}
return out;
}
/************************************************************************************/
#endif
The driver for this version looks like:
//File: link_driver.cpp
#include "linked.h"
#include <iostream>
#include <string>
using namespace std;
template <class T>
T average(const myList<T> & L)
{
T number, sum=0;
int k=0;
ListIterator<int> i(L);
while (i.next(number))
{
sum += number;
k++;
}
return sum/k;
}
int main()
{
myList<string> L;
L.add_front("Bill");
L.add_front("Mohamed");
L.add_rear("George");
// L.remove_front();
// L.remove_rear();
cout <<L << endl;
//The following averaging code requires access to the list private field, front
/* int sum=0, k=0;
for (node * temp=L.front; temp != NULL; temp=temp->next)
{
sum += temp->data;
k++;
}
*/
//The ListIterator class comes to the rescue
// cout << "Average=" << average(L) << endl;
return 0;
}
Solution 2. The following version is somewhat more elegant, but requires that we introduce a new idea, the nested class. In particular, we will nest the node struct and the ListIterator class. The syntactic effect of this change is that the node and ListIterator definitions will no longer be templated. The driver will be modified to reflect the change in scoping.
// Header File: linked2.h
// USING NESTED CLASSES
#ifndef LINKED2_H
#define LINKED2_H
#include <iostream>
using namespace std;
template <typename T=int>
//DEFAULT type is int; typename is synonymous with class in this
context
class myList
{
// Companion to class list
friend class ListIterator; //Gives ListIterator access
to myList private data
private:
struct node; //myList member ==>
No need to template
node *front;
node *rear;
public:
myList();
//Constructor
myList(const myList &); //Copy Constructor
~myList(); //Destructor
// Mutators
myList & add_front (const T);
myList & remove_front ();
myList & add_rear (const T);
myList & remove_rear ();
// Accessor
bool empty() const;
class ListIterator; //myList member ==> No need to
template
};
template <typename T>
struct myList<T>::node
{
T data;
node *next;
};
template <typename T>
class myList<T>::ListIterator
{
private:
node *current;
public:
ListIterator(const myList<T> &);
//Constructor
ListIterator(const ListIterator &); //Copy
Constructor
//"next" places data from current node into
//parameter and advances current pointer
//returns true if successful
//false if at end of list
bool next(T &);
};
/****************************************************************************/
//list IMPLEMENTATION
template <typename T>
myList<T>::myList() //Constructor
: front(NULL), rear(NULL) //member initializer list
{
}
template <typename T>
myList<T>::myList(const myList & L) //Copy Constructor
{
front=rear=NULL;
for (node *temp = L.front; temp!=NULL;
temp=temp->next)
{
add_rear(temp->data);
}
}
template <typename T>
myList<T>::~myList() //Destructor
{
node *temp;
while (front!=NULL)
{
temp = front->next;
delete front;
front = temp;
}
}
template <typename T>
myList<T> & myList<T>::add_front (const T number)
{
node * temp=new node;
temp->data=number;
temp->next=front;
front=temp;
if (rear==NULL) //list empty to
start
rear=front;
return *this;
}
//Pre-Condition: Non-empty list
template <typename T>
myList<T> & myList<T>::remove_front ()
{
node * temp=front;
front=front->next;
delete temp;
if (front==NULL) //list empty
rear=NULL;
return *this;
}
template <typename T>
myList<T> & myList<T>::add_rear (const T number)
{
node * temp = new node;
temp->data=number;
temp->next=0;
if (rear!=NULL)
rear->next=temp;
rear=temp;
if (front==NULL) //list empty to start
front=rear;
return *this;
}
//Pre-Condition: Non-empty list
template <typename T>
myList<T> & myList<T>::remove_rear ()
{
node *p, *followp=NULL;
for (p=front; p!=rear; p=p->next)
followp=p;
if (followp!=NULL)
followp->next=0;
delete p;
rear=followp;
if (rear==NULL) //list empty
front=NULL;
return *this;
}
template <typename T>
bool myList<T>::empty() const
{
return (front==NULL);
}
/*************************************************************************/
// ListIterator IMPLEMENTATION
template <typename T>
myList<T>::ListIterator::ListIterator(const myList<T> &
L) //Constructor
: current(L.front)
{
}
template <typename T>
myList<T>::ListIterator::ListIterator(const ListIterator & I)
//Copy Constructor
: current(I.current)
{
}
//"next" places data from current node <T> into
//parameter and advances current pointer
//returns true if successful
//false if at end of list
template <typename T>
bool myList<T>::ListIterator::next(T & number)
{
if (current==NULL)
return false;
number = current->data;
current = current->next;
return true;
}
/*****************************OVERLOADED OPERATORS*******************************/
// Auxiliary function IMPLEMENTATION
template <typename T>
ostream & operator<< (ostream & out, const myList<T>
& L)
{
T data;
myList<T>::ListIterator i(L);
while (i.next(data))
{
out << data << endl;
}
return out;
}
#endif
The driver program is as follows:
//File: link_driver2.cpp
#include "linked2.h"
#include <iostream>
#include <string>
using namespace std;
template <class T>
T average(const myList<T> & L)
{
T number, sum=0;
int k=0;
myList<T>::ListIterator i(L);
while (i.next(number))
{
sum += number;
k++;
}
return sum/k;
}
int main()
{
myList<> L;
L.add_front(24);
L.add_front(36);
cout <<L << endl;
//The following averaging code requires access to the list private field, front
/* int sum=0, k=0;
for (node * temp=L.front; temp != NULL; temp=temp->next)
{
sum += temp->data;
k++;
}
*/
//The ListIterator class comes to the rescue
cout << "Average=" << average(L) << endl;
return 0;
}
Lab Exercise. The lecture of 4/16 introduced exception classes into our vocabulary. In particular, we extended our intStack class to incorporate pushOnFull and popOnEmpty exceptions respectively. Rewrite the following by declaring the exception classes pushOnFull and popOnEmpty as public nested classes of class intStack.
intStack.h
intStack.cpp
driver.cpp
Lab Exercise. Extend the previous lab exercise to a templated version, stack<T>.
We continued our discussion of polymorphism by elaborating on the example which described a shape hierarchy of classes. Because a Circle is a Shape and a Rectangle is a Shape, the following code is legal:
//File: Shape_driver.cpp
#include <iostream>
#include <string>
#include "Shape0.h"
using namespace std;
int main()
{
Shape * s[3]; //Array of Shapes
Shape sh;
Circle c(0.0, 0.0, 1.0, "MyCircle");
Rectangle r(0.0, 1.0, 1.0, 0.0, "MyRectangle");
s[0] = & sh;
s[1] = & c;
s[2] = & r;
cout << s[0] -> area() << endl;
cout << s[0] -> name() << endl;
cout << s[1] -> area() << endl;
cout << s[1] -> name() << endl;
cout << s[2] -> area() << endl;
cout << s[2] -> name() << endl;
return 0;
}
When compiled with Shape0.cpp, the following output results:
0
Basic Shape
0
MyCircle
<======== OUTPUT
0
MyRectangle
But this is not the output we would hope to see. Ideally, the program would be able to determine that s[1] and s[2] represent a Circle and a Rectangle respectively and therefore execute their respective area() member functions. This can be achieved very easily by adding the keyword virtual before area() in the definition of the Shape class. We have
//Header File: Shape.h
#ifndef SHAPE_H
#define SHAPE_H
#include <string>
using namespace std;
class Shape
{
public:
//Constructors
Shape();
Shape(string);
//Destructor
~Shape(){};
//Accessor
string name() const;
//Facilitator
virtual double area() const;
private:
string m_name;
};
........
With this small change, and using Shape.h with Shape.cpp, the above driver program produces the following output:
0
Basic Shape
3.14159
MyCircle
<===== OUTPUT
1
MyRectangle
To conclude, virtual functions allow the execution of functions determined by the type of the object pointed to rather than by the type of the pointer. In this case, the pointer s[] was declared to be a pointer to Shape, but the member function area() or name() executed was determined by the type of object that s[] pointed to. In short, this allows run-time or dynamic polymorphism.
If you'd like to see how all of this goes together with a modular approach, check out Shape1.h, Shape1.cpp, Rectangle1.h, Rectangle1.cpp, Circle1.h, Circle1.cpp, and Shape_driver1.cpp.
Example The following example is not a particularly good example of inheritance, but it does illustrate amusingly the power of polymorphism.
//File: Pets.cpp
#include <iostream>
using namespace std;
class housePet
{
public:
virtual void speak() { cout <<
"huh?\n";}
};
class dog : public housePet
{
public:
void speak() {cout << "woof\n";}
};
class cat : public housePet
{
public:
void speak() {cout << "meow\n";}
};
class bird : public housePet
{
public:
void speak() {cout << "chirp\n";}
};
int main()
{
housePet* myHouse[3];
dog Fido;
cat Puff;
bird Tweety;
Fido.speak();
Puff.speak();
Tweety.speak();
myHouse[0] = &Fido;
myHouse[1] = &Puff;
myHouse[2] = &Tweety;
for (int i = 0; i < 3; i++)
myHouse[i] -> speak();
return 0;
}
woof
meow
chirp
<===== OUTPUT
woof
meow
chirp
Lab Exercise. Implement a stack of integers as a derived class using the linked list class as the base class. You can download the linked list files by clicking on the following: