一元多项式的运算.cpp

用线性表实现四则运算

#include <stdio.h>
struct polynode{
	float coef;//多项式的系数
	int exp;//多项式的指数
	polynode* link;//指向下一个结点的指针
};
typedef polynode* polypointer;

polypointer attach(float c,int e,polypointer d);//建立一个新结点,其系数coef=c,指数exp=e,并把它链到d所指结点之后,并返回这个新结点的指针
void out(polypointer z);//将多项式z输出
polypointer padd(polypointer a,polypointer b);//多项式a和b相加，返回结果；
polypointer pmins(polypointer a,polypointer b);//多项式a和b相减，返回结果；
char compare(int a,int b);//比较整数的大小,返回比较结果
void queue(polypointer p);//实现合并同类项，并按降幂排列功能的函数；
polypointer mul(polypointer a,polypointer b);//多项式a和b相乘,返回结果
void del(polypointer p);//删除链表p
polypointer fmuls(polypointer p1,polypointer p2);//多项式p1的第一项和多项式p2的所有项相乘,返回结果多项式
polypointer ch(polypointer a,polypointer b,polypointer c);//多项式a除以多项式b，商存于链表c中，返回余数

void main()
{
	polypointer x,y,z,q,p;
    int b;
	float a;
	int m,n;
	int i;
	char c;

	x=new polynode;//申请结点x做第一个多项式的表头结点
	z=x;

	do{
		printf("请输入第一个多项式的项数:\n");
	    scanf("%d",&m);
	    printf("是否确定?y/n\n");
		while((getchar())!='\n')
			;
	    c=getchar();}while(c!='y'&&c!='Y');

		for(i=1;i<=m;i++)//输入第一个多项式，存于链表z中
		{
            printf("请输入第%d项的系数：\n",i);
	        scanf("%f",&a);
			printf("请输入第%d项的指数:\n",i);
			scanf("%d",&b);

			z=attach(a,b,z);
		}
        z->link=NULL;

		printf("您输入的第一个多项式是:\n");
		z=x;
		x=x->link;
		delete z;//释放表头结点

		queue(x);//第一个多项式合并同类项并降幂排列

		out(x);//输出第一个多项式

	y=new polynode;//申请结点y做为第二个多项式的表头结点
	z=y;

    do{
		printf("请输入第二个多项式的项数:\n");
	    scanf("%d",&n);
	    printf("是否确定?y/n\n");
		while((getchar())!='\n')
			;
	    c=getchar();}while(c!='y'&&c!='Y');

		for(i=1;i<=n;i++)//输入第二个多项式，存于链表z
		{
            printf("请输入第%d项的系数：\n",i);
	        scanf("%f",&a);
			printf("请输入第%d项的指数:\n",i);
			scanf("%d",&b);

			z=attach(a,b,z);
		}
		z->link=NULL;

		printf("您输入的第二个多项式是:\n");
		z=y;
		y=y->link;
		delete z;//释放表头结点
       
		queue(y);//第二个多项式合并同类项并降幂排列

		out(y);//输出第二个多项式

		do{
		printf("请输入你要进行的四则运算符号：+ - * /\n");
		while((getchar())!='\n')
			;
	    c=getchar();
		switch(c){
		case'+'://调用padd()加函数
		    z=padd(x,y);
			printf("结果是：\n");
            out(z);
			break;
		case'-'://调用pmin()减函数
			z=pmins(x,y);
			printf("结果是：\n");
			out(z);
			break;
		case'*'://调用mul()乘函数
			z=mul(x,y);
            printf("结果是：\n");
			out(z);
			break;
		case'/':
			q=new polynode;//若输入的是/，先申请结点作为存商的表头结点
			z=ch(x,y,q);//调用除法函数ch()
			p=q;
			q=p->link;
			delete p;//释放表头结点
			printf("商式是:\n");
			out(q);//将商输出
			printf("余式是:\n");
			out(z);//将余数输出
			break;
		}
		printf("还想再进行运算吗?y/n\n");
        while((getchar())!='\n')
			;
	    c=getchar();}while(c!='n'&&c!='N');//判断是否进行此多项式的其他代数运算
	
}

