Data Structures and Algorithms with Object-Oriented Design Patterns in C++

### Implementation

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

Program: Term Class Definition

Three additional functions are declared in Program . 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  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.

Program: Polynomial Class Definition

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