按度数对多项式链表进行排序

Question

我正在尝试按降序对存储在链表中的多项式进行排序，但该算法似乎遗漏了链表的最后一个节点，因此多项式的最后一项始终未排序。有谁知道如何解决这一问题？

Node prev = mult.poly; //mult.poly is a pointer to the first node of the polynomial linked list 
Node curr = mult.poly.next;

    do{
        if (curr.term.degree < prev.term.degree){ //compare degrees
            int temp2 = curr.term.degree;             
            curr.term.degree = prev.term.degree;       
            prev.term.degree = temp2;                  

            float temp3 = curr.term.coeff;
            curr.term.coeff = prev.term.coeff;
            prev.term.coeff = temp3;

            prev = mult.poly;
            curr = mult.poly.next;
        } 

        prev = prev.next;
        curr = curr.next;
    } while(curr!=null);

    return mult;
}

Answer 1

您已尝试在链表上实现 bubble-sort。冒泡排序运行是循环中的循环，而您只实现了内部循环 - 这就是它不起作用的原因。

示例：

for (int i = 0; i < list.size(); i++) {
    Node prev = mult.poly; //mult.poly is a pointer to the first node of the polynomial linked list 
    Node curr = mult.poly.next;

    do {
        if (curr.term.degree < prev.term.degree){ //compare degrees
            int temp2 = curr.term.degree;
            curr.term.degree = prev.term.degree;
            prev.term.degree = temp2;

            float temp3 = curr.term.coeff;
            curr.term.coeff = prev.term.coeff;
            prev.term.coeff = temp3;

            prev = mult.poly;
            curr = mult.poly.next;
        }

        prev = prev.next;
        curr = curr.next;
    } while(curr!=null);
}
return mult;

提示：调试冒泡排序运行在一个以还原顺序排序的列表上，这将使您更容易发现冒泡中的错误-排序。

按度数对多项式链表进行排序

Sorting a polynomial linked list by degree

java

sorting

linked-list

polynomial-math

data-structures