//有序多项式加法
#include <iostream>
using namespace std;
struct Node
{
 
int coef;
 
int exp;
 Node 
*next;
}
;
class MExpression
{
 
private :
 Node 
*first;
 
public :
 MExpression();
 
void InsertNode(int coef,int exp);
 
void DeleteNode(int exp);
 
void Add(MExpression me);
 
void PrintAll();
}
;
MExpression::MExpression()
{
 first
->next=NULL;
}

void MExpression::InsertNode(int coef,int exp)
{
 Node 
*s=new Node();
 Node 
*p=first;
 
while(p->next!=NULL)
 p
=p->next;
 s
->coef=coef;
 s
->exp=exp;
 s
->next=p->next;
 p
->next=s;
}

void MExpression::DeleteNode(int exp)
{
 Node 
*p=first->next;
 Node 
*q;
 q
=first;
 
while(p!=NULL)
 
{
 
if (p->exp==exp) break;
  q
=p;
 p
=p->next;
 }

 q
->next=p->next;
 delete p;
}

void MExpression::Add(MExpression me)
{
 
int i=0,j=0;
 Node 
*p=first->next;
 Node 
*q=me.first->next;
 Node 
*pp,*qq;
 pp
=first;
 qq
=me.first; 
 
while(p&&q)
 
{
  
if (p->exp>q->exp)
  
{
  InsertNode(q
->coef,q->exp);
  q
=q->next;
  }

  
else if(p->exp==q->exp)
  
{
  p
->coef+=q->coef;
  p
=p->next;
  q
=q->next;
  }

  
else
  
{
  p
=p->next;
  }

 }

 
while(q)
 
{
  InsertNode(q
->coef,q->exp);
  q
=q->next;
  }

}

void MExpression::PrintAll()
{
cout
<<"=== coef c exp e ==="<<endl;
Node 
*p=first->next;
while(p!=NULL)
{
cout
<<p->coef<<"  c "<<p->exp<<" e ";
p
=p->next;
}

}

int main()
{
MExpression 
*me1=new MExpression();
MExpression 
*me2=new MExpression();
me1
->InsertNode(1,1);
me1
->InsertNode(2,2);
me1
->InsertNode(3,3);
me1
->InsertNode(4,4);
me2
->InsertNode(1,2);
me2
->InsertNode(2,3);
me2
->InsertNode(3,4);
me2
->InsertNode(4,5);
me1
->Add(*me2);
me1
->PrintAll();
}