This assignment will take time to solve. Begin early. Ask questions early if you have them. DO NOT WAIT TO GET STARTED.
This is an assignment in the use and creation of abstract data types. It involves two abstract data types and a program that uses them. It is required that there be separate files for each of the two abstract data types and a separate file for the application program. Do not violate the abstractions.
To implement this, prepare a refinement plan. That is, decide in what order you will implement different parts of the program. Then choose reasonable deadlines by which each part should be finished and tested. Be sure to leave extra room at the end for unforseen difficulties. Do not just type the whole program and then try to debug it.
Implement an abstract data type of polynomials called Polynomial. This will be a persistent ADT. That is, the functions will create new polynomials without destroying old ones. The interface should be as follows. It shows function prototypes in bold, followed by descriptions of what those functions are supposed to do.
Type: Polynomial. You can assume that polynomials only need to be stored up to some maximum degree (say 30), but it must be very easy to change this maximum degree in your program.
Polynomial Constant(double c); This function should return a constant polynomial c. For example, Constant(3.4) should return the polynomial 3.4.
Polynomial Linear(double a, double b); This function should return the polynomial ax + b.
Polynomial Sum(Polynomial p, Polynomial q); This function should compute the sum of polynomials p and q, and return that sum. It should allocate memory to store the result polynomial.
Polynomial Product(Polynomial p, Polynomial q); This function computes the product of polynomials p and q, and returns that product. It should allocate memory to store the result polynomial.
Polynomial Negative(Polynomial p); This function should return the negation of polynomial p.
void Print(Polynomial p); This function should print polynomial p on the standard output. To make things easy, print the polynomial just by showing its coefficients. Polynomial 3.4*x^2 + 5 should be printed as [3.4 0 5].
void DeletePolynomial(Polynomial p); This function should delete the memory occupied by polynomial p.
Polynomial DuplicatePolynomial(Polynomial p); This function should make a copy of polynomial p in new memory. This function must be designed so that doing
Polynomial q = DuplicatePolynomial(p); DeletePolynomial(p);leaves polynomial q still viable; its memory has not been deleted.
Now think about algorithms. Functions that compute new polymomials always allocate new space for the result. Addition is simple, since it is componentwise. That is, you just add corresponding coefficients. But be careful; multiplication is not componentwise. For example, (x^2 + 2x + 4)*(3x^2 - x + 9) = 3x^4 + 5x^3 + 13x^2 + 14x + 36.
Polynomial multiplication can be accomplished in a way that is quite similar to the way you learned to multiply integers in grade school. But with polynomials, there is no carry. Also, you don't need to store all of the intermediate results as you go. Just accumulate the coefficients in one answer array. Think carefully about how to do this before trying to code it.
Here is an example session. Lines in black are typed by the user. Lines in red are typed by the program.
fred = c 2.0 fred = [2]rod = l -1.0 0.0 rod = [-1 0]
zz = l 2.5 4.1 zz = [2.5 4.1]
m = + rod fred m = [-1 2]
sq = * rod rod sq = [1 0 0]
t = + sq rod t = [1 -1 0]
rod = + fred fred rod = [4]
Do not include much error checking in this program. Assume that the input is reasonable.