Computing Concepts with C++ Essentials, 2nd ed.
Laboratory Notebook
Chapter 13 - Data Structures

Cay S. Horstmann
Geof Pawlicki

Your name:
Your email address:
Your student ID number:

Once this form has been customized for your institution, you can use this button to send your lab work. Be sure to read the instructions before starting your work.

Lab Objectives

To gain experience with

P1. Pointers

Write a program that creates a vector ringof pointers toCircle objects, that is, a vector<Circle*> ring;. Your job is to fill rings with five pointers to circles that are configured like the interlocking Olympic rings.

Initialize the vector by allocating five circles on the heap with new and calling push_back to append the resulting pointers to the vector.

Write a loop that displays all elements in rings on the graphics screen

Write a loop that deletes all heap objects whose pointers are stored in rings

4. Combine the code into a main program that prints out the Olympic rings.

Note: In this example, there was no advantage to using a vector<Circle*>. It would have been easier to use a vector<Circle>. The purpose of this exercise was to get you used to the pointer notation and dynamic allocation.

This is a worthwhile exercise since the next lab (on inheritance) uses a vector<Card*> to hold a vector of cards (such as an ID card, a phone card, and so on). In that lab, it is essential that you use a vector of pointers--a vector<Card> will not be sufficient.

P2. Using Linked Lists

In this exercise, you should use the standard list template. Write a program that reads in a sequence of numbers and add seach input to the front of a list<int> object. (To add to the front, use the insert function with the begin iterator position.)

Then iterate through the list and print each element.


Run your program and describe its behavior.


P3. Implementing linked list operations

One very natural operation that is not already a feature of the List class in the textbook is appending an element to the head of a list.

Provide a new member function push_front(string e) class which will add the string e to the start of the original list.

For example, if the list a contains Harriet, Jim and Carolyn, and e is Harry, then the command a.push_front(e) changes a to contain Harry, Harriet, Jim, and Carolyn.

In this exercise, you must modify the pointers of the list. You may not use list iterators.


Test the append function by writing a main function that prints a list and then appends Employee objects to a list. Then print out the combined list.

P4. Operator overloading

Implement a class Fraction with a constructor

Fraction(long numerator, long denominator)

and overloaded operators + - * / << to add, subtract, multiply and divide fraction objects. Then test your program to compute the expression "1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10".

You must keep track of the numerator and denominator separately as exact values. Do not use double. This way, you will obtain the numerator and denominator of the result precisely, without roundoff error.

For example, to add two fractions, you use the formula

a/b + c/d = (ad + bc)/(bd)

and then reduce to the lowest common terms, by dividing through the greatest common divisor.

Fraction Fraction::operator+(Fraction b)
{   long n = num * b.den + den * b.num;
    long d = den * b.den;
    long g = gcd(n, d);
    return Fraction(n / g, d / g);

Here is a "greatest common divisor" function for your use:

int gcd(int a, int b)
// compute the greatest common divisor
{  if (a < 0) return gcd(-a, b);
   if (a == 0) return b;
   if (b < a)  return gcd(b, a);
      // now 0 < a <= b
   return gcd(b % a, a);
      // b % a is the remainder of the division b / a

P5. Templates

Templates let you design a family of related classes that differ by the type of some of the data members or member functions. In this exercise, you will design a template for a table of items of an arbitrary type. For example,

Table<double> balances(12, 5);

make a table of items of type double, with 12 rows and 5 columns.

Supply two member functions:

value = balances.get(row, col);
balances.set(row, col, value);

Hint: As implementation, use a vector with nrows * ncols elements. To access the element in row i and column j, access v[i * ncols + j].

Your job is now to design a Table class template and to put it to use by re-implementing the matrix.cpp program in your textbook on p. 427, using a Table<double> instead of a two-dimensional C-style array.

Don't forget to send your answers when you're finished.