polypointer attach(float c,int e,polypointer d)//建立一个新结点,系数coef=c,指数exp=e,并把它插到d所指结点之后,返回此新结点的指针
{
	polypointer x;
	x=new polynode;
    x->coef=c;
	x->exp=e;
	d->link=x;
	return x;
}

void out(polypointer z)//将多项式z输出
{
	int i=1,b;
	float a;
	polypointer x;

	x=z;
	if(x==NULL)
		printf("0\n");
	while(x!=NULL){
		    a=x->coef;
		    b=x->exp;

			if(i!=1){
				if(a>0)
					printf("+");
			}
			i++;
			if(a==1)
				printf("x^%d",b);
            else 
				printf("%fx^%d",a,b);
		    x=x->link;
	}
	printf("\n");
}

polypointer padd(polypointer a,polypointer b)//多项式a和多项式b相加，返回结果多项式；
{
	polypointer p,q,d,c;
	float x;
	p=a;
	q=b;
	c=new polynode;
	d=c;//初始化；
	while((p!=NULL)&&(q!=NULL))
		switch(compare(p->exp,q->exp)){
case'=':
	x=p->coef+q->coef;
	if(x!=0)
		d=attach(x,p->exp,d);//将新结点链入；
	p=p->link;
	q=q->link;
	break;
case'>':
	d=attach(p->coef,p->exp,d);//复制p所指结点并链入c中；
	p=p->link;                 //p前进一步
	break;
case'<':
	d=attach(q->coef,q->exp,d);//复制q所指结点并链入c中；
	q=q->link;                 //q前进一步
	break;
	}
	while(p!=NULL)//复制a的剩余部分；
	{
		d=attach(p->coef,p->exp,d);
		p=p->link;
	}
	while(q!=NULL)//复制b的剩余部分；
	{
		d=attach(q->coef,q->exp,d);
		q=q->link;
	}
	d->link=NULL;//最后结点；
	p=c;
	c=c->link;
	delete p;//删除临时用结点；
	return c;
}



char compare(int a,int b)//比较整数的大小,返回比较结果
{
	if(a==b)
		   return '=';
	else if(a>b)
		   return '>';
	else 
		   return '<';
	


}

polypointer pmins(polypointer a,polypointer b)//多项式a和多项式b相减，返回结果多项式；
{
	polypointer p,q,d,c;
	float x;
	p=a;
	q=b;
	c=new polynode;
	d=c;//初始化；
	while((p!=NULL)&&(q!=NULL))
		switch(compare(p->exp,q->exp)){
case'=':
	x=p->coef-q->coef;//系数相减；
	if(x!=0)
		d=attach(x,p->exp,d);//将新结点链入；
	p=p->link;
	q=q->link;//前进一步；
	break;
case'>':
	d=attach(p->coef,p->exp,d);//复制p所指结点并链入c中；
	p=p->link;//p前进；
	break;
case'<':
	d=attach(-q->coef,q->exp,d);//复制q所指结点并链入c中；
	q=q->link;//q前进；
	break;
	}//switch and while
	while(p!=NULL)//复制a的剩余部分；
	{
		d=attach(p->coef,p->exp,d);
		p=p->link;
	}
	while(q!=NULL)//将b的剩余部分系数取反并复制；
	{
		d=attach(-q->coef,q->exp,d);
		q=q->link;
	}
	d->link=NULL;//最后结点；
	p=c;
	c=c->link;
	delete p;//删除临时用结点；
	return c;
}


