java - 在java中使用链表进行多项式加法

Question

这是我使用链表实现的两个多项式相加的实现。
例如，如果我想添加
3x^2+5^x+3 和 4x^3+5x+2

首先，我检查两个多项式中是否有相似的指数，如果有，我将它们的系数相加，并将指数附加到一个字符串中。
添加相似的指数然后使用字符串后，我将两个多项式中的剩余部分添加到最终结果中。

 public class Node2{
        int coef;
        int exp;
        Node2 next;
        Node2(int c,int e,Node2 n){
            coef=c;
            exp=e;
            next=n;
        }
        Node2(int c,int e){
            coef=c;
            exp=e;

        }


}

public class LinkedPoly{
    static String exponent="";
    Node2 head;
    Node2 current;

LinkedPoly(){
    head=null;

}
public void createList(int c,int e){
    head=new Node2(c,e,head);
}

public static LinkedPoly add(LinkedPoly list1,LinkedPoly list2){
    LinkedPoly addList=new LinkedPoly();

    Node2 temp1=list1.head;
            Node2 temp3=temp1;
    Node2 temp2=list2.head;
            Node2 temp4=temp2;
    while(temp1.next!=null){
        while(temp2.next!=null){
            if(temp1.exp==temp2.exp){

            addList.createList((temp1.coef+temp2.coef),temp1.exp);
            exponent+=temp1.exp;

            }
            temp2=temp2.next;
        }
        temp1=temp1.next;
        temp2=temp4;
    }
    String[] array=exponent.split("");
    for(int i=1;i<array.length;i++){

        while(temp3.next!=null){
            if(temp3.exp!=Integer.parseInt(array[i])){
                addList.createList(temp3.coef,temp3.exp);
            }
            temp3=temp3.next;
        }
        while(temp4.next!=null){
            if(temp4.exp!=Integer.parseInt(array[i])){
                addList.createList(temp4.coef,temp4.exp);
            }
            temp4=temp4.next;
        }
    }

    return addList;
}


public static void main (String args[]){
    LinkedPoly l1=new LinkedPoly();
    l1.createList(3,2);
    l1.createList(5,1);
    l1.createList(3,0);
    LinkedPoly l2=new LinkedPoly();
    l2.createList(4,3);
    l2.createList(5,1);
    l2.createList(2,0);

    LinkedPoly l3=add(l1,l2);
    System.out.println(l3.head.next.next.coef);
}

}

根据我的示例，指数字符串包括 1 和 0 ，但它只对 1 的系数求和。此外，其余的加法也是错误的。

我看不出我哪里弄错了。还有我怎样才能打印出最终的 addList 以便我可以检查这个实现是否正常

Answer 1

这是一个有效的添加方法:

public static LinkedPoly add(LinkedPoly list1,LinkedPoly list2){
    LinkedPoly addList=new LinkedPoly();

    Node2 temp1=list1.head;
    Node2 temp3=temp1;
    Node2 temp2=list2.head;
    Node2 temp4=temp2;
    while(temp1.next!=null){
        while(temp2.next!=null){
            if(temp1.exp==temp2.exp){

                addList.createList((temp1.coef+temp2.coef),temp1.exp);
                exponent+=temp1.exp;

            }
            temp2=temp2.next;
        }
        temp1=temp1.next;
        temp2=temp4;
        addList.print();
    }
    String[] array=exponent.split("");


    while(temp3!=null){
        boolean exponentPresent = false;
        for(int i=1;i<array.length;i++){
            if(temp3.exp==Integer.parseInt(array[i])){
                exponentPresent = true;
            }
        }
        if (!exponentPresent) {
            addList.createList(temp3.coef,temp3.exp);
        }
        temp3=temp3.next;
    }
    while(temp4!=null){
        boolean exponentPresent = false;
        for(int i=1;i<array.length;i++){
            if(temp4.exp==Integer.parseInt(array[i])){
                exponentPresent = true;
            }
        }
        if (!exponentPresent) {
            addList.createList(temp4.coef,temp4.exp);
        }
        temp4=temp4.next;
    }


    return addList;
}

这是一个可以添加到 LinkedPoly 类的打印方法:

public void print() {
    current = head;
    System.out.print(current.coef + "x^" + current.exp);
    while (current.next != null) {
        current = current.next;
        System.out.print(" + " + current.coef + "x^" + current.exp);
    }
    System.out.println();
}

您的添加方法存在两个主要问题。

问题#1。第一个是你通过已经包含的指数数组的循环在你通过多项式链表的节点的循环之外 - 它应该在里面。按照您之前的做法，您的流程是这样的:

一个。从数组中取出一个已经包含的指数b.遍历每个多项式的所有项C。如果其中任何一项的指数与 a. 部分的指数不匹配，则将其添加到结果中。d.从 a. 部分开始重复，但使用下一个已经包含的指数。

这种方法的问题在于，如果新项的指数与任何已包含的项都不匹配，您只想向结果中添加一个新项 - 而不仅仅是它与其中一个项不匹配。这就是为什么你的结果有所有这些额外的 x^1 项——当你的程序位于数组的“0”元素时，它添加了多项式的 x^1 项。

问题#2。您应该将 while (temp3.next!= null) 或 (temp4.next!=null) 替换为 (temp3!=null) 或 (temp4!=null)。否则，您的代码永远不会到达多项式的最后一个节点(它在最后一个节点之前停止，因为它正在检查最后一个节点之后是否有“下一个”节点)。这就是为什么您的结果没有 x^3 和 x^4 项 - 您的循环在达到这些项之前就结束了。

需要考虑的几件事

1. 您使用了很多临时变量。尝试给它们起更具描述性的名称，或者更好的是，找到一种不用那么多的方法。
2. 我不确定为什么要将已使用的指数添加到“指数”字符串，然后使用 split() 方法将其分解为数组。考虑从一开始就添加到数组中。
3. 您的 add 方法可能会被重组为更简洁。与其查看你的两个多项式有哪些共同的指数，处理那些，然后分别处理它们没有共同的指数，不如试试这个:找到你的任何多项式中的最高指数。然后，循环遍历从 0 到该数字的所有指数度数。在每个循环中，循环遍历每个多项式，并将具有该指数的所有多项式的系数加在一起。这样一来，您的代码就会全部处于一个大循环中。
4. 现在，您的代码无法确保多项式按顺序排列它们的项 - 无法阻止 x^2 项出现在 x^3 项之前，x^3 项出现在 x^1 项之前。考虑向您的 LinkedPoly 类添加一个 sort() 方法，在添加节点期间添加一些代码以确保多项式保持有序，或者按照上面的建议 #3，这将允许您在创建多项式和时对其进行排序。或者，如果按顺序排列它们并不重要，请不要打扰:)