Assignment #7 Solution




  • Linked Lists

  • Operator Overloading

  • Copy control

The Task:

You will implement a class polynomial for storing and manipulating polynomial expressions. A polynomial is an expression of the form

akxk + … + a2x2 + a1x + a0

The number k is called the degree of the polynomial and the numbers a0, …, ak are called the coefficients.

Store each polynomial as a singly linked list of its coefficients, but “backwards” (backwards makes it easier). For example, the polynomial 4x3 + x + 7 would be stored as:

    head_ptr –> 7 –> 1 –> 0 –> 4

    degree:  3

Here the constant term, 7, is first, then the linear (x) term, 1, then the quadratic (x2) term, 0, and finally the highest degree term with a coefficient of 4. In addition, the degree of the polynomial is stored in the member variable degree.

Storing the polynomials in this order, rather than in the order in which we normally write them, will make it easier to perform arithmetic operations.

The class invariant (i.e., the thing that must be true about the class whenever a member function is finished making changes) is:

  1. The coefficients are stored in a linked list with the constant term at the front of the list and the highest order term at the end of the list.

  2. The zero polynomial is represented by a list with a single item, zero. The degree of the zero polynomial is 0.

  3. The list for a non-zero polynomial does not end in a zero. (In other words, the highest degree coefficient is not zero.)

  4. The value of the degree member variable is the length of the list minus one.

What you have to handle:

  • constructor that takes the degree of the polynomial and a vector of its coefficients in order from highest degree term to lowest

  • +=

  • +

  • copy control

  • ==

  • !=

  • << Use the caret ^ for exponentiation. So: 5x^3 represents five times the term with an exponent of three.

  • evaluation. Takes a single argument and evaluates the polynomial for that value of “X”.


  • Coefficients can be either ints or doubles, as you prefer.

  • Make your life easier by using the linked list code that we developed. You can put the Node struct and function prototypes in your polynomial.h and the implementations in polynomial.cpp.

What to hand in:

Header and implementation files for polynomial (polynomial.h and polynomial.cpp) and a test program that demonstrates that your class works.