#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include"iostream.h"

//================数据结构============================ 
typedef struct{ 
    int expn;//指数 
    float coef;//系数 
}PolynType,term; 
typedef struct LNode{ 
    PolynType data;//元素类型 
    struct LNode *next;//后继域 
}*Link,*Position; 
typedef struct{ 
    Link head,tail; 
    int len; 
}LinkList; 
typedef LinkList Polynomial; 

//================运算符重载=========================
ostream& operator<<(ostream &,PolynType &); 

//================一元多项式相关函数声明=============== 
void Add_Polyn(Polynomial &,Polynomial &); 
void GetPolyn(int &); 
void CreatePolyn(Polynomial &,int &); 
void Multi_Polyn(); 
void Display_Add(); 
void show_Add_result(Polynomial ); 

//================链表结构声明=======================
bool MakeNode(Link &,PolynType); 
void InsFirst(Link &,Link &); 
void InitList(Polynomial &,int ); 
Link GetHead(Polynomial); 
void SetCurElem(Link &,PolynType); 
int  cmp(term a,term b); 
void DelFirst(Link &a,Link &b); 
bool ListEmpty(LinkList a); 

//================主函数============================
int main(){ 
    while(1){ 
      cout<<"================================================"<<endl; 
      cout<<"                      BEGIN                     "<<endl; 
      cout<<"================================================"<<endl; 
      cout.width(30);cout.setf(ios::left); 
      cout<<"1、一元多项式相加"; 
      cout.width(30); 
      cout<<"2、一元多项式相乘"; 
      cout<<endl; 
      cout<<"================================================"<<endl; 
      cout<<endl; 
      cout<<"请选择你要进行的运算："; 
      switch(cin.get()){ 
         case'1':Display_Add();break;//一元多项式相加 
         case'2':Multi_Polyn();break;//一元多项式相乘 
         default:cout<<"ERROR!"<<endl; 
      }//switch 
      cout<<"================================================"<<endl; 
      cout<<"                      END                       "<<endl; 
      cout<<"================================================"<<endl; 
      cout<<endl<<endl<<endl; 
      cin.get(); 
    }//while(1) 
    return 0; 
} 

//======================================================= 
//                                                   相加 
//======================================================= 
void Display_Add(){ 
   cout<<endl; 
   cout<<"------- 你要进行的是一元多项式相加的操作 -------"; 
   cout<<endl; 
   int na; GetPolyn(na);//输出信息 
   Polynomial pa; CreatePolyn(pa,na);//创建第一个一元多项式 
   cout<<endl; 
   int nb; GetPolyn(nb);//输出信息 
   Polynomial pb; CreatePolyn(pb,nb);//创建第二个一元多项式 
   cout<<endl; 
   Add_Polyn(pa,pb);//调用加法函数 
   show_Add_result(pa); 
}//Display_Add() 

//=======================加法函数======================== 
void Add_Polyn(Polynomial &pa,Polynomial &pb){ 
   Link qa,qb,ha,hb; 
   //ha、hb分别指向pa，pb的头节点，qa，qb则指向第一个节点 
   ha=pa.head;  hb=pb.head; qa=pa.head->next;  qb=pb.head->next; 
   PolynType a; PolynType b;//a，b分别为当前qa，qb的data值 
   float sum;//sum记录系数和，以便判断是否为零 
   while(qa&&qb){ 
     a=qa->data;  b=qb->data; 
     switch(cmp(a,b)){ 
        case -1://a的指数小于b的指数 
           ha=qa;qa=qa->next;break; 
        case 0://指数相等 
          sum=a.coef+b.coef; 
          if(sum!=0.0){//系数不为零 
          qa->data.coef=sum; 
          ha=qa; 
          }//if 
         else{//系数为零 
         DelFirst(ha,qa);free(qa);//删除并释放节点 
    } 
    DelFirst(hb,qb);free(qb); 
    qb=hb->next;qa=ha->next; 
    break; 
   case 1://a的指数大于b的指数 
    DelFirst(hb,qb); 
    InsFirst(ha,qb); 
    qb=hb->next;ha=ha->next; 
    break; 
  }//switch 
}//while 
if(qb) ha->next=qb; 
free(hb);//释放节点 
}//Add_Polyn 
//=====================加法结果============================ 
void show_Add_result(Polynomial pa){ 
Link k=pa.head->next; 
cout<<"相加的结果为："<<endl; 
while(k->next){ 
  cout<<k->data<<'+'; 
  k=k->next; 
}//while 
cout<<k->data<<endl; 
}//show 

