java算法：基于应用ADT例子

例1：多项式ADT接口

classPoly{
Poly(int,int)
doubleeval(double)
voidadd(Poly)
voidmult(Poly)
publicStringtoString()
}

class Poly{
	Poly(int,int)
	double eval(double)
	void add(Poly)
	void mult(Poly)
	public String toString()
}

例2：多项式客户程序

publicclassBinomial{
publicstaticvoidmain(Stringargs[]){
intN=100;
doublep=1.1;
Polyy=newPoly(1,0);
Polyt=newPoly(1,0);
t.add(newPoly(1,1));
for(inti=0;i<N;i++){
y.mult(t);
System.out.println(y+"");
}
System.out.println("value:"+y.eval(p));
}
}

public class Binomial{
	public static void main(String args[]){
		int N = 100;
		double p = 1.1;
		Poly y = new Poly(1,0);
		Poly t = new Poly(1,0);
		t.add(new Poly(1,1));
		for(int i = 0; i < N; i++){
			y.mult(t);
			System.out.println(y + " ");
		}
		System.out.println("value: " + y.eval(p));
	}
}

例3：多项式ADT的数组实现

classPoly{
privateintn;
privateint[]a;
Poly(intc,intN){
a=newint[N+1];
n=N+1;
a[N]=c;
for(inti=0;i<N;i++){
a[i]=0;
}
}
doubleeval(doubled){
doublet=0.0;
for(inti=n-1;i>=0;i--){
t=t*d+(double)a[i];
}
returnt;
}
voidadd(Polyp){
int[]t=newint[(p.n>n)?p.n:n];
for(inti=0;i<p.n;i++){
t[i]=p.a[i];
}
for(intj=0;j<n;j++){
t[j]+=a[j];
}
a=t;
n=t.length;
}
voidmult(Polyp){
int[]t=newint[p.n+n-1];
for(inti=0;i<p.n;i++){
for(intij=0;j<n;j++){
t[i+j]+=p.a[i]*a[j];
}
}
a=t;
n=t.length;
}
publicStringtoString(){
Strings="";
for(inti=0;i<n;i++){
s+=a[i]+"";
}
returns;
}
}

class Poly{
	private int n;
	private int[] a;
	Poly(int c,int N){
		a = new int[N+1]; 
		n = N + 1; 
		a[N] = c;
		for(int i = 0; i < N; i++){
			a[i] = 0;
		}
	}
	double eval(double d){
		double t = 0.0;
		for(int i = n - 1; i >= 0; i--){
			t = t * d + (double)a[i];
		}
		return t;
	}
	void add(Poly p){
		int[] t = new int[(p.n > n) ? p.n : n];
		for(int i = 0; i < p.n; i++){
			t[i] = p.a[i];
		}
		for(int j = 0; j < n; j++){
			t[j] += a[j];
		}
		a = t;
		n = t.length;
	}
	void mult(Poly p){
		int[] t = new int[p.n + n -1];
		for(int i = 0; i < p.n; i++){
			for(inti j = 0; j < n; j++){
				t[i+j] += p.a[i] * a[j];
			}
		}
		a = t;
		n = t.length;
	}
	public String toString(){
		String s = "";
		for(int i = 0; i < n; i++){
			s += a[i] + " ";
		}
		return s;
	}
}

注意：Horner算法：a₄x⁴ + a₃x³ + a₂x² + a₁x + a₀ = (((a₄x + a₃)x + a₂)x + a₁)x + a₀