MVNU Computer Science II - Lab 7: Inheritance

Spring 2010


In this lab you are going to experiment with creating new classes that use inheritance to derive functionality from a base class. These classes will then be enhanced to be template classes.


Understanding Base and Derived Classes*

The object-oriented programming paradigm is based on the concept of object hierarchies that are created through inheritance . In this system, a simple base class acts as a foundation on which you can build more complex classes. The resulting classes can then act as the foundation for even more complex classes, and so on. A class that's built from an existing class, to extend its capabilities in some way, is called a derived class.

Inheritance

In C++ programming, inheritance is the ability of one class to derive characteristics from another class. The inherited class derives its characteristics from a base class, resulting in a derived class.

The code below illustrates how to declare a Dog class that is derived from a Mammal class.

0:  // Simple inheritance
 1:  #include <iostream>
 2:
 3:  enum BREED { YORKIE, CAIRN, DANDIE, SHETLAND, DOBERMAN, LAB };
 4:
 5:  class Mammal
 6:  {
 7:  public:
 8:      // constructors
 9:      Mammal();
10:      ~Mammal();
11:
12:      // accessors
13:      int GetAge() const;
14:      void SetAge(int);
15:      int GetWeight() const;
16:      void SetWeight();
17:
18:      // Other methods
19:      void Speak();
20:      void Sleep();
21:
22:
23:  protected:
24:      int itsAge;
25:      int itsWeight;
26:  };
27:
28:  class Dog : public Mammal
29:  {
30:  public:
31:      // Constructors
32:      Dog();
33:      ~Dog();
34:
35:      // Accessors
36:      BREED GetBreed() const;
37:      void SetBreed(BREED);
38:
39:      // Other methods
40:      // WagTail();
41:      // BegForFood();
42:
43:  protected:
44:      BREED itsBreed;
45:  };
46: int main()
47: {
48:        return 0;
}

The hierarchy has to begin somewhere; this program begins with Mammal . Because of this decision, some member variables that might properly belong in a higher base class are now represented here. For example, certainly all animals have an age and weight; so if Mammal derived from Animal, we might expect it to inherit those attributes. As it is, the attributes appear in the Mammal class.

To keep the program reasonably simple and manageable, only six methods have been put in the Mammal class—four accessor methods, Speak(), and Sleep().

The Dog class inherits from Mammal , as indicated on line 28. Every Dog object will have three member variables: itsAge, itsWeight, and itsBreed. Note that the class declaration for Dog does not include the member variables itsAge and itsWeight. Dog objects inherit these variables from the Mammal class, along with all Mammal's methods except the copy operator, the constructors, and the destructor.

Private Versus Protected

You may have noticed that a new access keyword, protected, has been introduced on lines 23 and 43 of the program above. Previously, class data had been declared private. However, private members are not available to derived classes. You could make itsAge and itsWeight public, but that is not desirable. You don't want other classes accessing these data members directly.

What you want is a designation that says, “Make these visible to this class and to classes that derive from this class.” That designation is protected . Protected data members and functions are fully visible to derived classes, but are otherwise private.

There are, in total, three access specifiers: public, protected, and private . If a function has an instance of a class, it can access all of the public member data and functions of that class. The member functions of a class, however, can access all the private data members and functions of any class from which they derive.

Therefore, the function Dog::WagTail() can access the private data itsBreed and can access the protected data in the Mammal class.

Even if other classes are layered between Mammal and Dog (for example, DomesticAnimals), the Dog class will still be able to access the protected members of Mammal , assuming that these other classes all use public inheritance.

The code below demonstrates how to create objects of type Dog and access the data and functions of that type.

0:  //Listing 16.6 Hiding methods
 1:
 2:  #include <iostream>
 3:
 4:  class Mammal
 5:  {
 6:  public:
 7:      void Move() const { std::cout << "Mammal move one step\n"; }
 8:      void Move(int distance) const
 9:          { std::cout << "Mammal move " << distance <<" steps.\n"; }
10:  protected:
11:      int itsAge;
12:      int itsWeight;
13:  };
14:
15:  class Dog : public Mammal
16:  {
17:  public:
18:      void Move() const { std::cout << "Dog move 5 steps.\n"; }
19:  }; // You may receive a warning that you are hiding a function!
20:
21:  int main()
22:  {
23:      Mammal bigAnimal;
24:      Dog fido;
25:      bigAnimal.Move();
26:      bigAnimal.Move(2);
27:      fido.Move();
28:      // fido.Move(10);
29:      return 0;
30:  }

Experiment 1

Get the previous program running. Then enhance with a new derived class "cat". A cat has a private value, "lives", which starts at 9. It has the functions "meow()", "prrrr()", and "kill(). Eat time killed the lives decreases, and when it is zero the cat is declared "Dead" to cout.

List

Now consider a simple list of integers, implemented with a linked list.

Below is the interface:

#include <iostream>
using namespace std;
class list
{
private:
   struct node
   {
      int data;
      node *link;
   }*p;


public:
   list();
   void append( int num );
   void prepend( int num );
   void addafter( int c, int num );
    void del( int num );
    friend ostream &operator<< (ostream &out, list &thelist); 
    int count();
   ~list();

};

Note the use of the overloaded friend << operator.

Next consider the implementation:


#include "list.h"

list::list()
{
   p=NULL;
}

void list::append(int num)
{
   node *q,*t;

   if( p == NULL )
   {
      p = new node;
      p->data = num;
      p->link = NULL;
   }
   else
   {
      q = p;
      while( q->link != NULL )
         q = q->link;

      t = new node;
      t->data = num;
      t->link = NULL;
      q->link = t;
   }
}

