UE CS 215 - CS 215 ­ Fundamentals of Programming II

Unformatted text preview:

CS 215 - Fundamentals of Programming IIFall 2010 - Project 540 pointsOut: October 20, 2010Due: November 3, 2010For this project, you will need the linked list toolkit that was covered in Lecture 22 and defined in files node1.h and node1.cpp. To keep all the files for this project together, do the following:● Create a new subdirectory for this project. ● Put copies of the linked list toolkit files into this subdirectory. If you did not complete these files for the in-class assignment, you may copy the files on csserver in /home/hwang/cs215/linked-list-toolkit/*.*● Modify the copies so that they use namespace Project5.Problem StatementRecall from Project 3 that a polynomial is a mathematical expression involving a sum of powers in one or more variables multiplied by coefficients. A polynomial of degree n in one variable with constant coefficients is given bycnxn + cn-1xn-1 + ... + c1x + c0Generally the terms where the integer coefficients ci are 0 are not written, except for the polynomial of a single constant term of value 0. There are various implementation of polynomials. In Project 3, we represented a polynomial as a vector of doubles where the value at index i is the coefficient ci of the term cixi. If the polynomial is of low degree and few coefficients are 0, this is a reasonable representation. However, if a polynomial is sparse and its degree is high, this representation wastes a lot of space storing the 0 coefficients. E.g., x99 + 1 would require a vector of 100 elements, 98 of which would be 0.For sparse polynomials, instead of storing all of the coefficients, we would like to store only the terms that exist, so that for the example above, only two terms would be stored. Consider the following specification for a Polynomial class that models mathematical polynomials using a singly-linked list. First, we define a class to hold a term.Specification for Term classThe Term class is used to represent a single polynomial term. The term coefficient is generally non-zero and the exponent must be non-negative. For example, a Term with coefficient of 10 and an exponent of 3 represents the term 10x3. The Term class will be the type stored in a linked list Node (i.e., it will be the value_type typedef in node1.h.)Data Attributes Object Type Nameterm coefficient int coeffterm exponent int expo10/19/2010 1 of 6 D. HwangSince a Term object simply allows access to its attributes, we will make them public. In addition to an explicit-value constructor used to initialize a Term object, the linked list toolkit requires that operator<< and operator== be implemented.Operations ● Explicit-value constructor that creates a term by initializing the coefficient and exponent to the given arguments. Note that the default values create the constant term 0 value, which is the only term that is allowed to have a coefficient of 0.Analysis Objects Default Type Movement Nameinitial coefficient 0 int received initCoeffinitial exponent 0 int received initExpo● operator<< - free overloaded operator function that writes a (single) Term to an output stream in mathematical format with exponentiation represented by ^. For example, 10x^3. Note that non-constant terms with coefficient 1 or -1 do not show the coefficient (for example x^3 or -x^3), terms with exponent 1 do not show an exponent (for example, 2x), and the constant term does not show x or an exponent. Analysis Objects Type Movement Nameoutput stream ostream received, passed back, and returned outterm object Term received aTerm● operator== - free overloaded operator function returns true if the two Term objects represent that same polynomial term, false otherwiseAnalysisObjects Type Movement Namea term Term received lhsanother term Term received rhsresult of comparison bool returned -----Specification for Polynomial ClassData Attributes Object Type Namepointer to first term Node * headPtr10/19/2010 2 of 6 D. HwangA polynomial is modeled using a linked list of Nodes containing Term data items. The only attribute of the class is a pointer variable to the first node of the list. The Terms in the list are to be kept in decreasing exponent order. Only terms with non-zero coefficients should be present in a Polynomial object. However, all Polynomial objects must have at least one term, which implies that there is one exception to the non-zero coefficient rule - the constant term 0 value. The diagram below illustrates the structure of the polynomial 10x3 - 3x + 6.Operations ● Explicit-value constructor - creates a polynomial from a vector of double coefficients and a vector of integer exponents. You should assume that both vectors are the same size and that the exponents are in decreasing order. (I.e., you do not need to do error checking or sort the terms.) The ith coefficient is matched with the ith power to form a term of the polynomial. If the vectors are empty, the default constructed polynomial should be the constant term 0 value.Analysis Objects Default Type Movement Namevector of coefficients vector<double>( ) vector<double> received initCoeffsvector of exponents vector<int>( ) vector<int> received initExpos● Copy constructor - creates a new Polynomial that is identical to an existing one.Analysis Objects Type Movement Nameoriginal polynomial object Polynomial received source10/19/2010 3 of 6 D. Hwang3headPtrdataItem nextLink10coeffexp1-3coeffexp06coeffexpNode objects with Term data itemsPolynomial p ({10,-3,6},{3,1,0});● Destructor - deallocates the list nodes Analysis - no objects ● operator= - overloaded assignment operator function. Makes an existing Polynomial object identical to the original Polynomial object. In order to allow assignments to be chained together, operator= is to return a reference to the left operand (hence the return type is Polynomial &). Then whenever the function is to return, the following code returns the left operand (i.e., the left operand is the object where the function is executing): return *this; // "this" is a pointer, so need to dereferenceAnalysis Objects Type Movement Nameoriginal polynomial object Polynomial received sourcethis polynomial object Polynomial returned *this● Degree - returns the highest exponent of the polynomialAnalysisObjects Type Movement Namehighest exponent int returned -------● Evaluate - evaluate the polynomial at particular point, return result Analysis Objects Type Movement Namepoint of evaluation double received xresult of


View Full Document

UE CS 215 - CS 215 ­ Fundamentals of Programming II

Documents in this Course
Lecture 4

Lecture 4

14 pages

Lecture 5

Lecture 5

18 pages

Lecture 6

Lecture 6

17 pages

Lecture 7

Lecture 7

28 pages

Lecture 1

Lecture 1

16 pages

Lecture 5

Lecture 5

15 pages

Lecture 7

Lecture 7

28 pages

Load more
Download CS 215 ­ Fundamentals of Programming II
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CS 215 ­ Fundamentals of Programming II and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS 215 ­ Fundamentals of Programming II 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?