shuju02.c

程序

#include<stdio.h>
#define OK   1
#define TRUE  1
#define ERROR 0
#define NULL 0
#define FALSE 0
typedef int Status;
typedef int Boolean;

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

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

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

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

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

Status InitList(LinkList *L)
{  Link p;
   p=(Link)malloc(sizeof(LNode));
   if(p)
   { p->next=NULL;
     (*L).head=(*L).tail=p;
     (*L).len=0;
     return OK;
   }
   else
     return ERROR;
}

Status ClearList(LinkList *L)
{  Link p,q;
   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;
     }
     free(q);
     (*L).tail=(*L).head;
     (*L).len=0;
   }
   return OK;
}

Status DestroyList(LinkList *L)
{  ClearList(L);
   FreeNode(&(*L).head);
   (*L).tail=NULL;
   (*L).len=0;
   return OK;
}

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

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;
   }
   else
     return FALSE;
}

Status Append(LinkList *L,Link s)
{  int i=1;
   (*L).tail->next=s;
   while(s->next)
   { s=s->next;
     i++;
   }
   (*L).tail=s;
   (*L).len+=i;
   return OK;
}

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

Position GetHead(LinkList L)
{ return L.head;
}

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

Position PriorPos(LinkList L,Link p)
{  Link q;
   q=L.head->next;
   if(q==p)
     return NULL;
   else
   {  while(q->next!=p)
      q=q->next;
     return q;
   }
}

Status LocateElemP(LinkList L,ElemType e,Position *q,int(*compare)(ElemType,ElemType))
{  Link p=L.head,pp;
   do
   { pp=p;
     p=p->next;
   }while(p&&(compare(p->data,e)<0));
   if(!p||compare(p->data,e)>0)
   { *q=pp;
     return FALSE;
   }
   else
   { *q=p;
     return TRUE;
   }
}

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

typedef LinkList polynomial;
#define DestroyPolyn DestroyList
#define PolynLength ListLength

Status OrderInsertMerge(LinkList *L,ElemType e,int(* compare)(term,term))
{  Position q,s;
   if(LocateElemP(*L,e,&q,compare))
   { q->data.coef+=e.coef;
     if(!q->data.coef)
     { s=PriorPos(*L,q);
       if(!s)
         s=(*L).head;
       DelFirst(L,s,&q);
       FreeNode(&q);
     }
     return OK;
   }
   else
     if(MakeNode(&s,e))
     { InsFirst(L,q,s);
       return OK;
     }
     else
       return ERROR;
}

int cmp(term a,term b)
{ if(a.expn==b.expn)
     return 0;
   else
     return (a.expn-b.expn)/abs(a.expn-b.expn);
}

void CreatPolyn(polynomial *P,int m)
{  Position q,s;
   term e;
   int i;
   InitList(P);
   printf("Please input %d coefs and expns in turn and devide with (,)\n",m);
   for(i=1;i<=m;++i)
   { scanf("%f,%d",&e.coef,&e.expn);
     if(!LocateElemP(*P,e,&q,cmp))
       if(MakeNode(&s,e))
         InsFirst(P,q,s);
   }
}

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

void AddPolyn(polynomial *Pa,polynomial *Pb) /* 算法2.23 */
{  Position ha,hb,qa,qb;
   term a,b;
   ha=GetHead(*Pa);
   hb=GetHead(*Pb);
   qa=NextPos(ha);
   qb=NextPos(hb);
   while(!ListEmpty(*Pa)&&!ListEmpty(*Pb)&&qa)
   { a=GetCurElem(qa);
     b=GetCurElem(qb);
     switch(cmp(a,b))
     { case -1:ha=qa;
               qa=NextPos(ha);
               break;
       case 0: qa->data.coef+=qb->data.coef;

               if(qa->data.coef==0)
               {
                 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);
               InsFirst(Pa,ha,qb);
               ha=ha->next;
               qb=NextPos(hb);
     }
    }
   if(!ListEmpty(*Pb))
   { (*Pb).tail=hb;
     Append(Pa,qb);
   }
   DestroyPolyn(Pb);
}

void Opposite(polynomial Pa)
{  Position p;
   p=Pa.head;
   while(p->next)
   { p=p->next;
     p->data.coef*=-1;
   }
}

void SubtractPolyn(polynomial *Pa,polynomial *Pb)
{  Opposite(*Pb);
   AddPolyn(Pa,Pb);
}

void MultiplyPolyn(polynomial *Pa,polynomial *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);
   ClearList(Pa);
   (*Pa).head=Pc.head;
   (*Pa).tail=Pc.tail;
   (*Pa).len=Pc.len;
}

void CreatTwoPolylns(polynomial *p,polynomial *q)
{ int m;
  printf("Please input the length of the 1st Polyn:   ");
  scanf("%d",&m);
  CreatPolyn(p,m);
  printf("Please input the length of the 2nd Polyn:   ");
  scanf("%d",&m);
  CreatPolyn(q,m);
}

main()
{  int flag=1;
   polynomial p,q;
   int i,m;
   while(flag)
  { printf(" \nYou can select   1: run AddPolyn\n");
   printf("                 2: run SubtractPolyn\n");
   printf("                 3: run MultiplyPolyn\n");
   printf("                 4: end\n");
   printf("Please input:  ");
   scanf("%d",&i);
   while(i>4)
    { printf("Number error! Please input a number (0<i<5) again\n");
      printf("Please input: ");
      scanf("%d",&i);
    }
 switch(i)
   { case 1: CreatTwoPolylns(&p,&q);
             AddPolyn(&p,&q);
             printf("The result of the two Polyns added is: \n");
             PrintPolyn(p);
	     break;
     case 2: CreatTwoPolylns(&p,&q);
             SubtractPolyn(&p,&q);
             printf("The result of the two Polyns subtracted is: \n");
             PrintPolyn(p);
             break;
     case 3: CreatTwoPolylns(&p,&q);
             MultiplyPolyn(&p,&q);
             printf("The result of the two Polyns multiplied is: \n");
             PrintPolyn(p);
			 break;
     case 4: flag=0;
    }
  }
}