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

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

//T或T的某个祖先类 “?” 实现Comparable接口，提供compareTo()方法比较对象大小和相等
public class SortedSinglyList> extends SinglyList {
    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 list){
        this(list.asc);
        Node rear=this.head;
        for (int i=0; i(list.get(i),null);
            rear=rear.next;
            this.size++;
        }
    }
    //算法按值插入list所有元素，O(n^2)
    public SortedSinglyList(SortedSinglyList list, boolean asc){
        this(asc);
        for (int i=0; i list){
        this(true);
        for (int i=0; i insert(int i,T x){
        throw new UnsupportedOperationException("insert(int i, T x)");
    }
    //插入x，根据x对象大小顺序查找确定插入位置，插入在等值结点之后
    public Node insert(T x){
        if (x==null){
            return null;
        }
        Node front=this.head;
        Node 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 search(T key){
        Node p=this.head;
        for (int i=0; i 
一元多项式链表类(继承排序单链表)
 
//一元多项式排序单链表
public class PolySinglyList extends SortedSinglyList {
    
    public PolySinglyList() {
        super();
    }
    
    public PolySinglyList(boolean asc){
        super(asc);
    }
    
    public PolySinglyList(TermX[] termXList, boolean asc){
        this(asc);
        for (int i=0; i rear=this.head;
        for (int i=0; i(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 front=this.head;
        Node p=front.next;
        Node 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 temp=new Node<>(q.data,null);
                temp.next=p;
                front.next=temp;
                front=front.next;
                q=q.next;
                this.size++;
            }
        }
        while (q!=null){
            Node 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 
一元多项式结点数据类
 
//一元多项式的项类，实现可比较接口和可相加接口
public class TermX implements Comparable,AddInterface{
    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 {
    //约定元素相加规则
    public void add(T t);
    //约定删除元素条件
    public boolean removeAble();
}