Java语言使用单项链表来计算多项式的求和的功能，链表的实现可以使用上个星期的作业中定义的

Java语言使用单项链表来计算多项式的求和的功能，链表的实现可以使用上个星期的作业中定义的

//定义节点类
class Node{
public int coef;//系数

public int exp;//指数

public Node next=null;//下个节点

public Node(){

coef=0;

exp=0;

}

public Node(int coef,int exp){

this.coef=coef;

this.exp=exp;

}
}
//多项式类
public class PolynList {
//多项式相加
public Node add(Node link1, Node link2) {
Node pre=link1;

Node qre=link2;

Node p=pre.next;

Node q=qre.next;

Node result=p;

while(p!=null && q!=null){

if(p.exp pre=p;
p=p.next;
}else if(p.exp>q.exp){

Node temp=q.next;

pre.next=q;

q.next=p;

q=temp;

}else{

p.coef=p.coef+q.coef;

if(p.coef==0){

pre.next=p.next;

p=pre.next;

}else{

pre=p;

p=p.next;

}

qre.next=q.next;

q=qre.next;

}

}

if(q!=null){

pre.next=q;

}

return result;

}

//添加数据方法
public Node insert(Node link,int coef,int exp) {//添加节点  
     Node node=new Node(coef,exp);  
     if(link==null){  
         link.next=node;  
     }else{  
         Node temp=link;  
         while(temp.next!=null){  
             temp=temp.next;  
         }  
         temp.next=node;  
     }  
     return link;
    } 
}

//主方法
public static void main(String[] args) {
PolynList ts = new PolynList();
Node link1=new Node();
Node link2=new Node();
//第一个多项式
ts.insert(link1,4,0);
ts.insert(link1,5,2);
ts.insert(link1,4,8);
ts.insert(link1,6,12);
//第二个多项式
ts.insert(link2,6,1);
ts.insert(link2,6,3);
ts.insert(link2,3,8);
ts.insert(link2,4,15);
ts.insert(link2,8,20);

     link1 = ts.add(link1, link2); 

     while(link1!=null){  
        if(link1.exp== 0)
            System.out.print(link1.coef);
        else
            System.out.print(link1.coef+"x^"+link1.exp);  
         link1=link1.next;  
         if(link1!=null)
            System.out.print("+");
     }  
 }

}

import java.util.Iterator;

public class LinkList implements Iterable {
//记录头结点
private Node head;
//记录链表的长度
private int N;

//节点类
private class Node{
    //存储数据
    T item;
    //下一个节点
    Node next;

    //内部类的构造函数
    public  Node(T item,Node next){
        this.item = item;
        this.next = next;
    }
}

//LinkList的构造函数
public LinkList(){
    //初始化头结点
    this.head = new Node(null,null);
    //初始化元素个数
    this.N = 0;
}

//清空链表
public void clear(){
    head.next = null;
    this.N = 0;
}

//获取链表的长度
public int length(){
    return N;
}

//判断链表是否为空
public boolean isEmpty(){
    return N==0;
}

//获取指定位置i处的元素
public T get(int i){
    //通过循环，从头节点开始往后找，依次找i次就可以找到对应的元素
    Node n = head.next;
    for(int index = 0; index < i; index++){
          n = n.next;
     }
     return n.item;

}
//向链表中添加元素t
public void insert(T t){
    //找到当前最后一个节点
    Node n = head;
    while (n.next != null){
        n = n.next;
    }
    //创建新节点，保存元素t
    Node newNode = new Node(t,null);
    //让当前最后一个节点指向新节点
    n.next = newNode;
    //元素个数+1
    N++;
}

//向指定位置i处，添加元素t
public void insert(int i,T t){
    //找到i位置前一个节点
    Node pre = head;
    for(int index = 0; index <= i-1; index++){//??????????
        pre = pre.next;
    }

    //找到i位置的节点
    Node curr = pre.next;
    //创建新节点，并且新节点需要指向原来i位置的节点
    Node newNode = new Node(t,curr);
    //原来i位置的前一个节点指向新节点
    pre.next = newNode;
    //元素个数+1；
    N++;
}

//删除指定位置i处的元素，并返回被删除的元素
public T remove(int i){
    //找到i位置的前一个节点
    Node pre = head;
    for(int index = 0; index <= i-1; index++){//??????????
        pre = pre.next;
    }
    //要找到i位置的节点
    Node curr = pre.next;
    //找到i位置的下一个节点
    Node nextNode = curr.next;
    //前一个节点指向下一个节点
    pre.next = nextNode;
    //元素个数-1
    return curr.item;
}

//查找元素t在链表中第一次出现的位置
public int indexOf(T t){
    //从头节点开始，依次找到每一个结点，取出item和t进行比较如果相同就找到了
    Node n = head;
    for(int i = 1; n.next!=null; i++){
        n = n.next;
        if(n.item.equals(t)){
            return i;
        }
    }
    return -1;
}

@Override
public Iterator<T> iterator() {
    return new LIterator();
}

private class LIterator implements Iterator{
    private Node n;
    public LIterator(){
        this.n = head;
    }

    @Override
    public boolean hasNext(){
        return n.next != null;
    }

    @Override
    public Object next() {
        n = n.next;
        return n.item;
    }
}

}