Sample Assignment: The Polynomial with a Linked List
(Chapter 5)

Data Structures and Other Objects Using C++
Third Edition
by Michael Main and Walter Savitch
ISBN 0-321-19716-X

The Assignment:
Implement a polynomial class that uses a doubly-linked list to store the polynomial's terms. Each node of the list holds the coefficient and exponent for one term. The terms are kept in order from smallest to largest exponent. Each polynomial also maintains a pointer to the most recently accessed node.
Ensure that you can write a class that uses a linked list.
Before Starting:
Read Sections 5.1 to 5.3 and 5.5.
Complete the previous assignment of a polynomial that uses a dynamic array to store its coefficients (
Due Date:
Thursday, Oct 12. If you run into problems, you may submit the work on Friday with no penalty. You may also submit on Saturday or Sunday with a penalty of 5 points per day. No submissions allowed after Sunday.
Files that you must write:
  1. poly2.h: The header file for the new polynomial class. Start with our our version of poly2.h and add your name and email address at the top.
  2. poly2.cxx: The implementation file for the new polynomial class.
Other files that you may find helpful:
  1. polytest2.cxx: A simple interactive test program.
  2. polyexam2.cxx: A non-interactive test program that will be used to grade the correctness of your polynomial class.

The Polynomial Class with a Linked List
Discussion of the Assignment

As indicated above, you will revise the polynomial class to use a doubly-linked list to store. You'll need to copy your poly1.cxx to a new file poly2.cxx and make these changes:

  1. Change the namespace to main_savitch_5, and change the include statement to include poly2.h. Also include <cstdlib> (which has NULL).

  2. Delete the DEFAULT_CAPACITY constant.

  3. Look at the new polynode class in poly2.h and look at the new private member variables for the polynomial class:
    	polynode *head_ptr;             // Head pointer for list of nodes
    	polynode *tail_ptr;             // Tail pointer for list of nodes
    	mutable polynode *recent_ptr;   // Pointer to most recently used node
    	unsigned int current_degree;    // Current degree of the polynomial
    The meaning of the mutable keyword will be covered in class. But a brief explanation now: Our plan is to keep the recent_ptr always pointing to the most recently-used node. For example, when we call the coefficient member function, we will move the recent_ptr to point to the node that contains the requested exponent. With a normal member variable, we could not do this (since the coefficient is a const member function and it is forbidden from changing normal member variables). So, the meaning of the mutable keyword is to indicate that changing the member variable does not change the value of the polynomial in a meaningful way (and therefore, the compiler will let const member functions change a mutable variable).
  4. In your poly2.cxx, write a clear description of how the member variables of a polynomial are used. The head_ptr and tail_ptr are the head and tail pointers for a doubly-linked list of nodes that contain the polynomial's terms in order from smallest to largest exponent. To make certain operations simpler, we will always keep a node for the zero-order (x^0) term. But other nodes are kept only if the coefficient is non-zero. We always maintain recent_ptr as a pointer to some node in the list--preferably the most recently used node. The degree of the polynomial is stored in current_degree (using zero for the case of all zero coefficients).

  5. Delete the reserve member function (and delete any places where you called the reserve function).

  6. The poly2.h header file contains a prototype for a private member function that will make it easier to implement everything else:
        // A private member function to aid the other functions:
        void set_recent(unsigned int exponent) const;
    The set_recent function will set the recent_ptr to the node that contains the requested exponent. If there is no such exponent, then recent_ptr should be set to the last node that is still less than the specified exponent. Note that set_recent is a const member function, but that it can still change the mutable recent_ptr member variable. My implementation of set_recent used three cases:

  7. Implement the new constructors, destructor, and assignment operator.

    The default constructor should start by creating a valid empty polynomial (with a head node that has exponent and coefficient of zero). Then call assign_coef to set the one term.

    The copy constructor should also start by creating a valid empty polynomial. Then have a loop tht steps through the terms of the source (using source.next_term). Each term of the source is placed in the polynomial (using assign_coef).

    The assignment operator first checks for a self-assignment, then clears out the terms (using the clear function). Finally, have a loop (similar to the copy constructor) to copy the terms of the source.

  8. Implement the new assign_coef function. After calling set_recent(exponent), my implementation had these cases:

  9. Rewrite next_term
  10. and previous_term so that they each start with set_recent(exponent). Hint for next_term: Start by calling set_recent(e). Normally, the right answer is then in the node after recent_ptr (but there is one exception that you should handle). Hint for previous_term: Start by checking the special case where e is zero. Then call set_recent(e-1). Normally, the right answer is then in the recent_ptr node (but again, there is one exception that you need to handle--the case where the node has exponent and coefficient of zero).

  11. Revise any other functions that access the member variables directly. In my implementation, this was only clear and coefficient. I told you that it would save work to avoid accessing those member variables directly!

Michael Main (