Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Projects

  1. Design and implement a sorting algorithm using one of the priority queue implementations described in this chapter.
  2. Complete the BinaryHeap class declared in Program gif by providing suitable definitions for the following member functions: CompareTo, IsFull, Accept and NewIterator. Write a test program and test your implementation.
  3. Complete the LeftistHeap class declared in Program gif by providing suitable definitions for the following member functions: LeftistHeap (two constructors), Left, Right and SwapContents. You must also have a complete implementation of the base class BinaryTree. (See Project gif). Write a test program and test your implementation.
  4.   Complete the implementation of the BinomialTree class declared in Program gif by providing suitable definitions for the following member functions: BinomialTree (constructor), Count, Subtree and SwapContents. You must also have a complete implementation of the base class GeneralTree. (See Project gif). Write a test program and test your implementation.
  5. Complete the implementation of the BinomialQueue class declared in Program gif by providing suitable definitions for the following member functions: BinomialQueue (constructor), BinomialQueue (destructor), Purge, CompareTo, Accept and NewIterator. You must also have a complete implementation of the BinomialTree class. (See Project gif). Write a test program and test your implementation.
  6. The binary heap described in this chapter uses an array as the underlying foundational data structure. Alternatively we may base an implementation on the BinaryTree class described in Chapter gif. Implement a concrete priority queue class using multiple inheritance to inherit the functionality from the BinaryTree class (Program gif) and the interface from the PriorityQueue class (Program gif).
  7. Implement a concrete priority queue class using the binary search tree class from Chapter gif. Specifically, use multiple inheritance to inherit the functionality from the BST class (Program gif) and the interface from the PriorityQueue class (Program gif). You will require a complete implementation of the base class BST. (See Project gif). Write a test program and test your implementation.
  8. Devise and implement an algorithm to multiply two polynomials:

    displaymath67112

    Generate the terms of the result in order by putting intermediate product terms into a priority queue. I.e., use the priority queue to group terms with the same exponent. Hint: See also Project gif.


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.