7-1 一元多项式的加法java线性表

在Java中，如果我们要实现一元多项式（比如多项式表达式如2x + 3）的加法，可以使用数组或链表数据结构来表示系数和变量。我们可以创建两个`Polynomial`类的对象，每个对象内部存储一个整数数组，数组的第一个元素代表常数项（x^0），后面的元素按降幂顺序存储其他项的系数。

下面是一个简单的例子，假设我们使用一个`Term[]`数组来存储每个多项式：

class Term {
    int coefficient; // 系数
    int exponent;   // 指数

    public Term(int coef, int exp) {
        this.coefficient = coef;
        this.exponent = exp;
    }
}

class Polynomial {
    private Term[] terms;

    public Polynomial(Term... terms) {
        this.terms = terms.clone(); // 复制防止修改原数组
    }

    public void add(Polynomial other) {
        if (other == null) return;

        for (Term t : other.terms) {
            // 找到对应的指数位置，如果没有则添加新项
            int index = binarySearch(terms, t.exponent);
            if (index < 0) {
                terms = insertAt(terms, -index - 1, new Term(t.coefficient, t.exponent));
            } else {
                // 如果指数存在，则直接累加系数
                terms[index].coefficient += t.coefficient;
            }
        }
    }

    // ...其他辅助方法，如binarySearch和insertAt

    // 二分查找插入位置
    private int binarySearch(Term[] terms, int targetExponent) {
        int left = 0, right = terms.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (terms[mid].exponent > targetExponent) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    // 插入一个term到已排序数组
    private Term[] insertAt(Term[] terms, int index, Term term) {
        Term[] newTerms = new Term[terms.length + 1];
        System.arraycopy(terms, 0, newTerms, 0, index);
        newTerms[index] = term;
        System.arraycopy(terms, index, newTerms, index + 1, terms.length - index);
        return newTerms;
    }
}

// 示例用法
Polynomial p1 = new Polynomial(new Term(2, 1), new Term(3, 0)); // 2x + 3
Polynomial p2 = new Polynomial(new Term(4, 1), new Term(5, 0)); // 4x + 5

p1.add(p2); // 现在 p1 是 6x + 8