polyniomial.cpp

数据结构课程经典源码

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
typedef struct Item{
  double  coef;
  int     expn;
  struct Item *next;
  }Item,*Polyn;
#define CreateItem(p) p=(Item *)malloc(sizeof(Item));
#define DeleteItem(p) free((void *)p);
int menu(void);
int PolynNotEmpty(Item *h,char *p);

int Select(char *str)
  { char ch;
    printf("%s\n",str);
    printf("Input Y or N:");
    do{ ch=getch();
	}while(ch!='Y'&&ch!='y'&&ch!='N'&&ch!='n');
    printf("\n");
    if(ch=='Y'||ch=='y') return(1);
    else return(0);
    }
int InsertLocate(Polyn h,int expn,Item **p)
  //查找给定指数expn在指定多项式中是否存在
  //若不存在且指数expn为最小，则返回0和最后一个结点指针
  //若存在，则返回1和对应结点指针
  //若不存在且指数expn值在某两个结点之间，则返回－1和指数值大于expn结点指针
  { Item *pre,*q;
    pre=h;
    q=h->next;
    while(q&&q->expn>expn) 
      { pre=q;
        q=q->next;
	}
    if(!q)
      { *p=pre;
	return(1);
	}
    else if(q->expn==expn)
      { *p=q;
	return(0);
	}
    else
      { *p=pre;
	return(-1);
        }
    }
        

void insert(Item *pre,Item *p)
{
    p->next=pre->next;
    pre->next=p;
    }
Polyn Input(void)
{
  double  coef;
  int     expn,flag;
  Item *h,*p,*q,*pp;
  CreateItem(h);
  h->next=NULL;
  printf("input coef and expn(if end ,expn=-1)\n");
  while(1)
  {
    scanf("%lf%d",&coef,&expn);
    if(expn==-1) break;
    if(InsertLocate(h,expn,&pp))
     { CreateItem(p);
       p->coef=coef;
       p->expn=expn;
       insert(pp,p);
       }
     else if(Select("has the same expn,Replace older value?"))
	  pp->coef=coef;
     }
  return h;
  }
void Destroy(Polyn h)
{
  Item *p=h,*q;
  while(p!=NULL)
  {
    q=p;
    p=p->next;
    DeleteItem(q);
    }
  }
void Output(Polyn h,char *title)
{
  int flag=1;
  Item *p=h->next;
  printf("%s=",title);
  while(p)
  { if(flag)
      { flag=0;
	if(p->expn==0) 	printf("%.2lf",p->coef);
	else printf("%.2lfx^%d",p->coef,p->expn);
	}
    else
      { if(p->coef>0) printf("+");
	if(p->expn==0) 	printf("%.2lf",p->coef);
	else printf("%.2lfx^%d",p->coef,p->expn);
	}
    p=p->next;
    }
 printf("\n");
 }
Polyn AddPolyn(Polyn h1,Polyn h2) //两个多项式相加
{
  Item *head,*last,*pa=h1->next,*pb=h2->next,*s,*s0;
  double coef;
  CreateItem(head);
  last=head;
  while(pa&&pb)
    if(pa->expn==pb->expn)
    {
      coef=pa->coef+pb->coef;
      if(coef!=0)
      {
	CreateItem(s);
	s->coef=coef;
	s->expn=pa->expn;
	last->next=s;
	last=s;
	}
      pa=pa->next;
      pb=pb->next;
      }
    else
      {
	if(pa->expn>pb->expn)
	  {
	    s0=pa;
	    pa=pa->next;
	    }
	else
	  {
	    s0=pb;
	    pb=pb->next;
	    }
	CreateItem(s);
	s->coef=s0->coef;
	s->expn=s0->expn;
	last->next=s;
	last=s;
	}
    s0=pa?pa:pb;
    while(s0)
    {
      CreateItem(s);
      s->coef=s0->coef;
      s->expn=s0->expn;
      last->next=s;
      last=s;
      s0=s0->next;
      }
    last->next=NULL;
    return head;
    }
Polyn SubtractPolyn(Polyn h1,Polyn h2)
{ int flag;
  Item *head,*last,*pa=h1->next,*pb=h2->next,*s,*s0;
  double coef;
  CreateItem(head);
  last=head;
  while(pa&&pb)
    if(pa->expn==pb->expn)
    {
      coef=pa->coef-pb->coef;
      if(coef!=0)
      {
	CreateItem(s);
	s->coef=coef;
	s->expn=pa->expn;
	last->next=s;
	last=s;
	}
      pa=pa->next;
      pb=pb->next;
      }
    else
      { if(pa->expn>pb->expn)
	  { flag=1;
	    s0=pa;
	    pa=pa->next;
	    }
	else
	  { flag=-1;
	    s0=pb;
	    pb=pb->next;
	    }
	CreateItem(s);
	s->coef=flag*s0->coef;
	s->expn=s0->expn;
	last->next=s;
	last=s;
	}
    s0=pa?pa:pb;
    flag=pa?1:-1;
    while(s0)
    {
      CreateItem(s);
      s->coef=flag*s0->coef;
      s->expn=s0->expn;
      last->next=s;
      last=s;
      s0=s0->next;
      }
    last->next=NULL;
    return head;
    }
