#include"stdio.h"
#include"alloc.h"
 typedef struct node
  { int c,e;/*定義系數，指數*/
    struct node *next;
  } polytype;   /*定義結構體*/
 polytype *create()  /*建多項式表*/
  { polytype *p, *head=malloc(sizeof(polytype));/*定義兩個指針*/
int c,e,n;
p=head;/*把頭節點附給P*/
    printf("please input the N:");
    scanf("%d",&n);
    printf("Warning the e's order must from min->max \n");
    while(n) 
     {n--; /*n向下逐個運算*/
      printf("please input c,e:");
      scanf("%d%d",&c,&e);
      p->next=malloc(sizeof(polytype)); /*申請一個空間付給p的下一個空間*/
      p=p->next; /*把p的下一個項付給p*/
      p->c=c;
      p->e=e;
     }
     p->next=NULL;
     return head; /*如果p的下一個項為空，則返回頭指針*/
  }
 void printpoly(polytype *head) /*這個函數用來輸出多項式*/
  { polytype *p=head->next;  /*把頭節點的下一個付給p*/
    while(p) 
     { printf("(%d,%d )",p->c,p->e);
       p=p->next;
     }
    printf("\n");
  }
 void freepoly(polytype *head)   /*此函數用來釋放所占用的空間*/
  { polytype *p=head;
while(p)  
{head=head->next;  /*把頭節點的下一個付給頭節點*/
     free(p);
     p=head;
    }
  }
 polytype *polyadd(polytype *ha,polytype *hb) /*多項式相加*/
  {polytype *hc=malloc(sizeof(polytype)); /*為hc申請一個空間*/
   polytype *pc=hc,*pa=ha->next,*pb=hb->next; /*定義多項式的三個數組*/
   int e,c; /*定義系數，指數*/
   while(pa||pb)
   {if(pa&&(pb==NULL||pa->e<pb->e)) /*如果pb為空或是pa的系數小于pb的系數*/
     {c=pa->c;
      e=pa->e;
      pa=pa->next;
     }
    else if(pb&&(pa==NULL||pb->e<pa->e))
     {c=pb->c;
      e=pb->e;
      pb=pb->next;
     }
    else /*兩鏈的當前結點指數相等*/
     {c=pa->c+pb->c; /*把兩個系數相加付給c*/
      e=pa->e; /*把pa的指數付給e*/
      pa=pa->next; /*把pa的下一項付給pa*/
      pb=pb->next;/*把pb的下一項付給pb*/
     }
    if(c) 
     {pc->next=malloc(sizeof(polytype)); /*申請一個多項式的空間付給pc*/
     pc=pc->next;  /*pc下一項付給pc*/
      pc->c=c;  /*c付給pc的系數*/
      pc->e=e;
     }
   }
  pc->next=NULL;
  return hc;
  }
  polytype *polysub(polytype *ha,polytype *hb) /*多項式相減*/
  {polytype *hc=malloc(sizeof(polytype)); /*為hc申請一個空間*/
   polytype *pc=hc,*pa=ha->next,*pb=hb->next; /*定義多項式的三個數組*/
   int e,c; /*定義系數，指數*/
   while(pa||pb)
   {if(pa&&(pb==NULL||pa->e<pb->e)) /*如果pb為空或是pa的系數小于pb的系數*/
     {c=pa->c;
      e=pa->e;
      pa=pa->next;
     }
    else if(pb&&(pa==NULL||pb->e<pa->e))
     {c=-(pb->c);
      e=pb->e;
      pb=pb->next;
     }
    else /*兩鏈的當前結點指數相等*/
     {c=pa->c-pb->c; /*把兩個系數相加付給c*/
      e=pa->e; /*把pa的指數付給e*/
      pa=pa->next; /*把pa的下一項付給pa*/
      pb=pb->next;/*把pb的下一項付給pb*/
     }
    if(c) 
     {pc->next=malloc(sizeof(polytype)); /*申請一個多項式的空間付給pc*/
     pc=pc->next;  /*pc下一項付給pc*/
      pc->c=c;  /*c付給pc的系數*/
      pc->e=e;
     }
   }
  pc->next=NULL;
  return hc;
  }

 polytype *onexmul(polytype *pa,polytype *pb)  /*一個數與多項式相乘*/

  {polytype *hc=malloc(sizeof(polytype)),*pc=hc;
    pa=pa->next;
    pb=pb->next;
  while(pb)
   { pc->next=malloc(sizeof(polytype));
     pc=pc->next;
     pc->e=pa->e+pb->e;
     pc->c=pa->c*pb->c;
     pb=pb->next;
   }
   pc->next=NULL;
   return hc;
 }
 polytype *mulxmul(polytype *ha,polytype *hb) /*多項式與多項式相乘*/
 {polytype *temp,*hc=malloc(sizeof(polytype)),*pa=ha,*pb=hb;
  hc->next=NULL;
  while(pa)
   { temp=onexmul(pa,pb);
     hc=polyadd(hc,temp);
     freepoly(temp);
     pa=pa->next;  }
   return hc;
 }
void main ()
   {polytype *ha,*hb,*add,*sub,*mul;  /*定義ha,hb,add mul指針*/
    ha=create();  /*建立多項式表*/
    printpoly(ha); /*輸出ha多項式項*/
    hb=create();  /*建立多項式表*/
    printpoly(hb);
    add=polyadd(ha,hb);  /*多項式相加*/
    puts(" The add:");
    printpoly(add);
    sub=polysub(ha,hb);  /*多項式相減*/
    puts(" The sub:");
    printpoly(sub);
    puts("The multiple:");
    mul=mulxmul(ha,hb); /*多項式相乘*/
    printpoly(mul);
    getch();
    freepoly(ha);  
    freepoly(hb);
    freepoly(add);
    freepoly(mul); }