University of Washington

CSE 373, Data Structures and Algorithms

Linked Lists and Polynomials

Due: Monday, October 22, 2001, 12:30pm

 

Autumn 2001                                                                                       October 12, 2001

Donald Chinn

 

Project Objectives

 

Project Description

 

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;

 

private:

      List<Literal> 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 3x2 in 4x3 + 3x2 – 2x + 1).  The polynomial, then, is represented by a linked list of Literal.  For example, the polynomial 4x3 + 3x2 – 2x + 1 would be represented by the following linked list:

 

 

 

 

 

 

 

 

 


What Code to Write

 

You may use the linked list code provided by Weiss (go to his web site from our course web page), and we recommend that you do.  The code is in LinkedList.h and LinkedList.cpp.  You will also need dsexceptions.h for the exceptions that the linked list code sometimes generates.  There is a weirdness with Weiss’s code where LinkedList.h actually #includes LinkedList.cpp.  To avoid a multiply defined error when you compile, do not add LinkedList.h to the project and do not add LinkedList.cpp to the project.

 

If you don’t like Weiss’s code, you may write your own List ADT using a linked list implementation.  Put your code in LinkedList.h and LinkedList.cpp (dsexceptions.h optional).

 

You should put your polynomial code into two files, polynomial.h and polynomial.cpp.  Follow the “usual” #include convention of saying #include “polynomial.h” in polynomial.cpp and add polynomial.cpp to the project.

 

In general, you may copy any code from Weiss’s web site, but you may not copy code from any other source.  Also, you may use the vector and string templates Weiss provides (although in this project you won’t need them), but you may not use any templates from the Standard Template Library (STL).

 

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 4x3 + 3x2 – 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.  (Why are these important?)

 

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 , then the derivative is .  For example, the derivative of 5x2 + 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; .

What is the running time (Big-Oh) of your algorithm?

 

 

How to Turn in Your Work

 

We are working on the electronic turning procedures.  It will be very much like the CSE 143 turnin procedure.  For this assignment, you will turn in five or six files: LinkedList.h, LinkedList.cpp, polynomial.h, polynomial.cpp, main.cpp, and (optionally, if you don’t write your own linked list implementation) dsexceptions.h.