多项式相加.cpp

数据结构

 #include <iostream>
 using namespace std;
 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<<"**********用系数=0作为结束标记!**********"<<endl;
  cout<<"输入系数c和指数e:  ";
  cin>>coef>>expn;
  cout<<endl;
  while (coef!=0)             
  {   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<<"输入系数c 指数e:  ";
       cin>>coef>>expn;        
      cout<<endl;         
  }

  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;    //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;     
        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);
   
}