本文主要是介绍【DataStructure】Another usage of List: Polynomial，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Statements: This blog was written by me, but most of content is quoted from book【Data Structure with Java Hubbard】
【Description】
Apolynomialis a mathematical function of the form:
p(x) = a0xn+ a1xn–1+a2xn–2+ ˜˜˜+an–1x + an The greatest exponent, n, is called the degreeof the polynomial. For example, p(x) = 7x4– 2 is abpolynomial of degree 4. The simplest polynomials are constant polynomialssuch as p(x) = 6 (degree 0) and linear polynomialssuch as p(x) = 9x+ 6 (degree 1). The unique zero polynomial p(x) = 0 is defined to have degree –1. In this section we present a Polynomialclass whose instances represent mathematical polynomials and which supports the usual algebraic operations on polynomials.A polynomial can be regarded as a sum of distinct terms. A termis a mathematical function of the form t(x) = cxe, where cis any real number and eis any nonnegative integer. The number ciscalled the coefficient, and the number eis called the exponent.To define a class whose objects represent polynomials, we use a linked list of Termobjects.For example, the polynomial p(x) = 3x2–2x+ 5 could be represented as a list of three elements,where the first element represents the term 3x2, the second element represents the term – 2x, andthe third element represents the (constant) term 5.
【Implement】
package com.albertshao.ds.polynomial;// Data Structures with Java, Second Edition // by John R. Hubbard // Copyright 2007 by McGraw-Hillimport java.util.*;public class Polynomial {private List<Term> list = new LinkedList<Term>();public static final Polynomial ZERO = new Polynomial();private Polynomial() {}public Polynomial(double coef, int exp) {if (coef != 0.0) {list.add(new Term(coef, exp));}}public Polynomial(double... a) {for (int i=0; i<a.length; i++) {if (a[i] != 0.0) {list.add(new Term(a[i], i));}}}public Polynomial(Polynomial p) { // copy constructorfor (Term term : p.list) {this.list.add(new Term(term));}}public int degree() {if (list.isEmpty()) {return -1;} else {return list.get(list.size()-1).exp;}}public boolean isZero() {return list.isEmpty();}public Polynomial plus(Polynomial p) {if (this.isZero()) {return new Polynomial(p);}if (p.isZero()) {return new Polynomial(this);}Polynomial q = new Polynomial();ListIterator<Term> it = list.listIterator();ListIterator<Term> itp = p.list.listIterator();while (it.hasNext() && itp.hasNext()) {Term term = it.next();Term pTerm = itp.next();if (term.exp < pTerm.exp) {q.list.add(new Term(term));itp.previous();} else if (term.exp == pTerm.exp) {q.list.add(new Term(term.coef + pTerm.coef, term.exp));} else { // (term.exp > pTerm.exp) q.list.add(new Term(pTerm));it.previous();}}while (it.hasNext()) {q.list.add(new Term(it.next()));}while (itp.hasNext()) {q.list.add(new Term(itp.next()));}return q;}public String toString() {if (this.isZero()) {return "0";}Iterator<Term> it = list.iterator();StringBuilder buf = new StringBuilder();boolean isFirstTerm = true;while (it.hasNext()) {Term term = it.next();double c = term.coef;int e = term.exp;if (isFirstTerm) {buf.append(String.format("%.2f", c));isFirstTerm = false;} else {if (term.coef < 0) {buf.append(String.format(" - %.2f", -c));} else {buf.append(String.format(" + %.2f", c));}}if (e == 1) {buf.append("x");} else if (e > 1) {buf.append("x^" + e);}}return buf.toString();}private class Term {private double coef;private int exp;public Term(double coef, int exp) {if (coef == 0.0 || exp < 0) {throw new IllegalArgumentException();}this.coef = coef;this.exp = exp;}public Term(Term that) { // copy constructorthis(that.coef, that.exp);}} }
// Data Structures with Java, Second Edition // by John R. Hubbard // Copyright 2007 by McGraw-Hillpackage com.albertshao.ds.polynomial;public class TestPolynomial {public static void main(String[] args) {Polynomial p = new Polynomial(3, -8, 0, 0, 2, 1);Polynomial q = new Polynomial(0, 5, 6, 9);System.out.println("p: " + p);System.out.println("p.degree(): " + p.degree());System.out.println("q: " + q);System.out.println("q.degree(): " + q.degree());System.out.println("p.plus(q): " + p.plus(q));System.out.println("q.plus(p): " + q.plus(p));System.out.println("p.plus(q).degree(): " + p.plus(q).degree());Polynomial z = new Polynomial(0);System.out.println("z: " + z);System.out.println("z.degree(): " + z.degree());System.out.println("p.plus(z): " + p.plus(z));System.out.println("z.plus(p): " + z.plus(p));System.out.println("p: " + p);Polynomial t = new Polynomial(8.88, 44);System.out.println("t: " + t);System.out.println("t.degree(): " + t.degree());} }【Result】
p: 3.00 - 8.00x + 2.00x^4 + 1.00x^5 p.degree(): 5 q: 5.00x + 6.00x^2 + 9.00x^3 q.degree(): 3 p.plus(q): 3.00 - 3.00x + 6.00x^2 + 9.00x^3 + 2.00x^4 + 1.00x^5 q.plus(p): 3.00 - 3.00x + 6.00x^2 + 9.00x^3 + 2.00x^4 + 1.00x^5 p.plus(q).degree(): 5 z: 0 z.degree(): -1 p.plus(z): 3.00 - 8.00x + 2.00x^4 + 1.00x^5 z.plus(p): 3.00 - 8.00x + 2.00x^4 + 1.00x^5 p: 3.00 - 8.00x + 2.00x^4 + 1.00x^5 t: 8.88x^44 t.degree(): 44
这篇关于【DataStructure】Another usage of List: Polynomial的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
