Data Structures - Chapter 11 - Alternative Assignment
Implement and Test the Set Class Using a B-tree

Data Structures and Other Objects Using C++
Second Edition
by Michael Main and Walter Savitch
ISBN 0-201-70297-5, Softcover, 816 pages


The Assignment:
Implement the Set class, using a b-tree to store the items, as described in Section 11.2. This is a difficult assignment. You should plan at least 30 hours to complete the honors assignment. If you do the honors assignment, you do not need to complete the ordinary assignments 11-12.
Purposes:
Have you implement a challenging tree-based data structure.
Before Starting:
Read all of Sections 10.5 and 11.2.
Due Date:
________________
Files that you must write:
  1. set.h: Header file for this version of the Set class. You don't have to write much of this file. Just copy our version from set.h and add your name and other information at the top. You may also add more private member functions if you like. Notice that the set is NOT a template class. It is easier to debug with the Item type fixed as a double.
  2. set.cxx: The implementation file for the new Set class. You will write this yourself, including all the private member functions described in Section 11.2. Put a precondition/postcondition contract with each private function's implementation. NOTE: Some of you have been forgetting to put your name and a clearly written invariant at the top of this file. The TAs will start taking off points for such omissions.
  3. makefile: This is a makefile for the assignment. The file should contain targets for set.o, setexam.o, and setexam (an executable file). The source code for setexam.cxx is available in the locations listed below. Your makefile should also include "all" and "clean" options. NOTE: Dora won't test your makefile, but the TAs will take off points if it is incomplete. Include your name in a comment at the top.
Other files that you may find helpful:
  1. setexam.cxx: A non-interactive test program that will be used to grade the correctness of your Set class.



The Set Class Using a B-tree
Discussion of the Assignment

Your Set class for this assignment will use a B-tree as described in Section 11.2. You may use a typedef statement defining the Item type as a double number (rather than implementing a template class). In order for you to further learn how to use private member functions, I would like for you to write and use all the private member functions that are listed in set.h. You should write precondition/postcondition contracts for these functions are given in your implementation file.

Do the Assignment in Two Parts

For easier debugging, carry out this assignment in two parts. Part One should include everything except the public remove member function and the private functions that are needed for removal (i.e., loose_remove, remove_biggest, and fix_shortage). Once Part One is working and tested, you may complete the assignment by implementing the remove member function and its associated private functions.

Use your own interactive test program and the debugger to track down errors in your implementation. If you like, you may share an interactive test program with another student, but do not look at another student's b-tree. If you have an error, do not start making changes until you have identified the cause of the error. If you come to me or a TA for help, we will always ask you to do the following:

  1. Show us the invariant that describes how your private member variables implement the List class.
  2. Use the debugger to show us the problem!


Michael Main (main@colorado.edu)