Implement a sparse polynomial class based on linked list classes
P(x) = an xn + an - 1xn - 1 + ... + a1 x + a0, ⋅∋⋅
ai ∈ Polynomial_coefficient_type
x ∈ Indeterminate_type
n ∈ Polynomial_index_type
This project should be performed using three linked list classes having the same interfaces:
Stage 1: Use wrappers to give the STL List class the same method interfaces as the two classes in Assignment 4.
Stage 2: implement the sparse polynomial class via the public methods (which should all share identical interfaces) of the sorted linked list classes developed in Stage 1 and in Assignment 4.
(This is based on Programming problem 4.8)
Note: See {Carrano pages 305 - 308} for an example of the implementation of an ADT class via the use of a pre-existing ADT class.
Stage 3: Test each sorted linked list implementation with the sparse polynomial class.
Recommended methods for the polynomial class:
default & copy constructor
destructor
save(stream_type outFile) & restore(stream_type inFile, poly_type p)
These methods dump to and restore from a file.
See {Carrano pages 205 - 208} for a discussion of the implementations of these methods.
Inquiry functions (must not change the polynomial data):
bool isEmpty() // Determines whether the polynomial is empty
bool isInOrder() // Determines whether the polynomial is stored having the terms ordered from greatest to least exponent.
bool isSimplified() // Assumes isInOrder(). Determines whether the polynomial is simplified. Is false if multiple terms share an exponent.
bool isSparse() // Is false if any (stored) term has a zero valued coefficient.
bool isDivisionAlgebra() // Is false if the coefficients are of a type that has no inverse.
{e.g. floating point (real and complex), and rational types have inverses, but integer types don't}
Polynomial_coefficient_type coef(Polynomial_index_type i) // Returns the coefficient of the xi term.
bool isMonic() // Is the leading coefficient the multiplicative identity (usually 1 or 1.0) (ensure that you handle the case where the coefficient is zero, i.e. there is no node for this term)
Polynomial_index_type degree() // Returns the value of the greatest exponent
isNextTerm(Polynomial_index_type i) // Is there a greatest exponent less than i having a non-zero coefficient.
Polynomial_index_type nextTerm(Polynomial_index_type i) // Returns the value of the greatest exponent less than i having a non-zero coefficient.
print(char x = 'x') // Pretty-print the polynomial to stdout using the specified character, defaulting to 'x' to represent the indeterminate (variable). E.g.
4 x^8 + 2 x^5 - 7 x^2 - 3
eval(Indeterminate_type x) // Evaluate the polynomial at a point using Horner's method
{Note that you can compute powers when there are zero valued coefficients.
You can use one of the binary power algorithms that you've written and tested}
e.g. 4 x^8 + 2 x^5 - 7 x^2 - 3 ->
( ( 4 x^3 + 2 ) x^3 - 7 ) x^2 - 3 ->
( ( 4 pow(x, 3) + 2 ) pow(x, 3) - 7 ) pow(x, 2) - 3
derivative(Polynomial p) // Set p to be the first derivative of the polynomial.
derivative() // Transform a polynomial to be its first derivative.
{how might you implement a related function which yields an nth derivative?}
Mutator functions (they change the polynomial data):
clear() // Sets all coefficients to zero (delete all nodes). Postcondition: isEmpty() is true.
clear(Polynomial_index_type i) // Set the coefficient of the xi term to zero (and delete that node).
setCoefficient(Polynomial_index_type i, Polynomial_coefficient_type a) // Set the coefficient of the xi term to a.
setInOrder() // Orders exponents from greatest to least.
setSparse() // Delete any (stored) terms having a zero coefficient.
simplify() // Adds together all terms sharing an exponent.
setMonic() // Assumes isDivisionAlgebra(). If not IsMonic(), divide polynomial by leading coefficient.
Operator functions:
{Note: all operator functions should be inorder, sparse, and simplified as preconditions and postconditions}
add(Polynomial b) // Addition: a += b
add(Polynomial c, Polynomial a, Polynomial b) // Addition: c = a + b
subtract(Polynomial b) // Subtraction: a -= b {consider using a helper function which reverses the signs of all nonzero coefficients}
subtract(Polynomial c, Polynomial a, Polynomial b) // Subtraction: c = a - b {consider using a helper function which reverses the signs of all nonzero coefficients}
product(Polynomial_coefficient_type b) // Product: a *= b // a is a polynomial and b is a scalar.
product(Polynomial b) // Product: a *= b
product(Polynomial c, Polynomial a, Polynomial b) // Product: c = a * b
extra credit: divide(Polynomial q, Polynomial r, Polynomial a, Polynomial b) // Quotient and remainder: a / b -> q + r / b
{see this resource on polynomial long division}
Ensure that your program detects bad, undefined, and out-of-range input errors both on the command line and during execution. Error messages should go to standard error.
Focus on the modularity of your design. Try to maximize cohesion and minimize coupling.
Before the program exits, be sure to release back to the heap all dynamic memory objects.
Use typedef to establish the types for the exponent, the coefficient and the independent variable