//=====================乘法函数============================ 
void Multi_Polyn(){ 
cout<<endl; 
cout<<"------- 你要进行的是一元多项式相乘的操作 -------"; 
cout<<endl; 
    int na_mul; GetPolyn(na_mul);//输出信息 
Polynomial pa_mul; CreatePolyn(pa_mul,na_mul);//创建第一个一元多项式 
cout<<endl; 
int nb_mul; GetPolyn(nb_mul);//输出信息 
Polynomial pb_mul; CreatePolyn(pb_mul,nb_mul);//创建第二个一元多项式 
Polynomial paMULpb;int paMULpb_len=0;//记录pa乘pb的积 
InitList(paMULpb,paMULpb_len); 
Link qa_mul,qb_mul,ha_mul,hb_mul,qc_mul; 
ha_mul=pa_mul.head;hb_mul=pb_mul.head;//ha首先指向pa的头节点 
qa_mul=pa_mul.head->next;//qa指向pa的第一个元素 
while(qa_mul){ 
  free(ha_mul);//释放前面的节点 
  Link pc_link;PolynType data_pc; 
  qb_mul=pb_mul.head->next;//qb指向pb的第一个元素 
  Polynomial pc_mul;int pc_mul_len=0;//pc用来存放pa中每一项乘pb得出的多项式 
        InitList(pc_mul,pc_mul_len); 
        qc_mul=GetHead(pc_mul);//qc重新指向头节点 
  while(qb_mul){ 
          data_pc.coef=qa_mul->data.coef*qb_mul->data.coef; 
   data_pc.expn=qa_mul->data.expn+qb_mul->data.expn; 
   if(MakeNode(pc_link,data_pc)){//生成pc的节点，data为系数积指数和 
       InsFirst(qc_mul,pc_link);//将当前qa乘qb的每一项记录进qc中 
      } 
   qc_mul=qc_mul->next;//qc始终指向尾节点 
   qb_mul=qb_mul->next; 
  }//while(qb) 
  Add_Polyn(paMULpb,pc_mul); 
  ha_mul=qa_mul; 
  qa_mul=qa_mul->next; 
}//while(qa) 
Link multik=paMULpb.head->next;//输出相乘后的一元多项式 
cout<<endl<<"相乘的结果为："<<endl; 
while(multik->next){ 
        /*while(multik->data.coef==0)//系数为零则不输出 
            multik=mutilk->next;*/ 
  cout<<multik->data<<"+"; 
     multik=multik->next; 
    }//while 
cout<<multik->data<<endl; 
while(qb_mul){//释放pb 
  free(hb_mul); 
  hb_mul=qb_mul; 
  qb_mul=qb_mul->next; 
} 
free(qb_mul); 
cout<<endl; 
} 

//输入非零个数 
void GetPolyn(int &n){ 
cout<<endl; 
cout<<"请输入一元多项式的非零项的个数："<<endl; 
cin>>n; 
cout<<"请输入这个一元多项式："<<endl; 
} 
//================创建一元方程对应的链表================ <br />void CreatePolyn(Polynomial &p,int &n){ 
InitList(p,n);//链表初始化 
Link q=GetHead(p),s; 
PolynType d; 
for(int i=1;i<=n;i++){//输入一元多项式的非零项 
  do{ 
   cout<<"系数"<<i<<": ";cin>>d.coef; 
   cout<<"指数"<<i<<": ";cin>>d.expn; 
   if(cmp(d,q->data)<=0) cout<<"你输入的数据有错误，请重新输入一次！"<<endl; 
  }while(cmp(d,q->data)<=0); 
  if(MakeNode(s,d))//生成节点 
      InsFirst(q,s);//插入节点s在q的后面 
  q=q->next;//q指向新生成的节点 
}//for 
Link l=p.head->next; 
    Link temp=p.head; 
cout<<"你输入的一元多项式为："<<endl; 
while(l->next){ 
        if(l->data.coef==0){//系数为零则删除 
          temp->next=l->next; 
          free(l); 
          l=temp; 
        } 
  cout<<l->data<<'+'; 
  temp=l; 
  l=l->next; 
}//while 
cout<<l->data<<endl; 
}//CreatePolyn 
//================链表函数和多项式函数================ <br />int cmp(term a,term b){//比较函数 
if(a.expn<b.expn) return -1; 
if(a.expn==b.expn) return 0; 
else return 1; 
} 
bool MakeNode(Link &s,PolynType e){//节点生成函数 
s=(Link)malloc(sizeof(LNode)); 
if(!s) exit(-1);//分配空间失败 
s->data=e; 
return 1; 
}//生成节点 
void InsFirst(Link &q,Link &s){ 
s->next=q->next; 
q->next=s; 
} 
void InitList(Polynomial &p,int n){ 
p.head=(Link)malloc(sizeof(LNode)); 
if(!p.head) exit(-1); 
p.head->next=NULL; 
p.head->data.coef=0.0; 
p.head->data.expn=0; 
} 
Link GetHead(Polynomial p){ 
return p.head; 
} 
void SetCurElem(Link &h,PolynType e){ 
h->data=e; 
} 
ostream &operator<<(ostream &out,PolynType &e){ 
//重载输出<<符号，能够直接输出PolynType类型的函数 
out<<e.coef<<'^'<<e.expn; 
return out; 
} 
void DelFirst(Link &a,Link &b){ 
//删除节点，应该加上free操作，那么就可以不必写上FreeNode(); 
a->next=b->next; 
} 
bool ListEmpty(LinkList a){//判断链表是否为空 
if(a.head->next!=NULL) 
  return true; 
else 
  return false; 
}