[数据结构与算法]排序单链表实现一元多项式的加减乘

排序单链表实现一元多项式的加减乘

• 排序单链表类(继承单链表)

//T或T的某个祖先类 “?” 实现Comparable<?>接口，提供compareTo()方法比较对象大小和相等
public class SortedSinglyList<T extends Comparable<? super T>> extends SinglyList<T> {
    protected boolean asc;  //排序次序，取值为true(升序)或false(降序)
    //构造空排序单链表，asc指定升/降序
    public SortedSinglyList(boolean asc){
        super();
        this.asc=asc;
    }
    //构造空排序单链表，默认升序
    public SortedSinglyList(){
        this(true);
    }
    //构造方法，按值插入values数组元素
    public SortedSinglyList(T[] values, boolean asc){
        this(asc);
        for (int i=0; i<values.length; i++){
            this.insert(values[i]);
        }

    }
    //构造方法，按值插入values数组元素，默认升序
    public SortedSinglyList(T[] values){
        this(values,true);
    }

    /*以下拷贝构造方法，由list构造，深拷贝*/
    //算法调用父类的深拷贝，O(n),asc属性同list
    public SortedSinglyList(SortedSinglyList<T> list){
        this(list.asc);
        Node<T> rear=this.head;
        for (int i=0; i<list.size; i++){
            rear.next=new Node<>(list.get(i),null);
            rear=rear.next;
            this.size++;
        }
    }
    //算法按值插入list所有元素，O(n^2)
    public SortedSinglyList(SortedSinglyList<T> list, boolean asc){
        this(asc);
        for (int i=0; i<list.size; i++){
            this.insert(list.get(i));
        }
    }
    //由list单链表构造，深拷贝，默认升序
    public SortedSinglyList(SinglyList<T> list){
        this(true);
        for (int i=0; i<list.size; i++){
            this.insert(list.get(i));
        }
    }
    //不支持，覆盖并抛出异常
    public void set(int i, T x){
        throw new UnsupportedOperationException("set(int i, T x)");
    }
    //不支持，覆盖并抛出异常
    public Node<T> insert(int i,T x){
        throw new UnsupportedOperationException("insert(int i, T x)");
    }
    //插入x，根据x对象大小顺序查找确定插入位置，插入在等值结点之后
    public Node<T> insert(T x){
        if (x==null){
            return null;
        }
        Node<T> front=this.head;
        Node<T> p=front.next;
        while (p!=null && (this.asc ? x.compareTo(p.data)>=0 : x.compareTo(p.data)<=0)){
            front=p;
            p=p.next;
        }
        front.next=new Node<>(x,p);//在front后，p前插入值为x的结点
        this.size++;
        return front.next;
    }
    //顺序查找并返回首个与key相等的元素
    public Node<T> search(T key){
        Node<T> p=this.head;
        for (int i=0; i<this.size; i++){
            if (p.next.data.equals(key)){
                return p.next;
            }
            else {
                p=p.next;
            }
        }
        return null;
    }
    //顺序查找，删除并返回首个与key相等的元素
    public T remove(T key){
        return this.remove(this.search(key).data);
    }
}

• 一元多项式链表类(继承排序单链表)

//一元多项式排序单链表
public class PolySinglyList extends SortedSinglyList<TermX> {
    /*构造空一元多项式排序单链表，默认升序*/
    public PolySinglyList() {
        super();
    }
    /*构造空一元多项式排序单链表，asc指定升降序*/
    public PolySinglyList(boolean asc){
        super(asc);
    }
    /*由项数组指定多项式各项值*/
    public PolySinglyList(TermX[] termXList, boolean asc){
        this(asc);
        for (int i=0; i<termXList.length; i++){
            if (termXList[i]!=null){
                this.insert(termXList[i]);
            }
        }
    }
    /*深拷贝，复制所有结点，没有复制对象*/
    public PolySinglyList(PolySinglyList list){
        this.asc=list.asc;
        Node<TermX> rear=this.head;
        for (int i=0; i<list.size; i++){
            rear.next=new Node<>(list.get(i),null);
            rear=rear.next;
            this.size++;
        }
    }

