| A polynomial may be represented as a linked list where each node contains
the coefficient and exponent of a term of the polynomial. For example,
the polynomial 4x3 + 3x2 - 5, would be represented
as shown at right. |
|
Write a program that reads two polynomials from the keyboard, stores them as linked lists, adds them together to form a third linked list, and then prints the result as a polynomial. For the polynomial above, input would be: 4 3 3 2 -5 0.
Hint: Traverse both polynomials and if a particular exponent value is present in only one of the two polynomials being summed, then it should be present in the answer. If it is present in both polynomials, then its coefficient is the sum of the corresponding coefficients in both polynomials. If this sum is zero, the term of course, should be deleted. Also, coefficient 1 and -1 is not shown unless the exponent is zero.
Use the term definition shown here on this lab.
struct term
{
int coef;
int exp;
term * next;
term (int C, int E, term * T)
: coef (C),
exp (E),
next T)
{ }
};
We have not yet indicated the order of storing the terms of the polynomial.
If we allow them to be stored in any order, then it might be difficult to recognize
that x5 + x2 - 3 and -3 + x5 + x2 and
x2 -3 + x5 all represent the same polynomial. Hence we adopt
the convention that the terms of every polynomial be stored in the order of decreasing
exponents within the linked list, and we further assume that no two terms have the same
exponent, and that no term has a zero coefficient.Below are three input/output examples:
|
Sample Input |
Expected Output |
line 1: 2 3 -4 2 -5 0 line 2: 2 2 7 1 6 0 2x^3-2x^2+7x+1 line 1: 4 3 -2 1 7 0 line 2: -4 3 5 1 -7 0 3x line 1: -3 5 2 4 -1 3 1 1 line 2: 2 3 -1 1 8 0 -3x^5+2x^4+x^3+8Challenge Allow inputting polynomials in any order of exponents but display the sum polynomial in descending order as above.