#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef int datatype;
typedef struct node
{
        float coef;   /*多项式系数*/
    int expn;     /*多项式指数*/
    struct node *next;
}listnode;
typedef listnode *linklist;
/*---------创建带头结点的多项式链表--------*/
linklist creat()
{ linklist head,s,p,pre;
  float coef;
  int expn;
  head=(linklist)malloc(sizeof(listnode));   /*表头结点*/
  head->next=NULL;
  cout<<"输入系数:";
  cin>>coef;
  cout<<endl<<"输入指数:";
  cin>>expn;
  while (coef!=0)             
  {   cout<<"用系数=0作为结束标记!"<<endl;
          s=(linklist)malloc(sizeof(listnode));    /*生成新结点*/
      
          s->coef=coef;
      s->expn=expn;
      s->next=NULL;
      pre=head;                 /*插入到有序的多项式链表中去*/
      p=head->next;
      while (p && p->expn <expn)
          { pre=p;
        p=p->next;
          }
      s->next=p;
      pre->next=s;
       cout<<"读下一项:";
          cout<<endl<<"输入系数:";
           cin>>coef;        
      cout<<endl<<"输入指数:";
           cin>>expn;
  }
return head;
}
/*-----------输出多项式链表-------------*/
void print(linklist head)    
  { linklist p;
    p=head->next;
    while (p)
    {   
         cout<<p->coef<<"X^"<<p->expn<<"+";
       p=p->next;
           
     }
    cout<<endl;
}
/*-------------多项式相加----------------*/
linklist add(linklist pa,linklist pb)
{
        linklist p,q,pre,r,head;
        float x;
        
        p=head=pa->next;    //p,q 指向头接点的下一个接点,即多项式的第一个接点
        q=pb->next;
        pre=pa;       //pre指向p的前驱
        while((p!=NULL)&&(q!=NULL))  //处理多项式的相加的问题
                if(p->expn<q->expn)         
                {
                        pre=p;
                        p=p->next;
                }
                else if (p->expn==q->expn) 
                {
                        x=p->coef+q->coef;
                        if(x!=0)  //系数相加不为0的情况
                        {
                                p->coef=x;
                                pre=p;
                                p=p->next;
                        }
                        else   //系数相加为0的情况
                        {
                                pre->next=p->next;
                                free(p);
                                p=pre->next;
                        }
                        
                        r=q;
                        q=q->next;
                        free(r);
                }
                else               
                {
                        r=q->next;
                        q->next=p;
                        pre->next=q;
                        pre=q;
                        q=r;
                }
                if(q!=NULL)
                        pre->next=q;
                return head;
                free(pb);
}
/*----主程序------*/
void main()
{ 
        cout<<"*****************一元多项式相加******************"<<endl;
        cout<<"        !!!!2x^3表示 2乘以x的三次方~!!!!"<<endl;
        cout<<"**************************************************"<<endl;
        linklist a,b,c;
   cout<<"请输入第一个多项式:"<<endl;
   a=creat();                      /*创建多项式链表a*/
      cout<<endl;
    
   
   cout<<"请输入第二个多项式:"<<endl;
   b=creat();                     /*创建多项式链表b*/
   cout<<endl; 
   cout<<"您输入的第一个多项式为:"<<endl;
   print(a);
   
   cout<<"您输入的第二个多项式为:"<<endl;
   print(b);
   cout<<endl;
    
   
   cout<<"两多项式相加后为:"<<endl;
  
   c=add(a,b);                    /* 计算多项式a+b  */
   print(c);
   
  
   cout<<"程序运行完啦,不过有发现问题了吗?第一项丢了-_-!"<<endl;
}