#include <iostream>
using namespace std;
struct list
{
int coef; //系数
int exp; //指数
list *next;
};
list *Creat(); //创建带头结点的链表
void Display(list *h); //输出链表
list *Merge(list *h1); //合并同类项
list *Multiply(list *h1,list *h2); //实现两个链表相乘
int main()
{
list *h1,*h2;
h1=Creat();
Display(h1);
h2=Creat();
Display(h2);
cout<<"The Result is:"<<endl;
h1=Multiply(h1,h2);
Display(h1);
return 0;
}

list *Creat()//创建带头结点的链表
{
list *h,*r,*s;//h是头结点，存放项的个数，指向第一项
r=h=new list;
h->next=NULL;
while(1)
{
  s=new list;
  cin>>s->coef>>s->exp;
  if(s->coef==0 )
   break;
  if(h->next==NULL)
  {
   r=s;//r=h->next
   h->next=r;
  }
  else
  {
   r->next=s;
   r=s;
  }
  r->next=NULL;
}
return h;
}
void Display(list *h)//输出链表
{
list *p;
p=h->next;
cout<<"f(x)=";
while(p)
{
  if(p->next!=NULL)
  {
   switch (p->exp)
   {
   case 0:
    cout<<p->coef<<"+";
    break;
   case 1:
    cout<<"X"<<"+";
    break;
   default:
    cout<<p->coef<<"X^"<<p->exp<<"+";
   }
  }
  else
  {
   switch (p->exp)
   {
   case 0:
    cout<<p->coef;
    break;
   case 1:
    cout<<"X";
    break;
   default:
    cout<<p->coef<<"X^"<<p->exp;
   }
  }
  p=p->next;
}
cout<<endl;
}
list *Merge(list *h1)//合并同类项
{
list *p1,*q1,*q2;
    for(p1=h1->next;p1;p1=p1->next)
{
  for(q1=p1,q2=q1->next;q2;q1=q2,q2=q2->next)
  {
   if(p1->exp==q2->exp)
   {
    p1->coef+=q2->coef;
    q1->next=q2->next;
    delete q2;
    q2=q1;//q2=q1->next;
   }
  }
}
//sort
struct list *temp, *cur, *pre, *preindex, *curindex;
for(pre=h1->next, cur=h1->next->next; cur !=NULL; pre=cur, cur=cur->next)
{
  preindex=h1;
  curindex=h1->next;
  while (curindex != cur )
  {
   if (curindex->exp > cur->exp)
   {
    temp=cur;
    cur=cur->next;
    pre->next=cur;
    temp->next=curindex;
    preindex->next=temp;
    break;
   }
   preindex=curindex;
   curindex=curindex->next;
  }
}
return h1;
}
list *Multiply(list *h1,list *h2)//实现两个链表相乘
{
    // h1 * h2
    list *result = new list;
    result->next = NULL;
    list *temp = result;

    list *p1, *p2;

    p1 = h1->next;
    while (p1)
    {
        p2 = h2->next;
        while (p2)
        {
            list *q = new list;
            q->coef = p1->coef * p2->coef;
            q->exp = p1->exp + p2->exp;
         
            temp->next = q;
            q->next = NULL;
            temp = q;

            p2 = p2->next;
        }
        p1 = p1->next;
    }

    result = Merge(result);
    return result;