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 non-interactive 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
doubly-linked list to store. You'll need to copy your
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).
poly2.hand look at the new private member variables for the
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
mutablekeyword will be covered in class. But a brief explanation now: Our plan is to keep the
recent_ptralways pointing to the most recently-used node. For example, when we call the
coefficientmember function, we will move the
recent_ptrto point to the node that contains the requested exponent. With a normal member variable, we could not do this (since the
coefficientis a const member function and it is forbidden from changing normal member variables). So, the meaning of the
mutablekeyword 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 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).
reservemember function (and delete any places where you called the
poly2.hheader 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_recentfunction will set the
recent_ptrto the node that contains the requested exponent. If there is no such exponent, then
recent_ptrshould be set to the last node that is still less than the specified exponent. Note that
set_recentis a const member function, but that it can still change the mutable
recent_ptrmember variable. My implementation of
set_recentused three cases:
recent_ptrto the head of the list.
recent_ptrto the tail of the list.
recent_ptrforward 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 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.
assign_coeffunction. After calling
set_recent(exponent), my implementation had these cases:
recent_ptr->exponent( ) is less than the new exponent).
- Else if the coefficient is non-zero 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.
previous_termso 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_ptrnode (but again, there is one exception that you need to handle--the 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
coefficient. I told you that it would save work to avoid accessing those member variables directly!