Sample Assignment: The Polynomial with a Linked List


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.
poly2.cxx:
The implementation file for the new
polynomial class.
polytest2.cxx:
A simple interactive test program.
polyexam2.cxx:
A noninteractive test program that will
be used to grade the correctness of your polynomial class.
As indicated above, you will revise the polynomial class to use a
doublylinked list to store. You'll need to copy your poly1.cxx
to
a new file poly2.cxx
and make these changes:
main_savitch_5
, and
change the include statement to include poly2.h
.
Also include <cstdlib>
(which has NULL).
polynode
class in poly2.h
and look
at the new private member variables for the polynomial
class:
private: 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 polynomialThe 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 recentlyused 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).
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
doublylinked 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 zeroorder (x^0) term. But other
nodes are kept only if the coefficient is nonzero.
We always maintain recent_ptr as a
pointer to some node in the listpreferably the most recently
used node.
The degree of the polynomial is stored in current_degree
(using zero for the case of all zero coefficients).
reserve
member function (and delete any
places where you called the reserve
function).
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:
recent_ptr
to the head of the list.
recent_ptr
to the tail of the list.
recent_ptr
forward as far as needed.
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 selfassignment, 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.
assign_coef
function. After calling
set_recent(exponent)
, my implementation
had these cases:
recent_ptr>exponent( ) is less than the new exponent).
Else if the coefficient is nonzero or the exponent is zero (in
both these cases, we just change the coefficient of a node).
Else if the exponent equals the current degree. In this case, the
coefficient is zero (otherwise we would have hit the previous case),
so we remove the tail node, set the recent_ptr to the new tail, and
reduce the current degree.
Else...in this last case we must have a new zero coefficient for a
node that is neither the head nor the tail. We just remove this node
and set the recent_ptr to the next node in the list.
Modify the other polynomial member functions to use the dynamic
array.
Rewrite next_term
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(e1). Normally, the
right answer is then in the recent_ptr
node (but again,
there is one exception that you need to handlethe case where
the node has exponent and coefficient of zero).

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
(main@colorado.edu)