厳蔚敏データ構造:チェーンは一元多項式の加算を実現します.

一、基本概念
1、多項式pn(x)は、次のように表されます. pn(x)=a 0+a 1 x+a 2 x 2+…+anxn.
listP={(a 0,e 0),(a 1,e 1),(a 2,e 2),…,(an,en)}.このような線形表の記述では、各ノードは、2つのデータドメインを含み、対応するタイプの説明は以下の通りである.
typedef struct node
{double coef}           //係数はダブル精度タイプです.
  int expn               //指数は正の整数です  struct node*next;   //ポイロイド;         
二、アルゴリズム思想は、2つの多項式を加算する演算規則は、ポインタqaとqbがそれぞれ多項式A(x)とB(x)の中で現在比較しているある結点を指すと仮定すると、2つの結点データ領域の指数項目を比較し、3つの場合があります.Qaポインタが指す結点を保留し、qaポインタを後に移動します.(2)ポインタqaが指すポイントの指数値＞ポインタqbが指すポイントの指数値は、qbポインタが指すノードをqaが指すノードの前に挿入し、qbポインタを後に移動します.(3)ポインタqaが指す結点の指数値＝ポインタqbが指す結点の指数値は、2つの結点の係数を加算します.和がゼロでない場合、qaの指す結点の係数値を修正し、同時にqbの指す結点を釈放する.逆に、多項式A(x)のチェーンから該当する結点を削除し、ポインタqaとqbの指す結点を解放します.

#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR -1
#define FALSE 0
#define TRUE 2
typedef int Status;

typedef struct
{
float coef; //  
int expn;   //  
}term,ElemType;

typedef struct LNode
{
ElemType data;
struct LNode *next;
}*Link,*Position;


typedef struct
{
Link head,tail;
int len;
}LinkList;


typedef LinkList polynomial; //               


int cmp(term a,term b)
{
if(a.expnnext=NULL;
   P.head=P.tail=p;
   P.len=0;
   return OK;
  }//
else return ERROR;
}//InitList


Position GetHead(polynomial P)
{
return P.head;
}//Position


Status SetCurElem(Position h,term e)
{
h->data=e;
return OK;
}//SetCurElem


Status LocateElem(LinkList P,ElemType e,Position &q,int(*cmp)(ElemType,ElemType))
{
Link p=P.head,pp;
do
  {
  pp=p;
  p=p->next;
  }while(p&&(cmp(p->data,e)<0));

  if(!p||cmp(p->data,e)>0)
  {
  q=pp;
  return FALSE;
  }//if

  else //find it
  {
  q=p;
  return TRUE;
  }//else
}


Status MakeNode(Link &p,ElemType e)
{
p=(Link)malloc(sizeof(LNode));
if(!p) return ERROR;
p->data=e;
return OK;
}//MakeNode


 


Status InsFirst(LinkList &P,Link h,Link s)
{
s->next=h->next;
h->next=s;
if(h==P.tail)
P.tail=h->next;
++P.len;
return OK;
}//InsFirst


 


void CreatPolyn(polynomial &P,int m)

{//  m       ，              P
InitList(P);
Position h,q,s;
h=GetHead(P); //h  P    
term e;
e.coef=0.0;
e.expn=-1;
SetCurElem(h,e);//          
printf("input the the value of m(indicate how many items)
");
scanf("%d",&m);
printf("input (%d) ceof,expn(separated by ,)
",m);
for(int i=1;i<=m;++i)
  {
  scanf("%f,%d",&e.coef,&e.expn);
  if(!LocateElem(P,e,q,cmp))
    {
    if(MakeNode(s,e)) InsFirst(P,q,s);
    }//if   ，         
  }//for
}//CreatPolyn


Position NextPos(Link p)
{
return p->next;
}//NextPos


ElemType GetCurElem(Link p)
{
return p->data;
}//GetCurElem



Status DelFirst(LinkList L,Link h,Link &q)
{
q=h->next;
if(q)//    
  {
   h->next=q->next;
   if(!h->next) //     
          L.tail=h;
   L.len--;
   return OK;
  }//if

else return FALSE; //   

}//DelFirst


 


void FreeNode(Link &p)
{
free(p);
p=NULL;
}//FreeNode


Status ListEmpty(LinkList L)
{
if(L.len)
       return FALSE;
else return TRUE;
}//ListEmpty


Status Append(LinkList &L,Link s)
{
int i=1;
L.tail->next=s;
while(s->next)
  {
  s=s->next;
  i++;
  }//while

L.tail=s;
L.len+=i;
return OK;
}//Append


void PrintPolyn(polynomial P)
{
Link q;
q=P.head->next;
printf("      
");
while(q)
  {
   printf("%f   %d
",q->data.coef,q->data.expn);
   q=q->next;
  }//while
}//PrintPolyn



Status ClearList(LinkList &L)
{
Link q,p;
if(L.head!=L.tail)
  {
   p=q=L.head->next;
   L.head->next=NULL;
   while(p!=L.tail)
   {
   p=q->next;
  free(q);
   q=p;
   }//while
   free(q);
   L.tail=L.head;
   L.len=0;

  }//if
return OK;
}//ClearList




Status DestroyPolyn(LinkList &L)
{ //       L，L    
   ClearList(L); //     
   FreeNode(L.head);
   L.tail=NULL;
   L.len=0;
   return OK;


}//DestroyList


 void AddPolyn(polynomial &Pa,polynomial &Pb)

 { //      :Pa=Pa+Pb,        Pb
   Position ha,hb,qa,qb;
   term a,b;
   ha=GetHead(Pa);
   hb=GetHead(Pb); // ha hb    Pa Pb    
   qa=NextPos(ha);
   qb=NextPos(hb); // qa qb    Pa Pb     （       ）
   while(qa&&qb)
   { // Pa Pb    ha      (qa!=0)
     a=GetCurElem(qa);
     b=GetCurElem(qb); // a b          
     switch(cmp(a,b))
     {
       case -1:ha=qa; //    Pa          
               qa=NextPos(ha); // ha qa        
               break;
       case 0: qa->data.coef+=qb->data.coef;
              //         ,  Pa        
               if(qa->data.coef==0) //      Pa     
               {
                 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); //    Pb          
               InsFirst(Pa,ha,qb);
               ha=ha->next;
               qb=NextPos(hb);
     }
   }
   if(!ListEmpty(Pb))
   {
     Pb.tail=hb;
     Append(Pa,qb); //   Pb     
   }
   DestroyPolyn(Pb); //   Pb
 }



int main()
{
polynomial Pa,Pb;
int m;
CreatPolyn(Pa,m);
PrintPolyn(Pa);
printf("Pa.len: %d
",Pa.len);
CreatPolyn(Pb,m);
PrintPolyn(Pb);
printf("Pb.len: %d
",Pb.len);
AddPolyn(Pa,Pb);
PrintPolyn(Pa);
printf("Pa.len: %d
",Pa.len);
return 1;
}