如何排序一个链表的多项式的程度

Question

目前我已经编写了一个将两个多项式相加的方法。Poly1和Poly2。该方法的逻辑如下，首先它添加来自Poly1和Poly2的所有匹配度项，然后它添加来自Poly1的所有不匹配项，最后添加来自Poly2的所有不匹配项。但正因为如此，这些条款的顺序是混乱的。

Polynomial answer = new Polynomial();
    for (Node firstPoly = poly; firstPoly != null; firstPoly = firstPoly.next){
        boolean polyAdded = false;
        for (Node secondPoly = p.poly; secondPoly != null; secondPoly = secondPoly.next){
            if (firstPoly.term.degree == secondPoly.term.degree){
            answer = addToRear(answer, (firstPoly.term.coeff + secondPoly.term.coeff), firstPoly.term.degree, null);
                    if (answer.poly.term.coeff == 0){
                        answer.poly = null;
                    }
                    polyAdded = true;           
            }

        }
        if (polyAdded == false){
        answer = addToRear(answer, firstPoly.term.coeff, firstPoly.term.degree, null);
        if (answer.poly.term.coeff == 0){
            answer.poly = null;
        }
        }
    }
    for (Node secondPoly = p.poly; secondPoly != null; secondPoly = secondPoly.next){
        boolean match = false;
        for (Node answerPoly = answer.poly; answerPoly != null; answerPoly = answerPoly.next){
            if (secondPoly.term.degree == answerPoly.term.degree){
                match = true;
                break;
            }
        }
        if (match == false){
        answer = addToRear(answer, secondPoly.term.coeff, secondPoly.term.degree, null);
        }
    }
    return answer;
    //alt + shift + r
}

如果此代码输出:

8.0x^4 + 4.0x^5 + 2.0x^3 + -1.0x + 12.0

链表表示为:

(系数、程度)//(12,0)->(1,1)->(2、3)->(4、5)-> (8,4)

我现在要对答案多项式按阶排序。链接列表应该像这样表示:

(系数、程度)//(12,0)->(1,1)->(2、3)->(8,4)->(4、5)

编辑:我自己找到了解决方案。下面是我创建的排序方法:

private Polynomial sortByDegree(Polynomial p){
    Node prev = p.poly;
    Node current = p.poly.next;
    while (current != null){
        if (current.term.degree < prev.term.degree){
            int temp = current.term.degree;
            current.term.degree = prev.term.degree;
            prev.term.degree = temp;
            float temp2 = current.term.coeff;
            current.term.coeff = prev.term.coeff;
            prev.term.coeff = temp2;
            prev = p.poly;
            current = p.poly.next;
        }
        prev = prev.next;
        current = current.next;
    }
    return p;
}

谢谢大家!

Answer 1

我建议两种方法:

。获取链表到数组列表(堆栈)，排序数组列表，重建链表

。使用以下算法:

void sortPoly(Polynomial answer) {
    float lowerMargin = 0;
    Node head = null, tail = null;
    while (answer.poly != null) {
        Node next = detouchMin(lowerMargin, answer);
        lowerMargin = next.term.degree;
        if (tail != null) {
            tail.next = next;
            tail = next;
        else {
            head = next;
            tail = next;
        }
    }
    answer.poly = head;
}

Node detouchMin(float lowerMargin, Polynomial answer) {
    float min = Float.inf;
    Node n = null;
    Node t = answer.poly;
    while (t != null) {
        if ((t.term.degree > lowerMargin) && (t.term.degree < min)) {
            n = t;
            min = n.term.degree;
        }
        t = t.next;
    }
    if (n != null) {
        Node t = answer.poly, prev = null;
        while (t != null) {
            if (t == n) {
                if (prev != null)
                    answer.poly = t.next;
                else
                    prev.next = t.next;
            }
            prev = t;
            t = t.next;
        }
    }
    return n;
}

注意:未测试代码