串列之應用—多項式相加

多項式相加

多項式相加可利用串列完成，其資料之表示方法如下:

COEF是係數，EXP是指數，而LINK則指向下一個節點。

若A=3x^14 + 2x^8 + 1 ，B=8x^14 - 3x^10 + 10x^6，則其放入串列之中則為:

本文將以A+B式舉例。

1.此時A.B兩式之第一個節點的EXP相同(14)，則將兩者係數相加(3+8)存入C串列，並同時讓A與B之指標同時向下一個節點

2.由於第二個節點A之EXP(8) < B之EXP(10)，則將B之第二個節點放入C串列，並讓B串列的指標指向下一個節點

3.此時為A的第二個節點與B的第三個節點比較，由於A的EXP(8) > B的EXP(6)，則將A的第二個節點放入C串列，並讓A串列指向下一個指標，以此類推。

總和上述，就是將A與B串列比較指數，讓指數大的先放入C串列，若兩者相同，則相加後再放入C串列。放入C串列之後，記得讓A或B串列指向下一個指標。

範例程式碼

import java.util.Scanner;

class poly{
    
    public int coef,exp;
    public poly next;

}
public class PolyLinkList {

    public poly ptr,eq1,eq2,ans;
    
    public poly input(){
        
        poly eq=null,prev=null;
        Scanner input=new Scanner(System.in);
        while(true){
            
            System.out.println("請輸入係數:");
            ptr=new poly();
            ptr.coef=input.nextInt();
            if(ptr.coef==0)
                return eq;
            
            System.out.println("請輸入指數:");
            ptr.exp=input.nextInt();
            
            if(eq==null){
                
                eq=ptr;
            
            }
            else{
                
                prev.next=ptr;
            
            }
            prev=ptr;
        
        }
        
    }
    
    public void add(){
        
        poly this1=eq1,this2=eq2,prev=null;
        while (this1!=null || this2!=null){
            
            ptr=new poly();
            ptr.next=null;
            //當第一個多相式不為空，或第一個多項式指數大於第二個多項式指數
            if((this1!=null && this2==null) || this1!=null && this1.exp>this2.exp){
                
                ptr.coef=this1.coef;
                ptr.exp=this1.exp;
                this1=this1.next;
                
                
            }
            else if(this1==null || (this2.exp>this1.exp)){
                
                ptr.coef=this2.coef;
                ptr.exp=this2.exp;
                this2=this2.next;
                
            }
            else{
                
                ptr.coef=this1.coef + this2.coef;
                ptr.exp=this1.exp;
                if(this1!=null)
                    this1=this1.next;
                if(this2!=null)
                    this2=this2.next;
                
            }
            
            if(ptr.coef!=0){
                
                if(ans==null)          
                    ans=ptr;
                else
                    prev.next=ptr;
                prev=ptr;
                
            }
            else
                ptr=null;
            
        }
        
    }
    
    public void print(poly node){
        
        if(node.coef<0)
            System.out.printf("-%dx^%d",node.coef,node.exp);
        else
            System.out.printf("%dx^%d",node.coef,node.exp);
        node=node.next;
        while(node!=null){
            
            if(node.coef >0)
                System.out.printf("+%dx^%d", node.coef,node.exp);
            else
                System.out.printf("-%dx^%d",node.coef,node.exp);
            node=node.next;
        }
        
        
    }
    
    
    public static void main(String[] args) {
        PolyLinkList obj = new PolyLinkList();
        System.out.println("----請輸入第一個多項式----");
        obj.eq1=obj.input();
        System.out.println("----請輸入第二個多項式----");
        obj.eq2=obj.input();
        System.out.println("----第一個多項式----");
        obj.print(obj.eq1);
        System.out.println();
        System.out.println("----第二個多項式----");
        obj.print(obj.eq2);
        System.out.println();
        System.out.println("----相加結果----");
        obj.add();
        obj.print(obj.ans);
    }
    
}