University of Washington
CSE 326, Data Structures
Linked Lists and Polynomials
Due: Monday, January 22, 2001, 1:30pm

Winter 2001
January 12, 2001
Donald Chinn

Linked lists are a convenient way to represent polynomials. In this programming assignment, you will implement a Polynomial abstract data type. Following Figure 3.24 in Weiss, here is what the ADT should look like:

class Polynomial
{
public:
Polynomial(); // constructor
~Polynomial(); // destructor
void zeroPolynomial(); // set the polynomial to be zero
void InsertTerm(const int coef, const int exp);
void Print(ostream & os) const;
Polynomial operator+ (const Polynomial & rhs) const;
Polynomial operator- (const Polynomial & rhs) const;
Polynomial Derivative () const;
void DerivativeInplace (); // do the derivative in place
private:
List terms; // or, you can use a class called
// LiteralList instead of using templates
};
class Literal
{
private:
// constructor and any other functions
int coefficient;
int exponent;
friend class Polynomial;
};

You may use a linked list implementation that uses a sentinel (as mentioned in Weiss) or not.

The ADT assumes that the polynomial is of a single variable (e.g., x) and that exponents and degrees are all integers. A Literal represents one of the terms of the polynomial (e.g., the 3x² in 4x³ + 3x² - 2x + 1). The polynomial, then, is represented by a linked list of Literal. For example, the polynomial 4x³ + 3x² - 2x + 1 would be represented by the following linked list:

(The picture for this didn't come out well, but there are four nodes
in the list, with the following data (coefficient/exponent):
4/3, 3/2, -2/1, 1/0

After you write your ADT, you will need to write a driver program that calls InsertTerm() to generate some polynomials. Then you can test all your public functions for the Polynomial ADT using those polynomials.

Things to be Careful about

In the Print() function, make sure the terms get printed in order, from highest exponent to the lowest. Exponents can be negative. Also, be sure you handle the signs of each term correctly (don't put a plus sign before the first term and make sure you don't print a plus sign and a minus sign before negative terms). The polynomial 4x³ + 3x² - 2x + 1 should print out like this:

4x^3 + 3x^2 - 2x + 1

For terms with a negative degree, place parentheses around the exponent:

4x^3 + 2x^(-1)

In your underlying implementation, be sure that you never have a term in a polynomial that has 0 as a coefficient and that for any given exponent there is no more than one term with that exponent.

Memory leaks: be sure to be very careful about calling delete on memory (either Literals or Polynomials) whenever they are no longer needed.

Derivative: Recall from your calculus class the way to calculate the derivative of a polynomial. If p(n) is a polynomial of the form
p(n) = sum_{i=-infinity}^{+infinity} c_i x^d_i
, then the derivative is
p'(n) = sum_{i=-infinity}^{+infinity} d_i c_i x^{(d_i - 1)} .
For example, the derivative of 5x² + 3x + 1 - 2x^-1 is 10x + 3 + 2x^-2.

Test cases: be sure to come up with a good set of test cases that test all of the logic of all of your code. Be sure that each test case tests something about your code that the other test cases do not.

Your grade (out of 50 points) will depend on the correctness and clarity of your code. It will also depend on the quality of your comments that explain potentially tricky parts of your code. Finally, it will depend on the quality and completeness of your test cases.

Bonus (5 points): Implement an operator* (multiply) for the Polynomial ADT, whose signature is
Polynomial operator* (const Polynomial & rhs) const; .