java排序单链表实现多项式相加和相乘

对于多项式的相加和相乘，可以通过单链表来实现。

首先，我们需要定义一个节点类来表示多项式的每一项，包括系数和指数。节点类的定义如下：

class PolynomialNode {
    int coefficient;
    int exponent;
    PolynomialNode next;

    public PolynomialNode(int coefficient, int exponent) {
        this.coefficient = coefficient;
        this.exponent = exponent;
        this.next = null;
    }
}

接下来，我们可以定义一个多项式类，包含两个链表分别表示两个多项式。多项式类的定义如下：

class Polynomial {
    PolynomialNode head;

    public Polynomial() {
        this.head = null;
    }

    public void insertTerm(int coefficient, int exponent) {
        PolynomialNode newNode = new PolynomialNode(coefficient, exponent);

        if (head == null) {
            head = newNode;
        } else {
            PolynomialNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    public void add(Polynomial p) {
        PolynomialNode current1 = this.head;
        PolynomialNode current2 = p.head;
        Polynomial result = new Polynomial();

        while (current1 != null && current2 != null) {
            if (current1.exponent > current2.exponent) {
                result.insertTerm(current1.coefficient, current1.exponent);
                current1 = current1.next;
            } else if (current1.exponent < current2.exponent) {
                result.insertTerm(current2.coefficient, current2.exponent);
                current2 = current2.next;
            } else {
                int sum = current1.coefficient + current2.coefficient;
                if (sum != 0) {
                    result.insertTerm(sum, current1.exponent);
                }
                current1 = current1.next;
                current2 = current2.next;
            }
        }

        while (current1 != null) {
            result.insertTerm(current1.coefficient, current1.exponent);
            current1 = current1.next;
        }

        while (current2 != null) {
            result.insertTerm(current2.coefficient, current2.exponent);
            current2 = current2.next;
        }

        this.head = result.head;
    }

    public void multiply(Polynomial p) {
        PolynomialNode current1 = this.head;
        Polynomial result = new Polynomial();

        while (current1 != null) {
            PolynomialNode current2 = p.head;
            while (current2 != null) {
                int productCoefficient = current1.coefficient * current2.coefficient;
                int productExponent = current1.exponent + current2.exponent;
                result.insertTerm(productCoefficient, productExponent);
                current2 = current2.next;
            }
            current1 = current1.next;
        }

        this.head = result.head;
    }

    public void display() {
        PolynomialNode current = this.head;
        while (current != null) {
            System.out.print(current.coefficient + "x^" + current.exponent);
            if (current.next != null) {
                System.out.print(" + ");
            }
            current = current.next;
        }
        System.out.println();
    }
}

使用上述类可以实现多项式的相加和相乘操作。例如，假设有两个多项式 `p1 = 3x^2 + 5x^1 + 2x^0` 和 `p2 = 4x^3 + 2x^1 + 6x^0`，可以按照以下步骤进行操作：

Polynomial p1 = new Polynomial();
p1.insertTerm(3, 2);
p1.insertTerm(5, 1);
p1.insertTerm(2, 0);

Polynomial p2 = new Polynomial();
p2.insertTerm(4, 3);
p2.insertTerm(2, 1);
p2.insertTerm(6, 0);

p1.add(p2);
p1.display();  // 输出结果：4x^3 + 8x^2 + 7x^1 + 8x^0

p1.multiply(p2);
p1.display();  // 输出结果：16x^6 + 26x^5 + 32x^4 + 58x^3 + 22x^2 + 34x^1 + 12x^0

通过以上代码，我们可以实现多项式的相加和相乘操作。