void queue(polypointer p)//实现合并同类项，并按降幂排列功能的函数；
{
	polypointer p1,p2;
	int temp_e;
	float temp_c;
	int i=1,n;
    
	p1=p;

	while(p1->link!=NULL)
	{
		p2=p1->link;
			if((p1->exp)<(p2->exp))
			{
				temp_c=p1->coef;
				temp_e=p1->exp;
				p1->coef=p2->coef;
				p1->exp=p2->exp;
				p2->coef=temp_c;
				p2->exp=temp_e;
			}
	         p1=p2;	                                  //将p2当前的位置告诉p1，这样可以在下一次循环中p1可以准确找到下一项。
    			i++;
	}
	n=i;
	while(n-1)
	{
		p1=p;
		for(i=1;i<=n-1;i++)                          //每次对p1,p2所指向的多项式的指数进行多次比较。
		{
            p2=p1->link;
			if((p1->exp)<(p2->exp))                  //p1的指数小于p2的指数，就将p1向后移动一位。
			{
				temp_c=p1->coef;
				temp_e=p1->exp;
				p1->coef=p2->coef;
				p1->exp=p2->exp;
				p2->coef=temp_c;
				p2->exp=temp_e;                      
			
			}
			p1=p2;                                    //将p2当前的位置告诉p1，这样可以在下一次循环中p1可以准确找到下一项。
		}
		n--;
	}

	p1=p;		 
    while(p1->link!=NULL)
	{
			p2=p1->link;
			while(p2!=NULL)
			{
			    if((p1->exp)==(p2->exp))
				{
				   p1->coef+=p2->coef;
				   p1->link=p2->link;
				   delete p2;
				   p2=p1->link;
				}
				else break;
			}
		if(p1->link!=NULL)
		  p1=p1->link;
	}		  
}

polypointer mul(polypointer a,polypointer b)//多项式a和多项式b相乘,并返回结果多项式
{
    polypointer p1,p2,c,d,e;
	
	p1=a;
	p2=b;

	c=fmuls(p1,p2);
	p1=p1->link;
	d=fmuls(p1,p2);
	e=padd(c,d);
	del(c);
	del(d);
	while(p1!=NULL)
	{
		p1=p1->link;                         //取p1的下一项，
		c=fmuls(p1,p2);                      //与p2的每一项相乘。        
		d=e;
		e=padd(c,d);                         //记录结果到最后的多项式中
        del(c);
		del(d);
	}
    return e;
}

void del(polypointer p)//删除链表p
{ 
	polypointer q;

	while(p!=NULL)
	{ 
		q=p->link;
		delete p;
		p=q;
	}
}

polypointer fmuls(polypointer p1,polypointer p2)  //多项式p1的第一项和多项式p2的所有项相乘,返回结果多项式
{
	polypointer x,p,q;
	int b;
	float a;
	q=new polynode;                               //建立结果多项式的头节点。
	p=q;
	x=p2;                                         //x指向p2的头节点

	if(p1!=NULL)
	{
		while(x!=NULL)
		{
			a=p1->coef*x->coef;                   //多项是相乘，系数相乘。
			b=p1->exp+x->exp;                     //多项是相乘，指数相加。
            p=attach(a,b,p);
			x=x->link;                            //找到p2的下一项
		}  
	
	}

	p->link=NULL;
		p=q->link;                                //找到记录结果的第一项结果的项，是为最终结果的表头节点。
		delete q;
		return p;
}

polypointer ch(polypointer a,polypointer b,polypointer c)//多项式a除以多项式b，商存于链表c中，返回余数
{
	polypointer p1,p2,p3,p;
	int p_exp;
	float p_coef;

	p1=a;
	p2=b;
	p=c;

	while(p1!=NULL)
	{
      if(p1->exp >= p2->exp)                              //验证是否满足多项式除法的条件
	  {
		  p_coef=p1->coef/p2->coef;                       //除法运算，系数相除。
		  p_exp=p1->exp-p2->exp;                          //除法运算，指数相减。
		  p=attach(p_coef,p_exp,p);                       //将结果保存到新的节点。
		                                                  //被减式减去除式与商式的积，得到余式。
		  p3=fmuls(p,p2);                                 
		  p1=pmins(p1,p3);                                
          del(p3);
	  }
	  else 
	  {p->link=NULL;
		  return p1;                                       //不满足条件，结束运算，返回当前结果。
	  }
	  p1=p1->link;
	}                 
	p->link=NULL;
	return p1;

}