基于链表的一元多项式加法求解（Java语言描述）

定义结点类

public class PolyNode {
    
    /**
     * 定义结点系数域
     */
    private int coef;
    
    /**
     * 定义结点指数域
     */
    private int exp;
    
    /**
     * 定义结点后继引用域
     */
    private PolyNode next;
    
    /**
     * 无参数构造器
     * 构造空结点
     */
    public PolyNode() {
        this.next = null;
    }

    /**
     * 有参数构造器
     * 初始化系数、指数
     * @param coef
     * @param exp
     */
    public PolyNode(int coef, int exp) {
        super();
        this.coef = coef;
        this.exp = exp;
    }

    public int getCoef() {
        return coef;
    }

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

    public int getExp() {
        return exp;
    }

    public void setExp(int exp) {
        this.exp = exp;
    }

    public PolyNode getNext() {
        return next;
    }

    public void setNext(PolyNode next) {
        this.next = next;
    }

}

对应单链表的实现

public class PolynomialList {
    
    /**
     * 头引用
     */
    protected PolyNode first;
    
    /**
     * 尾插法实现构造器
     * @param initialList
     */
    public PolynomialList(String[] initialList) {
        //头引用初始化为头结点
        first = new PolyNode();
        //初始化尾引用，实现未插入
        PolyNode rear = first;
        for (int i = 0; i < initialList.length; i++) {
            //以逗号分离系数、指数
            String[] polyInfo = initialList[i].split(",");
            int coef = Integer.parseInt(polyInfo[0]);
            int exp = Integer.parseInt(polyInfo[1]);
            //生成多项式结点
            PolyNode node = new PolyNode(coef, exp);
            rear.setNext(node);
            rear = node;
        }
    }
    
    public void printpolynomial() {
        PolyNode node = first;
        StringBuilder str = new StringBuilder();
        while (node != null) {
            if (node.getCoef() != 0) {
                str.append(node.getCoef() + "x^" + node.getExp());
                //System.out.print();
                if (node.getNext() != null) {
                    str.append(" + ");
                } else {
                    str.append(".");
                }
            }
            node = node.getNext();
        }
        System.out.println(str);
    }

}

多项式操作类

public class Polynomial {
    
    public PolynomialList addPolynomial(String[] initialA, String[] initialB) {
        //初始化一元多项式A、B的单链表
        PolynomialList polyA = new PolynomialList(initialA);
        PolynomialList polyB = new PolynomialList(initialB);
        //初始化工作引用pre、p
        PolyNode pre = polyA.first, p = pre.getNext();
        //初始化工作引用q
        PolyNode q = polyB.first.getNext();
        PolyNode qTemp;
        while (p != null && q != null) {
            //第一种情况
            if (p.getExp() < q.getExp()) {
                pre = p;
                p = p.getNext();
            } else if (p.getExp() > q.getExp()) {   //第二种情况
                qTemp = q.getNext();
                pre.setNext(q);
                q.setNext(p);
                q = qTemp;
            } else {    //第三种情况
                //系数相加
                p.setCoef(p.getCoef() + q.getCoef());
                //系数为0
                if (p.getCoef() == 0) {
                    pre.setNext(p.getNext());
                    p = pre.getNext();
                } else {    //系数不为0
                    pre = p;
                    p = p.getNext();
                }
                q = q.getNext();
            }
        }
        if (q != null) {
            //将q连接到第一个链表之后
            pre.setNext(q);
        }
        return polyA;
    }

}

测试类

public class PolynomialTester {

    public static void main(String[] args) {
        String[] initialA = {"3,0", "3,1", "3,4"};
        String[] initialB = {"3,0", "3,2", "3,3", "4,7"};
        
        Polynomial polynomial = new Polynomial();
        PolynomialList list = polynomial.addPolynomial(initialA, initialB);
        list.printpolynomial();
    }

}

运行结果

6x^0 + 3x^1 + 3x^3 + 3x^4 + 4x^7.