package shujuku;
public class List<E> {
int coefficient;//系数
int exponent;//指数
List next;
public List(int c,int e,List n){
coefficient=c;
exponent=e;
next=n;
}
public List(){
coefficient=0;
exponent=0;
next=null;
}
}
//上面是第一个程序
package shujuku;
import *;
public class Polynomial<E> {
List terms=new List();
/*插入一个节点，插入时通过比较使节点按降序排列*/
public void insertTerm(int coef,int exp){
List itr=terms;
while(true){
if(itr.next==null){
itr.next=new List(coef,exp,itr.next);
break;//空链表时直接插入
}
else{
if(exp<itr.next.exponent)
itr=itr.next;//迭代
else {
itr.next=new List(coef,exp,itr.next);
break;
}}
}
}
/********多项式相加******/
public void add(Polynomial rhs){
List pa=terms.next;
List pb=rhs.terms.next;//临时指针
List pc=terms;//指向结果链表的尾部
while(pa!=null&&pb!=null)
{
if(pa.exponent==pb.exponent)
{//指数相等，系数相加
pa.coefficient=pa.coefficient+pb.coefficient;
pb=pb.next;
if(pa.coefficient==0)
{//系数为0，删除节点
pc.next=pa.next;
pa=pa.next;//pa前进
}
else{//不为0，pa,pc都前进
pc.next=pa;
pc=pa;
pa=pa.next;
}
}
//不等时，pc指向指数大的一个
else if(pa.exponent<pb.exponent)
{
pc.next=pb;
pc=pb;
pb=pb.next;
}
else{
pc.next=pa;
pc=pa;
pa=pa.next;
}
if(pa==null)//有链表遍历完后，把另一个加上去
pc.next=pb;
else pc.next=pa;
}
}
/***********************打印链表****************************************/
public void print(){
List itr=terms.next;
System.out.print(itr.coefficient+"X^"+itr.exponent+" ");
itr=itr.next;
for(;itr!=null;itr=itr.next){
if(itr.coefficient>0)
System.out.print("+"+itr.coefficient+"X^"+itr.exponent+" ");
else
System.out.print(itr.coefficient+"X^"+itr.exponent+" ");
}
System.out.println();
}
public static void main(String args[]){
int n ;
Polynomial p1=new Polynomial();
Polynomial p2=new Polynomial();
List l1=new List();
List l2=new List();
/*输入多项式1系数指数*/
try
{
System.out.println("请输入第一个多项式1的项数n: ");
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(br.readLine());
int m=n;
for(int i=0;i<m;i++)
{
System.out.print("请输入第"+(i+1)+"系数以及X的次数: ");
l1.coefficient=Integer.parseInt(br.readLine());
l1.exponent=Integer.parseInt(br.readLine());
l1.next=null;
p1.insertTerm(l1.coefficient,l1.exponent);
}
}catch(IOException e){}
/*输入多项式2*/
try
{
System.out.println("请输入第二个多项式的项数n: ");
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(br.readLine());
int m=n;
for(int i=0;i<m;i++)
{
System.out.print("请输入"+(i+1)+"系数以及X的次数: ");
l2.coefficient=Integer.parseInt(br.readLine());
l2.exponent=Integer.parseInt(br.readLine());
l2.next=null;
p2.insertTerm(l2.coefficient,l2.exponent);
}
}catch(IOException e){}
System.out.print("P1=");
p1.print();
System.out.print("P2=");
p2.print();
p1.add(p2);
System.out.print("P1+P2=");
p1.print();
}
}
//以上这是第二个程序
