一元稀疏多项式计算器.cpp

一多项式求值,求导,减法,乘法,加法. 输出形式为类数学表达式, 指数升序排列.

#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#include "string.h"
#include "iostream.h"
#include "math.h"
#include "stdlib.h"

#define TRUE       1
#define FALSE      0
typedef int status;

typedef struct NodeType 
{
    float coef;  //系数
    int   expn;  //指数
    struct NodeType *next;
} NodeType, *LinkType;

typedef LinkType polynomail; //用带头结点的有序链表表示多项式

//——————————基本操作的函数————————————
void InitPolyn( polynomail &P);
     //构造一个多项式
status MakeNode( polynomail &pp,float Ncoef,int Nexpn);
     //创建一个结点
void CreatPolyn( polynomail &P,int m);
     //输入m项的系数和指数，建立表示一元多项式的有序链表P
void ClearPolyn( polynomail &P);
     //将单链表清空，并释放原链表的结点空间
void DestroyPolyn( polynomail &P);
     //销毁一元多项式P
void PrintPolyn( polynomail P);
     //打印输出一元多项式P
int  PolynLength( polynomail P);
     //返回一元多项式P中的项数
void MergePolynCoef(polynomail &Pn);
     //在序链表中,合并同类项
void SortPolyn(polynomail &Pn);
     //根据链表的expn指数域，对链表进行升序排序
void DelZeroNode(polynomail &Pn);
     //释放无用结点,即系数为0项
void AddPolyn( polynomail Pa,polynomail Pb,polynomail &Pc);
     //完成多项式相加运算，即：Pc=Pa+Pb
void SubtractPolyn( polynomail Pa,polynomail Pb,polynomail &Pc);
     //完成多项式相减运算，即：Pc=Pa-Pb
void MultiplyPolyn( polynomail Pa,polynomail Pb,polynomail &Pc);
     //完成多项式相乘运算，即：Pc=Pa×Pb
void Difference( polynomail &pa);
     //求多项式的导函数
float Evaluate(polynomail pn, float x);
     //求多项式的值


//————————基本操作的算法————————————————

void InitPolyn( polynomail &P)
//构造一个多项式
{  
   P=(NodeType *)malloc(sizeof(NodeType));
   P->coef=0;P->expn=0;P->next=NULL;
   //初始化带头结点的单链表
}

void ClearPolyn( polynomail &P)
//将单链表清空，并释放原链表的结点空间
{ LinkType q;
  q=P->next;
  while(q!=NULL) //释放原链表的结点空间
  {P->next=q->next;free(q);q=P->next;}
}

void DestroyPolyn( polynomail &P) 
//销毁一元多项式P
{LinkType q=P;
 while(q!=NULL)
 {q=P->next;free(P);}//释放所有结点空间
}

void SortPolyn(polynomail &Pn)
//根据链表的expn指数域，对链表进行升序排序
{ 
  MergePolynCoef(Pn);//先合并同类项
  LinkType p,q,r;
  q=Pn->next;Pn->next=NULL;
  while(q!=NULL) //插入法排序
  {  p=Pn; 
	 while(p->next!=NULL&&p->next->expn<q->expn)
		 p=p->next;

	 r=q->next;
	 q->next=p->next;
	 p->next=q;
	 q=r;   
  } 
}

void DelZeroNode(polynomail &Pn)
 //释放无用结点,即系数为0项
{ LinkType p,q;
  p=Pn->next; q=Pn;
  while(p!=NULL)
  {  if(p->coef==0)
	  {q->next=p->next;
	   free(p);
	   p=q->next;
	  }
     else 
	 {q=p;p=p->next;}
  }
}

void MergePolynCoef(polynomail &Pn)
//在序链表中,合并同类项
{ LinkType p,p1,p2;
  p=Pn->next; 
  while(p!=NULL)
  {p1=p;p2=p->next;
    while(p2!=NULL) //合并指数相同项
	{ if(p->expn==p2->expn)
		{p->coef+=p2->coef;
		 p1->next=p2->next;
		 free(p2);
		 p2=p1->next;
		}
	   else {p1=p2;p2=p1->next;}
	 }
	p=p->next;
  }
 DelZeroNode(Pn);//删除合并后系数为0的结点
}

