Laboratory Notebook

Chapter 13 - Data Structures

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 gain experience with

- pointers and dynamic memory allocation
- programming using linked lists
- insertion and removal of list elements
- programming using binary trees

Write a program that creates a vector `ring`of pointers to`Circle`
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.

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.

.

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.

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 }

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.