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

Implementation

To begin with, we need to represent the terms of the polynomial. Program gif repeats the definition of the Term class given in Section gif. The reason for repeating the definition here is that some additions are needed to support the the implementation of polynomial addition.

   program10916
Program: Term Class Definition

Three additional functions are declared in Program gif. The first two, Coefficient and Exponent, are simple accessor functions which provide read-only access to the corresponding member variables of a Term instance. Clearly, the running time of each of these functions is O(1).

The third function overloads the addition operator, operator+. in such a way as to make it possible to add two Terms together. The result of the addition is another Term. The working assumption is that the terms to be added have identical exponents. If the exponents are allowed to differ, the result of of the addition is a polynomial which cannot be represented using a single term! To add terms with like exponents, we simply need to add their respective coefficients. Therefore, the running time of the Term addition operator is O(1).

We now turn to the polynomial itself. Program gif declares the Polynomial class. We have chosen in this implementation to use the pointer-based sorted list implementation to represent the sequence of terms. Therefore, the Polynomial class is derived from the SortedListAsLinkedList class.

   program10947
Program: Polynomial Class Definition

Only one additional function is declared in Program gif. Specifically, the addition operator, operator+, has been overloaded to make it possible to add two Polynomials to obtain a third. Program gif gives the implementation for this operator.

   program10960
Program: Polynomial Addition Operator Definition


next up previous contents index

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