program代做、Java编程语言代写

日期：2023-11-07 09:13

Implementing Polynomials in Java

Introduction

A polynomial,

P x( )

, is a mathematical function of the form:

The degree, d, of the polynomial is the largest exponent in any of the terms of the polynomial. For

example, the largest exponent in

polynomial. It is customary to write the term with the largest exponent first, followed by the term

with the next largest exponent and so on, with the constant term (which you can think of as the term

with exponent 0) appearing last. You may assume for the purposes of this assignment that all the

exponents are positive valued or 0.

The constants

0 1 , , , d

a a a

are the coefficients of the polynomial. The coefficients can be positive,

negative or zero (except for the term with d as its exponent – the coefficient of that term cannot be

zero). For example, the coefficients of

are 2, -4 and 1. Note that the coefficient

of the

x

term in

is 0.

In the first part of this assignment, you are required to develop your own classes to represent

polynomials in Java as double linked lists. The diagram below illustrates how the polynomial

is implemented as a linked list.

2

3

previous null

next

coefficient

exponent

-4

2

previous

next

coefficient

exponent

1

0

null

previous

next

coefficient

exponent

head

Notice that in the linked list:

? The list has as many nodes as there are terms in the polynomial.

? Each node in the linked list contains a value for the coefficient and a value for the exponent.

? The nodes in the linked list are ordered. Nodes with a higher exponent precede nodes with a

lower exponent (this is in keeping with the convention that terms with higher exponent are

written first).

? The constant term has an exponent of 0.

? Other than the first and last nodes in the linked list, each node references the previous node

and the next node in the list.

Page 2 of 4

? The reference to the previous node in the head of the list is set to null.

? The reference to the next node in the tail of the list is set to null.

In the second part of this assignment you will also need to implement the methods necessary to add,

subtract and multiply any 2 polynomials. Recall that only the ‘like’ terms (the terms with the same

variables and exponents) of a polynomial are added or subtracted. We commonly refer to the process

of adding or subtracting ‘like’ terms as ‘collecting like terms’. For example, if

To multiply 2 polynomials each term of the first polynomial is multiplied by each term in the second.

You then need to collect like terms so that there is only one term for each exponent. For example, if

Three classes are provided for you: PolyList, PolyNode, and PolyOpps. PolyList contains the

methods and fields for creating a double linked list of polynomial terms. PolyNode defines the fields

of the nodes in the linked list. PolyOpps contains the methods for adding, subtracting and multiplying

polynomials. You may add extra classes and you may add your own variables and methods to the

classes supplied. You MUST NOT change the existing variables and method signatures. If you

change them the automated marking program cannot check your submission and you will lose marks

as a result.

Part A: Representing a polynomial as a linked list

1. Write code for the addNode method in the PolyList class that inserts the new node in its

correct position in linked list (that is, all nodes before the new node in the list have larger

exponents and all nodes after the new node have smaller exponents). For example, addNode

should add a node for the

2

x

term after the node for the

3

x

term in the list but before the node

for the

x

term. If the list is empty then addNode should set the node as the head of the list.

addNode should return true if it successfully added the new node to the linked list. It should

return false and leave the linked list unchanged if the list already contains a node with the

same exponent. (15 marks)

2. Add code to the getDegree method that returns the degree of the polynomial. If the linked list

is empty then getDegree should return -1. (5 marks)

3. Implement the getNode method in the PolyList class. getNode should return a reference to

this node in the linked list that contains the specified exponent. getNode should return null if

no node in the list has the specified exponent. (10 marks)

4. Write code for the reduce method in the PolyList class that removes nodes from the linked list

with a coefficient of 0. The reduce method should leave the linked list unmodified if there are

Page 3 of 4

no nodes with a coefficient of 0. For example, the reduce method removes the middle node

that has a coefficient of 0 from the linked list below. (14 marks)

Linked list before reduce method:

2

3

previous null

next

coefficient

exponent

0

2

previous

next

coefficient

exponent

5

1

null

previous

next

coefficient

exponent

head

Linked list after reduce method:

2

3

previous null

next

coefficient

exponent

5

1

null

previous

next

coefficient

exponent

head

5. Implement the toString method so that it returns a string representation of the polynomial.

This must be completed for the testing program to correctly display. For a polynomial of

degree d, toString should return a string in the form:

For example, your toString method should return the string:

to represent the polynomial

Page 4 of 4

Part B: Adding, subtracting and multiplying polynomials

1. Implement the addPolys method of PolyOpps to add any 2 polynomials. Note that the

polynomials may not have the same degree. If either method argument is null, or if either

input polynomial contains one or more negative exponents then addPolys should throw an

IllegalArgumentException. If the method arguments are valid then addPolys should add the 2

polynomials and return a reference to a new linked list containing the resultant polynomial.

(14 marks)

2. Implement the subtractPolys method of PolyOpps to subtract any 2 polynomials. If either

method argument is null, or if either input polynomial contains one or more negative

exponents then subtractPolys should throw an IllegalArgumentException. If the method

arguments are valid then subtractPolys should subtract the 2 polynomials and return a

reference to a new linked list containing the resultant polynomial. (14 marks)

3. Write code in the multiplyPolys method of PolyOpps to multiply any 2 polynomials. If either

method argument is null, or if either input polynomial contains one or more negative

exponents then multiplyPolys should throw an IllegalArgumentException. If the method

arguments are valid then multiplyPolys should multiply the 2 polynomials and return a

reference to a new linked list containing the resultant polynomial. (18 marks)

Hint: To multiply 2 polynomials multiply each term in the first polynomial by each term in the

second polynomial. Remember that you will need to collect like terms so that there is at most

one node for each exponent in the resultant polynomial.

Total Marks: 100