status MakeNode( polynomail &pp,float Ncoef,int Nexpn)
//创建一个结点
{
    if (!(pp=(LinkType)malloc(sizeof(NodeType)))) 
    {
     cout<<"Error, the memory is overflow!"<<endl;
     return FALSE;
    }
    pp->coef=Ncoef;
    pp->expn=Nexpn;
    pp->next=NULL;
 return TRUE;
}

void CreatPolyn( polynomail &P,int m)
//输入m项的系数和指数，建立表示一元多项式的有序链表P
{  float fcoef;
   int fexpn;
   NodeType *s,*q;
   q=P;
 //if(m==0)cout<<"空表!";
 for(int i=1;i<=m;i++)
   { cout<<"第"<<i<<"项式"<<endl;
     cout<<"系数,指数:";
	 cin>>fcoef>>fexpn;
	 s=(NodeType *)malloc(sizeof(NodeType));
	 s->coef=fcoef;s->expn=fexpn;s->next=NULL;
	 q->next=s;q=s;q->next=NULL;
   }
 MergePolynCoef(P); //合并指数相同项
 DelZeroNode(P);    //删除系数为0的结点
 SortPolyn(P);      //按指数域，对链表进行升序排序
}

void PrintPolyn(polynomail P) 
//打印输出一元多项式P
{ LinkType q;
  q=P->next;
  if(P->next==NULL) cout<<"0";
  else{
  //cout<<"\n输出多项式:";
   while(q!=NULL)
   {if(q->coef>1||q->coef<-1)
	  cout<<q->coef;
     if(q->expn==0&&(q->coef==1||q->coef==-1))cout<<q->coef;
     else if(q->coef==-1&&q->expn!=0) cout<<"-";

     if(q->expn<0) cout<<"x^"<<"("<<q->expn<<")";
     else if(q->expn==1) cout<<"x"; 
     else if(q->expn>0) cout<<"x^"<<q->expn;

     if(q->next!=NULL&&q->next->coef>0)cout<<"+";
    q=q->next;
   }
  }//else
 //cout<<endl;
}

int PolynLength( polynomail P) 
//返回一元多项式P中的项数
{ int i=0;
  LinkType q;
  q=P->next;
 while(q!=NULL) {q=q->next;i++;}
 return i;
}

void Difference(polynomail &pa)
// 稀疏多项式pa 以链表作存储结构，    
// 将此链表修改成它的导函数，并释放无用结点 
{
   LinkType p,q;
   p=pa->next;
   q=pa;
   while(p!=NULL)
   {  
     if(p->expn==0) {q->next=p->next;free(p);p=q->next;}
      //常数项，导数为零，释放结点
     else 
      {
      p->coef=p->coef*p->expn; //系数=原系数* 指数
      (p->expn )--; //指数减1
	  q=q->next;
      p=p->next;
      }
   }  
}

float Evaluate(polynomail pn, float x)
//求多项式的值
{ LinkType p;
  p=pn->next;
  float result=0;
  while(p!=NULL)
  {
   result+=(p->coef)*(float)pow(x,p->expn);
   //pow函数求x的n次方
   p=p->next;
  }
return result;
}

void AddPolyn(polynomail Pa,polynomail Pb,polynomail &Pc)
//完成多项式相加运算，即：Pc=Pa+Pb
{  float x;
   LinkType p,q,r;
   NodeType *s;
   p=Pa->next;
   q=Pb->next;
   r=Pc;
 while(p!=NULL&&q!=NULL)
  { if(p->expn==q->expn)//指数相同
	 { x=p->coef+q->coef ;
	    if(x!=0)  //指数相同，若系数相加不等于0,插入表中
		{s=(NodeType *)malloc(sizeof(NodeType));
		 s->coef=x;s->expn=q->expn;s->next=NULL;
         r->next=s;r=r->next;
		}
	  p=p->next;q=q->next;
	 }
	else if(q->expn<p->expn) //指数小的插入表中
	 {   s=(NodeType *)malloc(sizeof(NodeType));
		 s->coef=q->coef;s->expn=q->expn;s->next=NULL;
         r->next=s;r=r->next;
	  q=q->next;
	 }
    else  
	 {   s=(NodeType *)malloc(sizeof(NodeType));
		 s->coef=p->coef;s->expn=p->expn;s->next=NULL;
         r->next=s;r=r->next;
	   p=p->next;
	 }
  }
//加入余下的多项式 
  while(p!=NULL)
  { s=(NodeType *)malloc(sizeof(NodeType));
	s->coef=p->coef;s->expn=p->expn;s->next=NULL;
    r->next=s;r=r->next;
  p=p->next;
  }
  while(q!=NULL)
  { s=(NodeType *)malloc(sizeof(NodeType));
    s->coef=q->coef;s->expn=q->expn;s->next=NULL;
    r->next=s;r=r->next;
	q=q->next;
	}
}

