CS46B



CS46B Polynomials with java.util LinkedList class

Revise your polynomial class so that the coefficients are stored in the LinkedList class in java.util. The LinkedList class is one of the Java Collections Classes. As described below you will also want to use java.util’s Iterator and ListIterator classes. Documentation for these classes is in the files LinkedList.html, Iterator.html, and ListIterator.html. You should find these in a directory such as jdk1.3\docs\api\java\util or jdk1.4\docs\api\java\util (you may need to search a bit for these) or on the web at java.docs. You may also want to look at jdk1.3\docs\guide\collections\overview.html for an overview of the Java collections classes. Except for EasyReader do not use any code from Main, such as DoubleNode,. Also do not use arrays or any collection classes other than LinkedList in your program.

Make use of ListIterator (if you need to change values in the list) and Iterator (if you only need to access values in the list) to move through your linked list. Do this so that that inputting, outputting, evaluating and adding polynomials of degree n can be done in O(n) operations. Do not use the LinkedList’s get(int index) or set(int index, Object element). Use of get or set can increase the operation count to O(n 2 ).

As an example I will give you the code for multiplying two polynomials:

/**

* Multiplies two polynomials.

* @param f one of the polynomials

* @param g the second polynomial

* @return the product of the two polynomials

**/

public static Polynomial multiply(Polynomial f, Polynomial g)

{ // Note that the instance variables (declared earlier) of this class include

// private int degree ; // the degree of the polynomial

// private LinkedList coef; // a linked list (from java.util.*) storing

// // the polynomial coefficients starting with the 0th power

// // and storing 0 for the coefficient of any missing powers

// This implementation of polynomial multiplication uses iterators in order

// to illustrate their use and to write a code that is O(n^2) when

// multiplying two nth degree polynomials. Note that use of methods

// that require traversals such as LinkedList's get(int index) or

// set(int index,Object element) can make the operation count O(n^3).

Polynomial h = new Polynomial(f.degree + g.degree) ; // the constructor sets

// the degree of h and assigns zero to each coefficient of h

int i = 0; // i keeps track of the coefficient of f

Iterator fIterator = (f.coef).iterator() ; // at the 0th coefficient of f

while (fIterator.hasNext( ) ) // loop over the coefficients of f

{

ListIterator hIterator = (h.coef).listIterator( ); // at 0th coefficient of h

for( int k = 0 ; k < i ; k++ ) // move to the ith coef of h

{ hIterator.next( ); //Note ListIterator hIterator = (h.coef).listIterator(i);

} // would do the same thing here

double a = ( (Double) fIterator.next( ) ).doubleValue( ); // the ith coef of f

i++; // i increases due to the fIterator.next( ) call

Iterator gIterator = (g.coef).iterator( ); // at the 0th coefficient of g

int j = 0; // j keeps track of the coefficient of g

while (gIterator.hasNext( ) ) // loop over the coefficients of g

{

double b = ( (Double) gIterator.next( ) ).doubleValue( ); // coefficient j of g

j++; // j increases due to the gIterator.next( ) call

double c = ( (Double) hIterator.next( ) ).doubleValue( ); // coefficient i+j of h

c = c + a * b ; // calculate new coefficien of h

hIterator.set( new Double( c ) ) ; // reassign coefficient i + j of h

}

}

return h;

}

Do the same runs as in program 2 (so you will need to include equals and clone). You should be able to use exactly the same code for main as for program 2 (different implementations of a class should not change how the class is used) except I want you to add one line at the end of your main program: System.out.println("\nUsing toString f is: \n" + f); . Your Polynomial class should include a reasonable toString method. Note that the LinkedList class comes with its own equals, toString and clone methods that will make your equals, clone and toString easier to write. You should use these built in methods in writing the methods for your Polynomial class.

Turn in printouts of the four runs and listings of your source code. Also turn in a disk with Polynomial.java (now using java.util’s LinkedLists), and TestPolynomial.java, as well as EasyReader or FormatWriter, if you use them. Again place all these in the same directory (so delete the package statements from EasyReader and FormatWriter). Test your code on Sun’s Java (jdk 1.3 or 1.4) and TextPad before turning it in.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download