P(x) = x_n x^n + .... + x_3 x^3 + x_2 x^2 + x_1 x^1 + x_0 x^0
For example
P_1(x) = x^5 + x - 1 and P_2(X) = x^3 - 5x + 1
are both polynomials. In this assignment you will design and
implement a class for symbolic manipulation of polynomials with
integer coefficients. By symbolic we mean that a polynomial P(x)
will be represented by a list containing its coefficients and
exponents (powers).
When displaying a polynomial its terms should be output from
largest exponent to smallest. Terms with coefficients equal to
zero
are not displayed. A term with exponent equal to 0 does
not
show the exponent since x^0 =1. A term with exponent equal
to 1 should be written as cx instead of cx^1. Also,
any coefficients
equal to 1 should not be displayed. Thus, we write
x^4 + 2x^3 + x - 4 instead of 1x^4 + 2x^3 +0x^2 + 1x^1 - 4x^0
The one exception to the rules above is that the zero polynomial
Q(x) = 0
should be written out as
Q = 0.
Addition and subtraction of polynomials is done on a term by term
basis. For example, referring to the two polynomials defined
above,
setting
Q = P_1 + P_2
means that
Q(x) = x^5 + x^3 -4x
Multiplication is the standard polynomial multiplication.
For example, if
R_1(x) = x^2 + 1
and R_2(X) = x^3 - 2
setting
Q = R_1*R_2
means that
Q(x) = x^5 + x^3 - 2x^2 - 2
Since many polynomials have a large number of zero terms
it
is convenient to represent them using a sparse pointer-based
linked-list representation rather than an array based one. This
means that the list will store only the Terms of the polynomial
with non-zero coefficients where a Term is of the form c
x^p.
As an example, your data structure for the polynomial
P = 5x^100 + 2x
should only store the two terms 5x^100 and
2x.
It should not store any of the zero terms between them.
You assignment is to write a a class polyClass whose interface is
// constructors
// Creates a polynomial P(x) = 0;
polyClass();
// Creates a polynomial P(x) = c x^p
polyClass(int c, int p);
// Copy Constructor -- makes a deep copy
of P
polyClass(const polyClass& P);
//destructor -- needs to deallocate dynamically allocated data
~polyClass();
// assignment operator -- makes a deep copy
void operator=(const polyClass& P);
// Prints the polynomial following the instructions above
void Display();
//Prints YOUR name, ID Number, Lecture and Lab section
//This will be used for marking purposes
void Identify_Writer();
It should also support the following four functions that are friends
of the class
friend polyClass operator+( polyClass P1, polyClass P2);
friend polyClass operator-(polyClass P1, polyClass P2);
friend polyClass operator*(polyClass P1, polyClass P2);
friend int operator==(polyClass P1, polyClass P2);
where P1+P2 and P1-P2 return the associated sum and
difference polynomials and P1*P2 returns the associated
product polynomial. P1==P2 should return 1 if the two
polynomials are the same (term by term) and 0 if they
are not the same.
You should write two files:
Poly.h containing the class definition
and Poly.cpp containing the class
and friend
function implementations. We will test your files by compiling
them together with another program that will call all of your
functions and check if they perform correctly.
You must test your files yourself and satisfy yourself that
you've covered all possibilities.
We provide a small driver program CheckPoly.cpp
that can be compiled together with
Poly.h and Poly.cpp
to test a few cases. Here
is the output
(revised on 18/4/01 -- see Notes below)
of CheckPoly.
Note that this program DOES NOT cover all possible
test cases or functions and is not the program that we will
actually use to compile your program
Documentation: Both files should contain your name, student ID,
lecture
and Lab section at the top of the file in comments. Also, you
should
document the implementation of every function, describing what
it does.
Finally, be sure that you indent your code so that it is readable.
Documentation will count towards part of the grade of this assignment.
If we can not read your program and easily understand from the documentation
what it is doing and why it works, we will deduct points.
Recall that a Term is an item of the form c
x^p
2 When writing your code you have many choices as to how
to implement the linked list code . One is to write
it from scratch.
Another is to take already existing linked list code and modify
it. Some
code that you can use if you want is found in NewListP.h
and
NewListP.cpp
(updated April 24 to correct a memory leakage problem).
Note
that this list code contains some functions
that you might not want to use. Also, if you do use this code,
you will have to modify the data field of the linked list to
contain
Term data. You can also try and modify the linked
list code you
saw in COMP104. A third possibility, for the adventurous, is
to try
and use the list type in C++.
3. Your program will be tested using the g++ running
under UNIX.
Before submitting it please make sure that you have tested that
your
code works properly in this environment.
4. Copying of work is not permitted. You may discuss
the problem
with other people but all of the code must be your own.
If you do
share ideas with other students you should acknowledge
their names
in comments at the top of your files.
5. The orginal output of CheckPoly had
an error (x was written as x^1).
This has now been corrected (18/4/01)
Create a file Poly.cpp containing the class and friend function implementations.
Add your student name, student id, email, and lab section in the very beginning of each file as comment
Create a directory "assign2" and place files Poly.h and Poly.cpp under ~/comp151/assign2
Our system will collect the files under ~/comp151/assign2 on Wednesday,
May 2, 2001 at 9:00 AM
(Please note that this date has been pushed later than the original
date announced in class in Lecture 1.)
Submit a hard copy of Poly.h and Poly.cpp at the beginning of class on Wednesday, May 2, 2001
In the case of differences between the soft copy electronically collected
and the hard copy submitted
in class, the soft copy will be considered as the authoritative submitted
copy.