Using c++ to build a linked list that represents a polynomial function:

ABOUT THIS PROJECT:

A keyed list is an ordered list in which each item consists of two parts: a key value that determines the item's position in the list, and other data associated with and identified by the key.

A polynomial function f (x) is a function of one variable x of the form

where the c_i (the coefficients) are real numbers and the e_i (the exponents) are distinct non-negative integers. Multiplying a polynomial by a constant multiplies all the polynomial's coefficients by the constant.

Consider one term cx^e of a polynomial function. The derivative of this term is cex^e-1, if e > 0; and 0, if e = 0 (that is, if the term is constant). The derivative f '(x) of a polynomial function f (x) is the sum of the derivatives of its terms. Note that the derivative of a polynomial function is itself a polynomial function.

A polynomial function can be represented by an ordered linked list each of whose nodes represents one term of the function. Each node holds two data items: a real number (a coefficient) and an integer (an exponent). The exponents act as keys in such a list: the nodes representing terms are maintained in order of increasing exponents. For example, the following linked list represents the polynomial f (x) = 5.5 + 2.7*x² - 6.2*x³ + 3.5*x⁶.

REQUIREMENTS

Your are to design, implement, document, and test a polynomial function class that represents a polynomial as a keyed linked list and an interactive, menu-driven program that exercises and tests this class. The class must provide the following operations.

-A default constructor. The default value of a polynomial is 0.0.

-A copy constructor.

-A destructor, since the lists that represent polynomials are dynamic objects.

-A function that inserts a new term into a polynomial. If the polynomial already contains a term with the same exponent, the new term is added to the existing one.

-A function that assigns one polynomial to another. Overload the assignment operator '=' to name this function.

-A function that multiplies a polynomial by a real constant.

-A function that returns the degree of a polynomial.

-A function that reports the derivative of the polynomial that invokes it.

-A function that prints a polynomial to an output stream. Overload the output operator "

The program that exercises this class will be menu-driven and interactive, as in the previous program. It will manipulate one polynomial and provide commands that invoke (most of) the operations listed above. It must also read in sequences of real and integer pairs that specify the terms of polynomials. The program will call the insert() function to build a polynomial corresponding to such input.

INPUT

The program will read one-letter commands, values associated with commands, and real/integer pairs of values that specify terms of polynomials. These pairs will always consist of a real value (a double) followed by an integer, but terms/pairs may occur in any order. In particular, there is no guarantee that lower exponents will always precede higher ones, nor that an exponent will not appear more than once.

OUTPUT

The program will write its menu of commands, prompt for commands, and write out the polynomial when instructed to do so.

ERRORS

The program may assume that the input is correct; it need not check for any errors.

EXAMPLE

A session with the program might look like this:

This program responds to commands the user enters to

manipulate a polynomial function. The function

is initially 0.0.

In the following commands, v is a double value and

n is a non-negative integer.

i v n -- Insert the term v*x^n into the polynomial.

r -- Reinitialize the polynomial to 0.

g -- Report the degree of the polynomial.

m v -- Multiply the polynomial by v.

d -- Report the derivative of the polynomial.

w -- Write out the polynomial.

h -- See this menu.

q -- Quit the program.

--> i 2.5 8

--> i -3.2 5

--> i 6.7 0

--> i 10.5 3

--> w

f(x) = 6.7 + 10.5*x^3 - 3.2*x^5 + 2.5*x^8

--> g 0

The polynomial has degree 8.

--> m 3.0

--> w

f(x) = 20.1 + 31.5*x^3 - 9.6*x^5 + 7.5*x^8

--> d

f'(x) = 94.5*x^2 + 48*x^4 + 60*x^7

--> w

f(x) = 20.1 + 31.5*x^3 - 9.6*x^5 + 7.5*x^8

--> q

OTHER REQUIREMENTS

Implement a polynomial function abstract data type in a class. This class will implement the ADT as a keyed, ordered linked list as described above. The main program will use this class and the functions that it provides.

In the main program, write a menu function that displays instructions and lists the program's commands.

SOME ADVICE

The polynomial class is specific to the representation of polynomials. Its nodes will always include a double coefficient and an integer exponent (and a pointer). Thus there will be no typedef statements to specify the types of items.

The key values in lists that represent polynomials are the exponents of the polynomial's terms, and they ascend from the first node to the last in the list that represents a polynomial.

Be sure to test inputs in which the exponents of a polynomial's terms are not in ascending order, and in which the same exponent appears more than once.

The client program presents the menu and processes commands. For the latter, consider a big switch statement within a while loop.