Project 3
Due: Thursday, October 29, 2015 9:00PM
Objectives
- Practice using C++ class syntax
- Practice using C++ dynamic memory
- Practice using linked lists
Background
For this project, you will implement member functions of a C++ Polynomial class that stores univariate polynomials in linked lists. You will also complete the implementation of the Node class which describes linked list node. You will use C++ dynamic memory (new and delete) to allocate and destory nodes in the linked lists.
Polynomials are of fundamental importance in mathemtics as even very complex functions can often be approximated by polynomials. In addition, multi-precision numbers can be represented by polynomials. For example, the 192-bit number
1985008943614989521094070429257356021098061753208738173457
is represented by the quadratic polynomial
5833416998877842037 x^2 + 4432272967969985261 x + 10368951529917665809
with x equal to 264. Each coefficient of the polynomial requires at most 64 bits of storage, so this representation allows us to store and manipulate very large numbers on a computer with a 64-bit word size. This is especially useful for public key cryptographic algorithms which typically require arithmetic computations with large integers.
In addition to storing polynomials in linked lists, you will implement functions to add, subtract, and mutiply polynomials; to determine the degree of a polynomial; and to evaluate a polynomial for a given value of x. Lastly, you will overload the insertion operator (<<) to display a polynomial and the assignment operator (=) to make a deep copy of a Polynomial object.
Assignment
Your assignment is to implement the member functions of the classes Polynomial and Node, defined below. A Polynomial object has a single variable, m_head, which is a pointer to the first node in the linked list. Your linked list implementation must be space-efficient, only storing what is necessary to represent the polynomial. The first node of a linked list must be a "dummy" node; the code will be cleaner and easier to write if you can assume that there is always at least one node in the linked list.
You must implement polynomial addition and subtraction (the add() and subtract() functions) efficiently, making a single pass through the linked lists of the two operands. Implementation of the remaining functions is fairly straight-forward.
Here are the requirements for the Polynomial member functions:
- Polynomial(); The default constructor should set up the host object as an empty linked list, containing only a "dummy" node.
- Polynomial(const Polynomial& p); The copy constructor creates a new Polynomial object from an existing one; it must make a "deep" copy.
- ~Polynomial(); The destructor must delete all the nodes of the linked list in a Polynomial object.
- void insertMonomial(long coeff, unsigned int deg); The function inserts the monomial (coeff xdeg) into the linked list of the host object. If a monomial of the given degree is already present, it prints a warning message and leaves the host object unchanged.
- Polynomial add(const Polynomial& p) const; The function returns the mathematical sum of the host object and p. The implementation must be efficient, requiring only a single pass through each linked list.
- Polynomial subract(const Polynomial& p) const; The function returns the mathematical difference of the host object and p (host - p). The implemenation must be efficieint (see add(), above).
- Polynomial multiply(const Polynomial& p) const; The functions returns the mathematical product of the host polynomial and p.
- unsigned int degree() const; The function returns the degree (highest power of x) of the host object.
- long evaluate(long x) const; The function evaluates the polynomial for the given value of x.
- Polynomial& operator=(const Polynomial& p); The overloaded assignment operator performs a "deep copy" of p.
- friend ostream& operator<<(ostream& sout, const Polynomial& p); The overloaded insertion operator can be used to display a Polynomial object in standard mathematical notation. See the test output for a sample of acceptable output.
- Extra Credit: Polynomial modulo(const Polynomial& p) const; The function returns the remainder when dividing the host polynomial by p.
The Node class has two constructors, but no other functions. The variable m_coefficient stores the coefficient of a monomial and m_degree stores the degree (power of x) of a monomial; m_next is a pointer to the next node in the linked list.
Here are the requirements for the Node member functions:
- Node(); The default constructor initializes m_next to NULL.
- Node(long coeff, unsigned int deg); The construtor initializes m_ceofficient to coeff, m_degree to deg, and m_next to NULL.
Implementation Issues
Here are some issues to consider and pitfalls to avoid. (You should read these before coding!)
- Reminder: do not develop your programs in the submission directories. Develop your programs in some other location in GL or on your own computer. The files that you have in the submission directory should not be your only copy of your code.
- Your linked list implementation must be space-efficient, so you should not store any terms with coefficient zero. In particular, the zero polynomial is represented by a linked list having only the dummy node.
- It is a good idea to store the terms of your polynomial in order of decreasing degree. Standard mathematical notation writes polynomials in this order; storing the terms in the same order makes the implementation of the overloaded insertion operator easier. Also, in this case the degree of the polynomial is just the degree of the first non-dummy node in the linked list.
- The variables of the Node class are all public, so they can be accessed from within the Polynomial class without the need for accessors or mutators.
- The header files Polynomial.h and Node.h
and a test program test.cpp and sample
output test.out can be copied to your working directory
on GL:
cp /afs/umbc.edu/users/c/m/cmarron/pub/cmsc202/proj3.zip . unzip proj3.zip You should put your implementations of the Polynomial and Node member functions in the files Polynomial.cpp and Node.cpp, respectively. You should not have a main() function in Polynomial.cpp or Node.cpp; any main() functions should be in separate test or driver files. - On GL, you can compile the test program with your
implementation with one command, like this:
linux3% g++ -Wall -g test.cpp Polynomial.cpp Node.cpp or separately, like this:linux3% g++ -Wall -g -c Node.cpp linux3% g++ -Wall -g -c Polynomial.cpp linux3% g++ -Wall -g -c test.cpp linux3% g++ -g test.o Polynomial.o Node.o
Submitting your program
You should submit these files to the proj3 subdirectory:
- Polynomial.h The only change from the provided file should be the addition of private member function prototypes, if used.
- Polynomial.cpp This should contain your implementations of all of the Polynomial member functions. This file should not include a main() function.
- Node.cpp This should contain your implementations of all the Node member functions. This file should not include a main() function.
- mytest.cpp A main program that exercises the working parts of your submission. This is where you tell us what works. If you could not get some member function to work, don't test it here. We will test all functions with other programs.
If you followed the directions for setting up the shared directories, then you can copy your code to the submission directory with:
You can check that your program compiles and runs in the proj3 directory, but please clean up any .o and executable files. Again, do not develop your code in this directory; you need to keep the main copy of your program elsewhere.