多項式相加可利用串列完成,其資料之表示方法如下:
COEF | EXP | LINK |
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);
}
}
關於作者
粉絲專頁
文章分類