void SubtractPolyn( polynomail Pa,polynomail Pb,polynomail &Pc)
     //完成多项式相减运算，即：Pc=Pa-Pb
{ float x;
   LinkType p,q,r;
   NodeType *s;
   p=Pa->next;
   q=Pb->next;
   r=Pc;
 while(p!=NULL&&q!=NULL)
  {  if(p->expn==q->expn)//指数相同
	 { x=p->coef-q->coef;
	    if(x!=0) //指数相同，若系数相减不等于0,插入表中
		{s=(NodeType *)malloc(sizeof(NodeType));
		 s->coef=x;s->expn=q->expn;s->next=NULL;
         r->next=s;r=r->next;
		}
	  p=p->next;q=q->next;
	 }
	 else if(q->expn<p->expn) //指数小的插入表中
	 {   s=(NodeType *)malloc(sizeof(NodeType));
		 s->coef=-q->coef; //减数的系数变为相反数
		 s->expn=q->expn;s->next=NULL;
         r->next=s;r=r->next;
	  q=q->next;
	 }
     else  
	 {   s=(NodeType *)malloc(sizeof(NodeType));
		 s->coef=p->coef;s->expn=p->expn;s->next=NULL;
         r->next=s;r=r->next;
	  p=p->next;
	 }
  }
//加入余下的多项式，减数的系数变为相反数
  while(p!=NULL)
  { s=(NodeType *)malloc(sizeof(NodeType));
	s->coef=p->coef;s->expn=p->expn;s->next=NULL;
    r->next=s;r=r->next;
  p=p->next;
  }
  while(q!=NULL)
  { s=(NodeType *)malloc(sizeof(NodeType));
    s->coef=-q->coef;s->expn=q->expn;s->next=NULL;
    r->next=s;r=r->next;
	q=q->next;
	}
}

void MultiplyPolyn( polynomail Pa,polynomail Pb,polynomail &Pc)
 //完成多项式相乘运算，即：Pc=Pa×Pb
{  LinkType p,q,r;
   NodeType *s;
   p=Pa->next; 
   r=Pc;
   while(p!=NULL)
   {q=Pb->next;
     while(q!=NULL)
	 { s=(NodeType *)malloc(sizeof(NodeType));
	   s->coef=p->coef*q->coef;
	   s->expn=p->expn+q->expn;
	   s->next=NULL;

       r->next=s;r=r->next;
	   q=q->next;
	 }
	 p=p->next;
   }
 MergePolynCoef(Pc);//合并指数相同项
 DelZeroNode(Pc);   //删除系数为0的结点
 SortPolyn(Pc);     //按指数域，对链表进行升序排序

}


