CptS 122 – Data Structures

Lab 12: Inheritance and Containers and Data Structures in C++

Assigned: Week of November 12, 2012

Due: At the end of the lab session

I. Learner Objectives:

At the conclusion of this programming assignment, participants should be able to:

• Design, implement and test classes in C++ which apply inheritance
• Apply and implement private inheritance to container classes
• Compare and contrast inheritance (“is-a”) relationships versus composition (“has-a”) relationships
• Apply and implement overloaded functions and operators

II. Prerequisites:

Before starting this programming assignment, participants should be able to:

• Analyze a basic set of requirements for a problem
• Create test cases for a program
• Design, implement and test classes in C++
• Declare and define constructors
• Declare and define destructors
• Compare and contrast public and private access specifiers in C++
• Describe what is an attribute or data member of a class
• Describe what is a method of a class
• Apply and implement overloaded functions
• Distinguish between pass-by-value and pass-by-reference
• Discuss classes versus objects
• Describe and define inheritance

III. Overview & Requirements:

This lab, along with your TA, will help you navigate through designing, implementing, and testing inheritance with container classes in C++. It will also, once again, help you with understanding how to apply inheritance to an application.

Labs are held in a “closed” environment such that you may ask your TA questions. Please use your TAs knowledge to your advantage. You are required to move at the pace set forth by your TA. Please help other students in need when you are finished with a task. You may work in pairs if you wish. However, I encourage you to compose your own solution to each problem. Have a great time! Labs are a vital part to your education in CptS 122 so work diligently.

One of the powers of inheritance is that it facilitates large amounts of code reuse. In this lab you will redesign your stack and queue classes by inheriting from a base list class.

Task 1.

Implement a templated class list and listnode. You may add methods/functions as you see fit. Test these classes. I have left all of the implementation as an exercise for you.

template< class NODETYPE > class List; // forward declaration

template<class NODETYPE>

class ListNode

{

friend class List< NODETYPE >; // make List a friend

public:

ListNode( const NODETYPE & ); // copy constructor

NODETYPE getData() const; // return data in the node

private:

NODETYPE data; // data

ListNode< NODETYPE > *nextPtr; // next node in the list

};

template< class NODETYPE >

class List

{

public:

List(); // constructor

~List(); // destructor

void insertAtFront( const NODETYPE & );

void insertAtBack( const NODETYPE & );

bool removeFromFront( NODETYPE & );

bool removeFromBack( NODETYPE & );

bool isEmpty() const;

void print() const;

private:

ListNode< NODETYPE > *firstPtr; // pointer to first node

ListNode< NODETYPE > *lastPtr; // pointer to last node

// Utility function to allocate a new node

ListNode< NODETYPE > *getNewNode( const NODETYPE & );

};

Task 2. Now for the cool part.

Create a stack that inherits privately from the List class. You should define the push ( ), pop ( ), top ( ), full ( ), and empty ( ) operations in terms of the inherited list operations.

Task 3. More coolness.

Create a queue that inherits from a list class in the same way that you built the stack.

IV. Submitting Labs:

• You are not required to submit your lab solutions. However, you should keep them in a folder that you may continue to access throughout the semester. You should not store your solutions to the local C: drive on the Sloan 353 machines. These files are erased on a daily basis.

V. Grading Guidelines:

• This lab is worth 100 points. Your lab grade is assigned based on completeness and effort. To receive full credit for the lab you must show up on time and continue to work on the problems and complete all the problems until the TA has dismissed you.