UMBC, CMSC202 Computer Science II, Spring 2007

Project 3: Zoom Tables

Due Dates

Design Document: Sunday, April 1, 2007, 11:59pm + 59 seconds

Final Project*: Monday, April 9, 2007, 11:59pm + 59 seconds

*Because of the religious holidays around the due date, Monday was chosen to be the official due date. If this creates an unusual hardship, contact Prof. Chang.



The objective of this project is to practice writing C++ code for dynamic memory allocation.

^Return to top


In this project, you will design and implement a data structure we will call a ZoomTable. Our ZoomTable is motivated by the representation of race courses in Project 2. A common strategy is to use a two dimensional array to represent a race course. There are two problems with this approach when the race course is very large:
  1. If most of the race course is empty space, then we use a lot of memory to store nothing.
  2. When we zoom a car in a particular direction, we may have to loop through a large expanse of empty space to find the new position of the car.
These two problems can be solved by storing only those positions that contain objects and linking them together in what is essentially a two-dimensional linked list. For example:

Here, each node represents an object in the race course. Each node has 4 pointers to point to the object above, below, to the left and to the right of the node. (The node might also hold information about the object itself. This is not shown in the diagram.) Using such a ZoomTable, our storage requirement is proportional to the number of objects in the race course and we can determine the new position of a car in one step.

^Return to top


Note: you must also complete and submit a design document by Sunday, April 1. See the Design Document section.

Your assignment is to design and implement the ZoomTable data structure. As in Project 2, your code must conform to the requirements specified below and work with the main programs supplied. You must implement two classes: Node and ZoomTable. Since the primary objective of this project is to have you write code that manages memory dynamically, you are not allowed to use vectors or any other data type that does the dynamic memory allocation and deallocation for you.

Requirements for the Node class

Each Node object will have 4 pointers to other Node objects, as described above. Each Node must also hold an int data member which we'll call the "payload data". The intention is that we won't store the default int value 0 in ZoomTable.

The Node class must also have the following member functions with the prescribed function prototypes:

You will, of course, need to implement other member functions and specify the data members. Note that row and column numbers have type int rather than unsigned int. This is deliberate.

Requirements for the ZoomTable class

Since ZoomTable objects allocate memory dynamically, you must implement the following member functions: The ZoomTable class must support the following methods:

^Return to top


^Return to top

Implementation Notes

  1. Since Node and ZoomTable are closely related classes (you would not use one without the other), both class declarations should go into a single file ZoomTable.h and both implementations should go into another single file ZoomTable.cpp. Please capitalize ZoomTable exactly.

  2. Since a ZoomTable is designed to replace two-dimensional arrays, row and column numbers should begin at 0.

  3. When a Node is inserted, you must link the Node into its row and into its column.

  4. The ZoomTable member function insert() will allow a programmer to insert 0's into the table, even though one of the main reasons for having a ZoomTable is to not store zeroes. We'll assume the programmer has a good reason for doing so.

  5. The ZoomTable member functions insert(), remove() and find() share some common tasks. It will make your code cleaner (and easier to debug) if the common tasks are consolidated into one function. Such functions are usually declared as private member functions.

  6. Remember that you are not allowed to use vector.

  7. Yes, the copy constructor has to chase down every Node in the ZoomTable and copy it. Ditto for the overloaded assignment operator.

  8. The insert() function can be pretty useful when you write the copy constructor and the overloaded assignment operator.

  9. Know the difference between delete and delete [].

  10. Yes, the destructor has to chase down every Node in the ZoomTable and delete it.

  11. Consider using assertions (see p. 169 of your textbook). It is very useful to have assertions like: assert(ptr != NULL) ; in parts of your code where you think you know that ptr can't be or shouldn't be NULL. If you're wrong then the assertion will fail and you will get an error message giving the line number of the assertion that failed. This is much better than having your program crash later when you try to dereference a NULL pointer.

    There is no harm in having too many assertions, since they can be "turned off" easily with a #define NDEBUG.

  12. When you get a core dump, remember that you've had practice using the gdb debugger.

^Return to top

Design Document

You must submit written responses to these questions by Sunday, April 1, 11:59:59pm. Late submissions are not accepted for design documents.

Answer the following questions using complete English sentences. As usual, grammar and spelling counts. If you remember CUPS = "Capitalization, Usage, Punctuation and Spelling" from elementary school, they certainly apply here.

  1. In Lab 6, the List class used dummy headers at the beginning of the linked list. Will you use dummy headers for each row or column of a ZoomTable? If so, how many (1 or 2) and how can you tell when a Node pointer is pointing to a dummy? If no dummy headers will be used, why not?

  2. How will your ZoomTable constructor initialize the linked lists for each row and or column? What, if any, items need to be dynamically allocated?

  3. Suppose that you locate the insertion point for a Node in a ZoomTable starting at smaller index values to larger ones. When you copy an entire ZoomTable in the copy constructor, should you copy nodes with larger indices first? or smaller indices first? Why would this make a difference?

What/how to submit for your design document:

^Return to top


You are provided with 2 main programs listed below. Your design and implementation of the Node and ZoomTable classes must compile and run with these 2 programs without any modification.

Warning: When your project is graded, it will also be tested with additional main programs. So, having a project that works with these programs is not a 100% guarantee. Your project must also satisfy the requirements specified above.

You must also create and submit your own test program. Part of your grade depends on this. You should show that you have fully exercised your implementation of the Node and ZoomTable classes.

Note: these files are also available on the GL file system at: /afs/

^Return to top

Submitting in your program

Remember to submit the design document the first week!

Use the UNIX submit command to turn in your project. The project name for Project 3 is 'proj3'. So, the Unix command will look like:

submit cs202 proj3 ... where ... is a list of files you wish to submit.

You should submit the following files. Please follow the capitalization and spelling of these files.

Note: We will assume that your project will compile using: g++ -Wall -ansi *.cpp If this is not the case, submit a makefile.

^Return to top