    /*输出一元多项式*/
    public String toString(){
        String str=this.getClass().getName() + "(";
        if (this.size>0)
            str += this.get(0).coef + "X^" + this.get(0).xexp;
        for (int i=1;i<size;i++){
            str += ", " + this.get(i).coef + "X^" + this.get(i).xexp;
        }
        return str + ")";
    }

    /*一元多项式加法*/
    public void add(PolySinglyList pList){
        Node<TermX> front=this.head;
        Node<TermX> p=front.next;
        Node<TermX> q=pList.head.next;
        while (p!=null){
            if (p.data.compareTo(q.data) == 0){
                p.data.add(q.data);
                if (p.data.removeAble()){
                    p=p.next;
                    front.next=p;
                    q=q.next;
                }
                p=p.next;
                front=front.next;
                q=q.next;
            }
            else if (p.data.compareTo(q.data) < 0){
                p=p.next;
                front=front.next;
            }
            else {
                Node<TermX> temp=new Node<>(q.data,null);
                temp.next=p;
                front.next=temp;
                front=front.next;
                q=q.next;
                this.size++;
            }
        }
        while (q!=null){
            Node<TermX> temp=new Node<>(q.data, null);
            front.next=temp;
            front=front.next;
            q=q.next;
            this.size++;
        }
    }
    /*一元多项式乘法*/
    public PolySinglyList multi(PolySinglyList pList){
        PolySinglyList multiList=new PolySinglyList();
        for (int i=0; i<this.size; i++){
            for (int j=0; j<pList.size; j++){
                TermX t=new TermX(this.get(i).coef*pList.get(j).coef,this.get(i).xexp+pList.get(j).xexp);
                multiList.insert(t);
            }
        }
        return multiList;
    }
    /*一元多项式减法*/
    public PolySinglyList sub(PolySinglyList pList){
        PolySinglyList temp=new PolySinglyList(this);
        TermX[] flagTermX={new TermX(-1,0)};
        PolySinglyList flagList=new PolySinglyList(flagTermX,true);
        temp=temp.multi(flagList);
        temp.add(pList);
        temp=temp.multi(flagList);
        return temp;
    }

    public static void main(String[] args) {
        TermX[] termX1={new TermX(2,6),new TermX(-9,3),new TermX(1,2),new TermX(-1,1),new TermX(2,0)};
        PolySinglyList list1=new PolySinglyList(termX1,true);
        System.out.println(list1.toString());
        TermX[] termX2={new TermX(3,7)};
        PolySinglyList list2=new PolySinglyList(termX2,true);
        System.out.println(list2.toString());
        list1=list1.sub(list2);
        System.out.println(list1.toString());
    }
}

• 一元多项式结点数据类

//一元多项式的项类，实现可比较接口和可相加接口
public class TermX implements Comparable<TermX>,AddInterface<TermX>{
    protected int coef;     //系数
    protected int xexp;     //指数

    public TermX(int coef, int xexp){
        this.coef=coef;
        this.xexp=xexp;
    }
    //拷贝构造方法
    public TermX(TermX termX){
        this.coef=termX.coef;
        this.xexp=termX.xexp;
    }

    public boolean equals(Object obj){
        // 如果为同一对象的不同引用,则相同
        if (this == obj) {
            return true;
        }
        // 如果传入的对象为空,则返回false
        if (obj == null) {
            return false;
        }

        // 如果两者属于不同的类型,不能相等
        if (getClass() != obj.getClass()) {
            return false;
        }
        //类型相同，比较内容是否相同
        TermX termX=(TermX)obj;
        if (this.coef == termX.coef && this.xexp==termX.xexp){
            return true;
        }
        else {
            return false;
        }
    }
    @Override
    public int compareTo(TermX o) {
        if (this.xexp < o.xexp){
            return -1;
        }
        else if (this.xexp == o.xexp){
            return 0;
        }
        else {
            return 1;
        }
    }
    @Override
    public void add(TermX termX) {
        if (this.xexp == termX.xexp){
            this.coef += termX.coef;
        }
    }
    @Override
    public boolean removeAble() {
        if (this.coef == 0){
            return true;
        }
        else {
            return false;
        }
    }
}

• 判断接口

//可相加接口，T表示数据元素的数据类型
public interface AddInterface<T> {
    //约定元素相加规则
    public void add(T t);
    //约定删除元素条件
    public boolean removeAble();
}