void list::prepend(int num)
{
   node *q;

   q = new node;
   q->data = num;
   q->link = p;
   p = q;
}

void list::addafter( int c, int num)
{
   node *q,*t;
   int i;
   for(i=1,q=p;i<c;i++)
   {
      q = q->link;
      if( q == NULL )
      {
         cout<<"\nThere are less than "<<c<<" elements.";
         return;
      }
   }

   t = new node;
   t->data = num;
   t->link = q->link;
   q->link = t;
}

void list::del( int num )
{
   node *q,*r;
   q = p;
   if( q->data == num )
   {
      p = q->link;
      delete q;
      return;
   }

   r = q;
   while( q!=NULL )
   {
      if( q->data == num )
      {
         r->link = q->link;
         delete q;
         return;
      }

      r = q;
      q = q->link;
   }
   cout<<"\nElement "<<num<<" not Found.";
}

ostream &operator<< (ostream &out, list &thelist)
{
   list::node *q;
   out<<endl;

   for( q = thelist.p ; q != NULL ; q = q->link )
      out<<q->data<<" ";
   out<<endl;
   return out;
}

int list::count()
{
   node *q;
   int c=0;
   for( q=p ; q != NULL ; q = q->link )
      c++;

   return c;
}

list::~list()
{
   node *q;
   if( p == NULL )
      return;

   while( p != NULL )
   {
      q = p->link;
      delete p;
      p = q;
   }
}

Finally consider a driver program to test it all out:


#include "list.h"

int main()
{
   list ll;
   cout<<"No. of elements = "<<ll.count();
   ll.append(12);
   ll.append(13);
   ll.append(23);
   ll.append(43);
   ll.append(44);
   ll.append(50);

   ll.prepend(2);
   ll.prepend(1);

   ll.addafter(3,333);
   ll.addafter(6,666);

   cout << "\nList State: ";
   cout << ll;
   cout<<"\nNo. of elements = "<<ll.count();

   ll.del(333);
   ll.del(12);
   ll.del(98);
   cout << "\nList State: ";
   cout << ll;
   cout<<"\nNo. of elements = "<<ll.count();
   return 0;
}

Experiment 2

Implement the previous list code and driver. Test it out.

Then add two additional functions: "removeFirst()" and "removeLast()". These functions attempt to remove and return the first, or last, element from the list, deleting the item in the process. Modify the driver program to test these new features out.

Stacks and queues**

In this section, we introduce two closely-related data types for manipulating arbitrarily large collections of objects: the stack and the queue. Each is defined by two basic operations: insert a new item, and remove an item. When we insert an item, our intent is clear. But when we remove an item, which one do we choose? The rule used for a queue is to always remove the item that has been in the collection the most amount of time. This policy is known as first-in-first-out or FIFO. The rule used for a stack is to always remove the item that has been in the collection the least amount of time. This policy is known as last-in first-out or LIFO.

Pushdown stacks.

A pushdown stack (or just a stack) is a collection that is based on the last-in-first-out (LIFO) policy. When you click a hyperlink, your browser displays the new page (and inserts it onto a stack). You can keep clicking on hyperlinks to visit new pages. You can always revisit the previous page by clicking the back button (remove it from a stack). The last-in-first-out policy offered by a pushdown stack provides just the behavior that you expect.

Pushdown stack

By tradition, we name the stack insert method push() and the stack remove operation pop(). We also include a method to test whether the stack is empty. The following API summarizes the operations:

API for a stack of strings

Note that a Stack is a special type of list - one where items are allowed to be added, and removed, from the same end (front).

Experiment 3

Note the similarity between a stack and a list. Create a new class, using the previous list class as the base class.

Consider:

1. Do you need to change "list", If so, why?

2. Can the new functions reuse some of the existing functions? If so, reuse code, don't write new code.

Create a new driver that completely tests the functionality of the stack

Do the following: Push: 4 56 32 65 34 56 34 Display stack Pop and display twice push 4 6 3 57 23 pop three times and display display stack

Queue.

A queue supports the insert and remove operations using a FIFO discipline. By convention, we name the queue insert operation enqueue and the remove operation dequeue. Lincoln tunnel. Student has tasks that must be completed. Put on a queue. Do the tasks in the same order that they arrive.

LIFO queue

public class Queue<Item> {
    public boolean isEmpty();
    public void enqueue(Item item);
    public Item dequeue();
 }

Experiment 4

Note again the similarity between a queue and a list. Create a new queue class, using the list class as the base class. Expand you test driver to create and fully test instances of the queue class.

Do the following:

Add: 22 32 35 68 94 53 21 66

Remove and display three items

Display Queue

Add: 12 7 17 41 85 17

Remove and display six items

Display Queue


What to turn in on Moodle

The laboratory report should include the following elements:

1. Brief statement of the objectives of the lab and a description of what you did during the lab session (1/2 – 1 page).
2. Lab results such as program listings, input and/or output files, tables of data produced, answers to specific questions posed, etc. as appropriate to the lab assignment. If there were no results, indicate this with “No Results.”
3. Discussion of any difficulties you encountered and what you did to resolve them (1/2 – 1 page).
4. Discussion of what you learned or how the lab experience reinforced things you already knew (1/2 – 1 page).
5. Your overall rating of the lab on a scale of 1-4 and an explanation of your rating. Ratings are as follows:

1 = poor
2 = fair
3 = good
4 = excellent

*Adapted from Practical C++ and Sams Teach Yourself C++ in 24 Hours, Third Edition

** Adapted from http://www.cs.princeton.edu/introcs/43stack/

-- JimSkon - 2010-04-08

Topic revision: r5 - 2011-04-28 - JimSkon
 
This site is powered by the TWiki collaboration platformCopyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback