排序顺序表实现一元多项式加减乘运算

• 排序顺序表结点类

public class Term implements Comparable<Term> {
    private double coef;    //系数
    private int expn;   //指数

    public Term(double coef, int expn){
        this.coef=coef;
        this.expn=expn;
    }

    public double getCoef() {
        return coef;
    }

    public void setCoef(double coef) {
        this.coef = coef;
    }

    public int getExpn() {
        return expn;
    }

    public void setExpn(int expn) {
        this.expn = expn;
    }

    @Override
    public int compareTo(Term o) {
        if (this.expn <o.expn)
            return -1;
        else if (this.expn > o.expn)
            return 1;
        return 0;
    }
}

• 一元多项式类

public class PolySeqList extends SortedSeqList<Term> {
    public PolySeqList(double[] coef, int[] expn){
        int size=expn.length;
        for (int i=0; i<size; i++){
            if (coef[i]==0)
                continue;
            Term term=new Term(coef[i],expn[i]);
            this.insert(term);
        }
    }
    public PolySeqList(){
        super();
    }

    public int insert(Term term){
        int i=0;
        if (this.isEmpty() || term.compareTo(this.get(this.n-1))>0) {
            i = this.n;
        }
        else {
            while (i < this.n && term.compareTo(this.get(i)) >= 0) {
                if (term.compareTo(this.get(i)) == 0){
                    Term temp=this.get(i);
                    temp.setCoef(temp.getCoef()+term.getCoef());
                    if (temp.getCoef() == 0){
                        this.remove(i);
                        i--;
                    }
                    return i;
                }
                i++;
            }
        }
        super.insert(i,term);
        return i;
    }

    public String toString(){
        String str=this.getClass().getName() + "(";
        if (this.n>0)
            str += this.get(0).getCoef() + "X^" + this.get(0).getExpn();
        for (int i=1;i<n;i++){
            str += ", " + this.get(i).getCoef() + "X^" + this.get(i).getExpn();
        }
        return str + ")";
    }

    /*一元多项式相加*/
    public void add(PolySeqList p){
        int i,j;
        for (i=0,j=0; i<this.n && j<p.n; ){
            Term l=this.get(i);
            Term r=p.get(j);
            if (l.compareTo(r) == 0){
                l.setCoef(l.getCoef()+r.getCoef());
                if (l.getCoef() == 0)
                    this.remove(i);
                j++;
            }
            else if (l.compareTo(r) < 0){
                i++;
            }
            else {
                Term temp=new Term(r.getCoef(),r.getExpn());
                this.insert(i,temp);
                i++;
                j++;
            }
        }

        while (j<p.n){
            Term temp=p.get(j);
            this.insert(new Term(temp.getCoef(),temp.getExpn()));
            j++;
        }
    }
    /*一元多项式相乘*/
    public PolySeqList multi(PolySeqList p){
        PolySeqList addList=new PolySeqList();
        for (int i=0; i<this.n; i++){
            Term temp1=this.get(i);
            double[] coefList=new double[p.n];
            int[] expnList=new int[p.n];
            for (int j=0; j<p.n; j++){
                Term temp2=p.get(j);
                coefList[j]=temp1.getCoef()*temp2.getCoef();
                expnList[j]=temp1.getExpn()+temp2.getExpn();
            }
            PolySeqList list=new PolySeqList(coefList,expnList);
            addList.add(list);
        }
        return addList;
    }
    /*一元多项式相减*/
    public PolySeqList sub(PolySeqList p){
        PolySeqList temp=this;
        double[] flagCoef={-1};
        int[] flagExpn={0};
        PolySeqList flag=new PolySeqList(flagCoef,flagExpn);
        temp=temp.multi(flag);
        temp.add(p);
        temp=temp.multi(flag);
        return temp;
    }

    public static void main(String[] args) {
        double[] coef1={2};
        int[] expn1={6};

        double[] coef2={3,5,7};
        int[] expn2={0,2,4};
        PolySeqList list1=new PolySeqList(coef1,expn1);
        PolySeqList list2=new PolySeqList(coef2,expn2);
        System.out.println(list1.toString());
        System.out.println(list2.toString());
        list1=list1.sub(list2);
        System.out.println(list1.toString());
    }
}

• 一元多项式父类排序顺序表类

public class SortedSeqList<T extends Comparable<? super T>> extends SeqList<T> {
    public SortedSeqList(){
        super();
    }
    public SortedSeqList(int length){
        super(length);
    }
    public SortedSeqList(T[] values){
        super(values.length);
        for (int i=0; i<values.length; i++)
            this.insert(values[i]); //插入元素
    }
    /*由顺序表list构造排序顺序表this*/
    public SortedSeqList(SeqList<? extends T> list){
        super(list.size());
        for (int i=0; i<this.n; i++)
            this.insert(list.get(i));
    }

    //不支持父类的以下成员方法，将其覆盖并抛出异常
    /*排序顺序表的数据元素具有只读性，不支持*/
    public void set(int i, T x){
        throw new UnsupportedOperationException("set(int i, T x)");
    }
    /*不支持在指定位置插入*/
//    public int insert(int i, T x){
//        throw new UnsupportedOperationException("insert(int i, T x)");
//    }
    /*
    * 排序顺序表插入操作的特点是，不能指定插入位置
    * 由各数据元素的关键字大小确定插入位置，采用顺序查找算法寻早插入位置
    * */
    public int insert(T x){
        int i=0;
        if (this.isEmpty() || x.compareTo(this.get(this.n-1))>0) {
            i = this.n;
        }
        else {
            while (i < this.n && x.compareTo(this.get(i)) >= 0) {
                i++;
            }
        }
        super.insert(i, x);
        return i;
    }
    /*排序顺序表的查找操作*/
    public int search(T key){
        for (int i=0; i<this.n && key.compareTo(this.get(i))>=0;i++){
            if (key.compareTo(this.get(i))==0)
                return i;
        }
        return -1;
    }
    /*排序顺序表的删除操作*/
    public T remove(T key){
        return this.remove(this.search(key));
    }
}