Polyn MultPolyn(Polyn h1,Polyn h2)
{ int item,expn;
  Item *head,*pa,*pb=h2->next,*s,*pp;
  double coef;
  CreateItem(head);
  head->next=NULL;
  while(pb)
    { pa=h1->next;
      while(pa)
       { coef=pa->coef*pb->coef;
	 expn=pa->expn+pb->expn;
	 if( InsertLocate(head,expn,&pp))
	  { CreateItem(s);
	    s->coef=coef;
	    s->expn=expn;
	    insert(pp,s);
	    }
	  else pp->coef=pp->coef+coef;
	  pa=pa->next;
	  }
       pb=pb->next;
       }
    return head;
    }

void main()
{ int num;
  Polyn  h1=NULL; //p(x)
  Polyn  h2=NULL; //Q(x)
  Polyn  h3=NULL; //P(x)+Q(x)
  Polyn  h4=NULL; //P(x)-Q(x)
  Polyn  h5=NULL; //P(x)*Q(x)
  while(1)
    { num=menu();
      getchar();
      switch(num)
       {
	 case 1:
	    if(h1!=NULL)
	      { if(Select("P(x) is not Empty,Create P(x) again?"))
		 { Destroy(h1);
		   h1=Input();
		   }
		}
	    else h1=Input();
            break;
	 case 2:
	    if(h2!=NULL)
	      { if(Select("Q(x) is not Empty,Create Q(x) again?"))
		 { Destroy(h2);
		   h2=Input();
		   }
		}
	    else h2=Input();
	    break;
	 case 3:
	    if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h2,"Q(X)"))
	      {h3=AddPolyn(h1,h2);
	       Output(h3,"P(x)+Q(X)");
               printf("P(x)+Q(x) has finished!\n");
	       getchar();
               }
	    break;
	 case 4:
	    if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h2,"Q(X)"))
	      { h4=SubtractPolyn(h1,h2);
	        Output(h4,"Px)-Q(x)");
                printf("P(x)-Q(x) has finished!\n");
		getchar();
		}
	    break;
	 case 5:
            if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h2,"Q(X)"))
	      { h5=MultPolyn(h1,h2);
                Output(h5,"P(x)*Q(x)");
	        printf("P(x)*Q(x) has finished!\n");
	        getchar();
                }
	    break;
         case 6:
	    if(PolynNotEmpty(h1,"p(x)"))
	       { Output(h1,"P(x)");
		 getchar();
		 }
	    break;
	 case 7:
	    if(PolynNotEmpty(h2,"Q(x)"))
	      { Output(h2,"Q(x)");
		getchar();
		}
	    break;
	 case 8:
	    if(PolynNotEmpty(h3,"P(x)+Q(x)"))
	      { Output(h3,"P(x)+Q(x)");
		getchar();
		}
	    break;
	 case 9:
	    if(PolynNotEmpty(h4,"P(x)-Q(x)"))
	      { Output(h3,"P(x)-Q(x)");
		getchar();
		}
	    break;
	 case 10:
	    if(PolynNotEmpty(h5,"P(x)*Q(x)"))
	      { Output(h3,"P(x)*Q(x)");
		getchar();
		}
	    break;
	 case 11:
	    if(h1!=NULL) Destroy(h1);
	    if(h2!=NULL) Destroy(h2);
	    if(h3!=NULL) Destroy(h3);
	    if(h4!=NULL) Destroy(h4);
	    if(h5!=NULL) Destroy(h5);
	 }
      if(num==11) break;
      }
  getch();
  }
int menu(void)
  { int num;
    clrscr();
    printf("%20c1--create P(x)\n",' ');
    printf("%20c2--create Q(x)\n",' ');
    printf("%20c3--p(x)+Q(x)\n",' ');
    printf("%20c4--P(x)-Q(x)\n",' ');
    printf("%20c5--p(x)*Q(x)\n",' ');
    printf("%20c6--print P(x)\n",' ');
    printf("%20c7--print Q(x)\n",' ');
    printf("%20c8--print P(x)+Q(x)\n",' ');
    printf("%20c9--print P(x)-Q(x)\n",' ');
    printf("%20c10--print P(x)*Q(x)\n",' ');
    printf("%20c11--Quit\n",' ');
    printf("         please select 1,2,3,4,5,6,7,8,9,10,11:");
      do{
	  scanf("%d",&num);
	  }while(num<1 || num>11);
    return(num);
    }
int PolynNotEmpty(Polyn h,char *p)
  { if(h==NULL)
      { printf("%s is not exist!\n",p);
        getchar();
	return(0);
	}
     else return(1);
     }