多项式乘法

题目的链接为：http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1006
题目为：
多项式乘法
时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:171            测试通过:77

描述


线性表是一种最简单、最基本，也是最常用的数据结构，其用途十分广泛，例如，用带表头结点的单链表求解一元整系数多项式加法和乘法运算。

现给两个一元整系数多项式，请求解两者的乘积。


输入


两组数据，每一组代表一个一元整系数多项式，有多行组成，其中每一行给出多项式每一项的系数和指数，这些行按指数递减次序排序。每一组结束行输入为0 -1


输出


三组数据，前两组为一元整系数多项式，最后一组为两个多项式的乘积。

一元整系数多项式输出形式如下：

（1）多项式项4x输出为4X

（2）多项式项4x2输出为4X^2

（3）第一项系数为正数时，加号不要输出

（4）除常系数项外，项系数为1不显式输出，-1输出为-

例如，4x3- x2+x-1正确输出形式为4X^3-X^2+X-1，错误输出形式为 +4X^3-1X^2+1X-1


样例输入

3 14
-8 8
6 2
2 0
0 -1
2 10
4 8
-6 2
0 -1

样例输出

3X^14-8X^8+6X^2+2
2X^10+4X^8-6X^2
6X^24+12X^22-16X^18-50X^16+12X^12+76X^10+8X^8-36X^4-12X^2

刚做完多项式加法，趁热打铁做多项式乘法。其实乘法就是遍历两个多项式，将系数相乘，指数相加：
如果有指数相同的项，那么合并；
如果没有指数相同的项，那么按照指数递减的顺序找到合适的位置存放该项目。
最后再输出。

#include<iostream>
using namespace std;
typedef struct node{
      
      int xs;
      int zs;
      struct node *next;  
}Node;
int xs,zs;
bool tag=true;
void print(Node *root)
{
    Node *p=root->next;
    while(p!=NULL)
    {
         if(p->xs==0)
         {
             p=p->next;
             continue; 
         }
         if(p==root->next)
         {
              if(p->xs!=1)
              {
                 if(p->xs==-1)
                 {
                     cout<<"-"; 
                 }    
                 else
                 {
                     cout<<p->xs; 
                 }
              } 
         } 
         else
         {
              if(p->xs>0)
              {
                   cout<<"+";
                   if(p->xs!=1)
                   {
                       cout<<p->xs; 
                   }
              } 
              else
              {
                    if(p->xs!=-1)
                    {
                       cout<<p->xs;
                    } 
                    else
                    {
                       cout<<"-"; 
                    }
              }
         }
         if(p->zs!=0)
         {
               cout<<"X";
         }
         else
         {
               if(p->xs==1||p->xs==-1)
               {
                  cout<<"1"; 
               }
               
               p=p->next;
               continue; 
         }
         if(p->zs!=1)
         {
               cout<<"^"<<p->zs; 
         }
         
         p=p->next;
    }
    cout<<endl;
}
int main(){

    Node *root[2],*root1,*t,*u,*k,*e1,*e2;
    for(int i=0;i<2;i++){
        root[i]=NULL; 
    } 
    root1=new Node();
    for(int i=0;i<2;i++){
        while(cin>>xs>>zs&&(xs!=0||zs!=-1)){
         
            if(xs==0)
            {
               continue;
            }
            if(root[i]==NULL)
            {
                  Node *temp=new Node();
                  temp->xs=xs;
                  temp->zs=zs;
                  temp->next=NULL;
                  
                  root[i]=new Node();
                  root[i]->next=temp;
            }
            else
            {
                  Node *p,*q;
                  p=root[i]->next;
                  q=root[i];
                  while(p!=NULL&&p->zs!=zs)
                  {
                       q=p;
                       p=p->next; 
                  }
                  if(p==NULL)
                  {
                       Node *temp=new Node();
                       temp->xs=xs;
                       temp->zs=zs;
                       temp->next=NULL;
                  
                       q->next=temp;
                  }
                  else
                  {
                       p->xs+=xs;
                       if(p->xs==0)
                       {
                           q->next=p->next; 
                       }
                  }
            }
        }
        print(root[i]);  
    }
    t=root[0]->next;
    u=root[1]->next;
    k=root1;
   
    while(t!=NULL)
    {
       u=root[1]->next;
       while(u!=NULL)
       {
           int tempXS=t->xs*u->xs;
           int tempZS=t->zs+u->zs;
           if(tempXS==0)
           {
               u=u->next;
               continue;
           }
           else
           {
               e2=root1->next;
               e1=root1;
               while(e2!=NULL&&e2->zs!=tempZS)
               {
                     e1=e2;
                     e2=e2->next;
               }
               if(e2==NULL)
               {
                     Node *tempNode=new Node();
                     tempNode->xs=tempXS;
                     tempNode->zs=tempZS;
                     tempNode->next=NULL;
                     
                     //按照指数的大小放到合适的位置
                     e2=root1->next;
                     e1=root1;
                     while(e2!=NULL&&e2->zs>tempNode->zs)
                     {
                          e1=e2;
                          e2=e2->next; 
                     }
                     e1->next=tempNode;
                     tempNode->next=e2;
               }
               else
               {
                     e2->xs+=tempXS;
               }
           }
           u=u->next;
       }  
       t=t->next; 
    }
    print(root1);
    
    //释放new的空间 
    for(int i=0;i<2;i++)
    {
        t=root[i];
        u=t;
        while(t!=NULL)
        {
              u=t->next;
              delete t;
              t=u;
        } 
    }
    t=root1;
    u=t;
    while(t!=NULL)
    {
              u=t->next;
              delete t;
              t=u;
    } 
    system("pause");
    return 0;
}