/* bo2-7.c 多項(xiàng)式(存儲結(jié)構(gòu)由c2-6.h定義)的基本操作及算法2.22、2.23等 */
 #include"c2-5.h"
 #include"bo2-6.c"
 typedef LinkList polynomial;
 #define DestroyPolyn DestroyList /* 與bo2-6.cpp中的函數(shù)同義不同名 */
 #define PolynLength ListLength /* 與bo2-6.cpp中的函數(shù)同義不同名 */

 Status OrderInsertMerge(LinkList *L,ElemType e,int(* compare)(term,term))
 { /* 按有序判定函數(shù)compare()的約定，將值為e的結(jié)點(diǎn)插入或合并到升序鏈表L的適當(dāng)位置 */
   Position q,s;
   if(LocateElemP(*L,e,&q,compare)) /* L中存在該指數(shù)項(xiàng) */
   {
     q->data.coef+=e.coef; /* 改變當(dāng)前結(jié)點(diǎn)系數(shù)的值 */
     if(!q->data.coef) /* 系數(shù)為0 */
     { /* 刪除多項(xiàng)式L中當(dāng)前結(jié)點(diǎn) */
       s=PriorPos(*L,q); /* s為當(dāng)前結(jié)點(diǎn)的前驅(qū) */
       if(!s) /* q無前驅(qū) */
         s=(*L).head;
       DelFirst(L,s,&q);
       FreeNode(&q);
     }
     return OK;
   }
   else /* 生成該指數(shù)項(xiàng)并插入鏈表 */
     if(MakeNode(&s,e)) /* 生成結(jié)點(diǎn)成功 */
     {
       InsFirst(L,q,s);
       return OK;
     }
     else /* 生成結(jié)點(diǎn)失敗 */
       return ERROR;
 }

 int cmp(term a,term b) /* CreatPolyn()的實(shí)參 */
 { /* 依a的指數(shù)值<、=或>b的指數(shù)值，分別返回-1、0或+1 */
   if(a.expn==b.expn)
     return 0;
   else
     return (a.expn-b.expn)/abs(a.expn-b.expn);
 }

 void CreatPolyn(polynomial *P,int m) /* 算法2.22 */
 { /* 輸入m項(xiàng)的系數(shù)和指數(shù)，建立表示一元多項(xiàng)式的有序鏈表P */
   Position q,s;
   term e;
   int i;
   InitList(P);
   printf("請依次輸入%d個系數(shù)，指數(shù)：\n",m);
   for(i=1;i<=m;++i)
   { /* 依次輸入m個非零項(xiàng)（可按任意順序） */
     scanf("%f,%d",&e.coef,&e.expn);
     if(!LocateElemP(*P,e,&q,cmp)) /* 當(dāng)前鏈表中不存在該指數(shù)項(xiàng),cmp是實(shí)參 */
       if(MakeNode(&s,e)) /* 生成結(jié)點(diǎn)并插入鏈表 */
         InsFirst(P,q,s);
   }
 }

 void PrintPolyn(polynomial P)
 { /* 打印輸出一元多項(xiàng)式P */
   Link q;
   q=P.head->next; /* q指向第一個結(jié)點(diǎn) */
   printf("  系數(shù)    指數(shù)\n");
   while(q)
   {
     printf("%f  %d\n",q->data.coef,q->data.expn);
     q=q->next;
   }
 }

 void AddPolyn(polynomial *Pa,polynomial *Pb) /* 算法2.23 */
 { /* 多項(xiàng)式加法:Pa=Pa+Pb,并銷毀一元多項(xiàng)式Pb */
   Position ha,hb,qa,qb;
   term a,b;
   ha=GetHead(*Pa);
   hb=GetHead(*Pb); /* ha和hb分別指向Pa和Pb的頭結(jié)點(diǎn) */
   qa=NextPos(ha);
   qb=NextPos(hb); /* qa和qb分別指向Pa和Pb中當(dāng)前結(jié)點(diǎn)（現(xiàn)為第一個結(jié)點(diǎn)） */
   while(!ListEmpty(*Pa)&&!ListEmpty(*Pb)&&qa)
   { /* Pa和Pb均非空且ha沒指向尾結(jié)點(diǎn)(qa!=0) */
     a=GetCurElem(qa);
     b=GetCurElem(qb); /* a和b為兩表中當(dāng)前比較元素 */
     switch(cmp(a,b))
     {
       case -1:ha=qa; /* 多項(xiàng)式Pa中當(dāng)前結(jié)點(diǎn)的指數(shù)值小 */
               qa=NextPos(ha); /* ha和qa均向后移一個結(jié)點(diǎn) */
               break;
       case 0: qa->data.coef+=qb->data.coef;
               /* 兩者的指數(shù)值相等,修改Pa當(dāng)前結(jié)點(diǎn)的系數(shù)值 */
               if(qa->data.coef==0) /* 刪除多項(xiàng)式Pa中當(dāng)前結(jié)點(diǎn) */
               {
                 DelFirst(Pa,ha,&qa);
                 FreeNode(&qa);
               }
               else
                 ha=qa;
               DelFirst(Pb,hb,&qb);
               FreeNode(&qb);
               qb=NextPos(hb);
               qa=NextPos(ha);
               break;
       case 1: DelFirst(Pb,hb,&qb); /* 多項(xiàng)式Pb中當(dāng)前結(jié)點(diǎn)的指數(shù)值小 */
               InsFirst(Pa,ha,qb);
               ha=ha->next;
               qb=NextPos(hb);
     }
   }
   if(!ListEmpty(*Pb))
   {
     (*Pb).tail=hb;
     Append(Pa,qb); /* 鏈接Pb中剩余結(jié)點(diǎn) */
   }
   DestroyPolyn(Pb); /* 銷毀Pb */
 }

 void AddPolyn1(polynomial *Pa,polynomial *Pb)
 { /* 另一種多項(xiàng)式加法的算法:Pa=Pa+Pb,并銷毀一元多項(xiàng)式Pb */
   Position qb;
   term b;
   qb=GetHead(*Pb); /* qb指向Pb的頭結(jié)點(diǎn) */
   qb=qb->next; /* qb指向Pb的第一個結(jié)點(diǎn) */
   while(qb)
   {
     b=GetCurElem(qb);
     OrderInsertMerge(Pa,b,cmp);
     qb=qb->next;
   }
   DestroyPolyn(Pb); /* 銷毀Pb */
 }

 void Opposite(polynomial Pa)
 { /* 一元多項(xiàng)式系數(shù)取反 */
   Position p;
   p=Pa.head;
   while(p->next)
   {
     p=p->next;
     p->data.coef*=-1;
   }
 }

 void SubtractPolyn(polynomial *Pa,polynomial *Pb)
 { /* 多項(xiàng)式減法:Pa=Pa-Pb,并銷毀一元多項(xiàng)式Pb */
   Opposite(*Pb);
   AddPolyn(Pa,Pb);
 }

 void MultiplyPolyn(polynomial *Pa,polynomial *Pb)
 { /* 多項(xiàng)式乘法:Pa=PaPb,并銷毀一元多項(xiàng)式Pb */
   polynomial Pc;
   Position qa,qb;
   term a,b,c;
   InitList(&Pc);
   qa=GetHead(*Pa);
   qa=qa->next;
   while(qa)
   {
     a=GetCurElem(qa);
     qb=GetHead(*Pb);
     qb=qb->next;
     while(qb)
     {
       b=GetCurElem(qb);
       c.coef=a.coef*b.coef;
       c.expn=a.expn+b.expn;
       OrderInsertMerge(&Pc,c,cmp);
       qb=qb->next;
     }
     qa=qa->next;
   }
   DestroyPolyn(Pb); /* 銷毀Pb */
   ClearList(Pa); /* 將Pa重置為空表 */
   (*Pa).head=Pc.head;
   (*Pa).tail=Pc.tail;
   (*Pa).len=Pc.len;
 }