polynomial.java

用JAVA写的多项式加法

/*多项式加法，用链表实现
 *Write by zhangyi 2006-10*/
public class Polynomial{
	private List terms=new List();
/*插入一个节点，插入时通过比较使节点按降序排列*/
	public void insertTerm(int coef,int exp){
		List itr=terms;
		while(true){
			if(itr.next==null){
			   itr.next=new List(coef,exp,itr.next);
			   break;//空链表时直接插入
			}
			else{
			if(exp<itr.next.exponent)
			itr=itr.next;//迭代
			else {
				itr.next=new List(coef,exp,itr.next);
				break;
			}}			
		}
	}
/********多项式相加******/
	public void add(Polynomial rhs){
		List pa=terms.next;
		List pb=rhs.terms.next;//临时指针
		List pc=terms;//指向结果链表的尾部
		while(pa!=null&&pb!=null){//没有一个链表遍历完
			if(pa.exponent==pb.exponent){//指数相等，系数相加
			    pa.coefficient=pa.coefficient+pb.coefficient;
			    pb=pb.next;
			    if(pa.coefficient==0){//系数为0，删除节点
			      pc.next=pa.next;
			      pa=pa.next;//pa前进
			    }
			    else{//不为0，pa,pc都前进
			    	pc.next=pa;
			    pc=pa;
			    pa=pa.next;
			    }		    
		    }
		    //不等时，pc指向指数大的一个
		    else if(pa.exponent<pb.exponent){
		    	pc.next=pb;
		    	pc=pb;
		    	pb=pb.next;
		    }
		    else{
		    	pc.next=pa;
		    	pc=pa;
		    	pa=pa.next;
		}
		if(pa==null)//有链表遍历完后，把另一个加上去
		pc.next=pb;
		else pc.next=pa;

	}
}
/***********************打印链表****************************************/
	public void print(){
		List itr=terms.next;
		System.out.print(itr.coefficient+"X"+itr.exponent+" ");
		itr=itr.next;
		for(;itr!=null;itr=itr.next){
			if(itr.coefficient>0)
			System.out.print("+"+itr.coefficient+"X"+itr.exponent+" ");
		  else
		  System.out.print(itr.coefficient+"X"+itr.exponent+" ");
		}
		  System.out.println();
	}
	public static void main(String args[]){
		Polynomial l1=new Polynomial();
		Polynomial l2=new Polynomial();
		{l1.insertTerm(10,1000);l1.insertTerm(2,14);l1.insertTerm(1,0);}
		//初始化链表1
		System.out.print("L1=");
		l1.print();
		{l2.insertTerm(3,1990);l2.insertTerm(-2,14);l2.insertTerm(11,1);l2.insertTerm(5,0);}
		//初始化链表2
		System.out.print("L2=");
		l2.print();
		l1.add(l2);
		System.out.print("L1+L2=");
		l1.print();
	}
}