void main()
{ float x,sum;
  LinkType pa,pb,pc;
  InitPolyn(pa);
  InitPolyn(pb);
  InitPolyn(pc);
  int num1,num2;

inp: while(1)
{system("cls");
	cout<<endl;
	cout<<"                        一元稀疏多项式计算器                                "<<endl;
    cout<<"    班级：计算机科学与技术02（8）班   学生：陈 堪   学号：200209124204      "<<endl;
	cout<<" ==========================================================================="<<endl;
	cout<<"     求值—1    加法—2      减法—3    乘法—4    求导—5    退出--0       "<<endl;
	cout<<" ==========================================================================="<<endl;
    cout<<" 测试数据为:A1=7-5x^8+11x^9             A2=1+x+x^2+x^3+x^4+x^5              "<<endl;
	cout<<"            B1=6x(-3)+4.4x^2-1.2x^9     B2=-x^3-x^4                         "<<endl;

  char choice;
  cout<<endl<<" 请选择操作(0-5):";
  cin>>choice;
  cout<<endl;
  switch(choice)
  {  case '1': cout<<"求多项式A的值"<<endl;
             cout<<"输入多项式A的项数:";
             cin>>num1;
             CreatPolyn(pa,num1);
             cout<<"多项式A为:";
			 PrintPolyn(pa);
			 cout<<endl<<endl;

			 cout<<"输入x的值：";
			 cin>>x;
			 sum=Evaluate(pa, x);
			 cout<<"多项式A的值:";
			 PrintPolyn(pa);
			 cout<<"="<<sum;

			 ClearPolyn(pa);
			 cout<<"\nPress any key to continue!"<<endl;
             getche();system("cls");goto inp;

     case '2': cout<<"多项式加法C=A+B"<<endl;
		     cout<<"输入多项式A的项数:";
             cin>>num1;
             CreatPolyn(pa,num1);
			 cout<<"多项式A为:";
			 PrintPolyn(pa);
			 cout<<endl<<endl;

			 cout<<"输入多项式B的项数:";
             cin>>num2;
             CreatPolyn(pb,num2);
			 cout<<"多项式B为:";
			 PrintPolyn(pb);
			 cout<<endl<<endl;
             
			 AddPolyn(pa,pb,pc);
             cout<<"多项式C=A+B: (";
			 PrintPolyn(pa);
			 cout<<")+(";
			 PrintPolyn(pb);
			 cout<<")=";
			 PrintPolyn(pc);

			 ClearPolyn(pa);
			 ClearPolyn(pb);
			 ClearPolyn(pc);
		     cout<<"\nPress any key to continue!"<<endl;
             getche();system("cls");goto inp;

	 case '3': cout<<"多项式减法C=A-B"<<endl;
		     cout<<"输入多项式A的项数:";
             cin>>num1;
             CreatPolyn(pa,num1);
			 cout<<"多项式A为:";
			 PrintPolyn(pa);
			 cout<<endl<<endl;

			 cout<<"输入多项式B的项数:";
             cin>>num2;
             CreatPolyn(pb,num2);
			 cout<<"多项式B为:";
			 PrintPolyn(pb);
			 cout<<endl<<endl;
             
			 SubtractPolyn(pa,pb,pc);
             cout<<"多项式C=A-B: (";
			 PrintPolyn(pa);
			 cout<<")-(";
			 PrintPolyn(pb);
			 cout<<")=";
			 PrintPolyn(pc);

			 ClearPolyn(pa);
			 ClearPolyn(pb);
			 ClearPolyn(pc);
		     cout<<"\nPress any key to continue!"<<endl;
             getche();system("cls");goto inp;
		 
		
	 case '4': cout<<"多项式乘法C=A×B"<<endl;
		     cout<<"输入多项式A的项数:";
             cin>>num1;
             CreatPolyn(pa,num1);
			 cout<<"多项式A为:";
			 PrintPolyn(pa);
			 cout<<endl<<endl;

			 cout<<"输入多项式B的项数:";
             cin>>num2;
             CreatPolyn(pb,num2);
			 cout<<"多项式B为:";
			 PrintPolyn(pb);
			 cout<<endl<<endl;
             
			 MultiplyPolyn(pa,pb,pc);
             cout<<"多项式C=A×B: (";
			 PrintPolyn(pa);
			 cout<<")×(";
			 PrintPolyn(pb);
			 cout<<")=";
			 PrintPolyn(pc);

			 ClearPolyn(pa);
			 ClearPolyn(pb);
			 ClearPolyn(pc);
		     cout<<"\nPress any key to continue!"<<endl;
             getche();system("cls");goto inp;
		 		    
	 case '5': cout<<"求多项式A的导数"<<endl;
             cout<<"输入多项式A的项数:";
             cin>>num1;
             CreatPolyn(pa,num1);
             cout<<"多项式A为:";
			 PrintPolyn(pa);
			 cout<<endl<<endl;

			 cout<<"多项式A的导数: (";
			 PrintPolyn(pa);
			 cout<<")’= ";
			 Difference(pa);
			 PrintPolyn(pa);
             			 
			 ClearPolyn(pa);
			 cout<<"\nPress any key to continue!"<<endl;
             getche();system("cls");goto inp;
		 
	 case '0':cout<<"谢谢使用!再见!"<<endl<<endl;
		    return ;

     default:cout<<"错误命令!"<<endl;
		     cout<<"Press any key to continue!"<<endl;
             getche();system("cls");goto inp;

  }//switch
 }//whlie(1)

}