polyn.cpp

可以实现两多项式的加减乘除及微积分运算

#include"Polyn.h"


//          _________
//_________|转化链表|__________
Linklist string_change_link(char *start)
{	Linklist head,pnew,help1,help2;
	int i=0,j=0,k,sum=0,flag=1;
	head=(Linklist)malloc(sizeof(Node));
	if(head==NULL)			exit(OVERFLOW);
	head->next=NULL;
	
	while(start[i]!='\0')
	{	if(start[i]=='-'||start[i]=='+'||start[i]=='x'||start[i]=='#')
		{	if(start[j]=='-')		flag=0;
   			if(start[j]=='+')		flag=1;

			if(start[j]=='-'||start[j]=='+'||j==0)
			{	if(i==0)	
				{	i++;
					continue;
				}
				pnew=(Linklist)malloc(sizeof(Node));
				if(!pnew)			exit(OVERFLOW);
				pnew->coef_denominator=1;
				pnew->exp=-1;
				pnew->next=NULL;
			}
		
			//计算系数和指数
			if(i-j==1)
			{	if(start[j]>'1'&&start[j]<='9')		sum=start[j]-'0';
				else	sum=1;
			}
			else if(j==0&&start[j]>='1'&&start[j]<='9')
					for(k=j;k<i;k++)
						sum=sum*10+start[k]-'0';
			else for(k=j+1;k<i;k++)
  					sum=sum*10+start[k]-'0';
			if(flag==0)			sum=-sum;

			
			//将计算出的数判断是系数还是指数后存入链表
			if(j==0||start[j]=='+'||start[j]=='-')
			{	pnew->coef_numerator=sum;
				if(start[i]=='+'||start[i]=='-'||start[i]=='#')//常数项
					pnew->exp=0;
			}//系数
			if(start[j]=='x')
			{	if(j==0)	pnew->coef_numerator=1;
				pnew->exp=sum;
			}//指数

			if(pnew->exp!=-1)	   //如果指数被赋值，插入链表
			{	if(head->next==NULL)	head->next=pnew;
				else
				{	help2=head;
					help1=head->next;
					while(help1!=NULL)
					{	if(help1->exp<pnew->exp)
						{	pnew->next=help1;
							help2->next=pnew;
							break;
						}
						else if(help1->exp>pnew->exp)
						{	help2=help1;
							help1=help1->next;
						}
						else
						{	help1->coef_numerator+=pnew->coef_numerator;
							if(help1->coef_numerator==0)
							{	help2->next=help1->next;
								free(help1);
							}
							free(pnew);
							break;
						}
					}
					if(help1==NULL)		help2->next=pnew;
				}
			}

			flag=1;
   			sum=0;
			j=i;
		}			//end if 
		i++;
	}			//end while

	return(head);
}


//          ____
//_________|约分|__________
void reduction(int *numerator,int *denominator)
{	int i,m,n;
	m=*denominator;		//分母
	n=*numerator;		//分子
	if(m%n==0||n%m==0)
	{	i=abs(m)>abs(n)?abs(n):abs(m);
		m/=i;
		n/=i;
	}
	else
		for(i=2;i<=m/2&&i<=n/2;i++)
			if(m%i==0&&n%i==0)
			{	m/=i;
				n/=i;
				i=1;
			}
	*denominator=m;
	*numerator=n;	
}



//          ____
//_________|打印|__________
void print(Linklist head)
{	Node *p;
	p=head->next;
    if(p==NULL)			return;
  	else if(p->coef_denominator==1)			//第一项为整数系数
		{	if(p->exp==0)					printf("%d",p->coef_numerator);
			else if(p->exp==1)		
				{	if(p->coef_numerator==1)	printf("x");
					else						printf("%dx",p->coef_numerator);
				}
			else if(p->coef_numerator==1)	printf("x^%d",p->exp);
			else if(p->coef_numerator==-1)	printf("-x^%d",p->exp);
			else							printf("%dx^%d",p->coef_numerator,p->exp);
			p=p->next;
		}
	else			//第一项为分数系数
	{	if(p->exp==0)			printf("%d/%d",p->coef_numerator,p->coef_denominator);
		else if(p->exp==1)
			{	if(p->coef_numerator>0)
					printf("(%d/%d)x",p->coef_numerator,p->coef_denominator);
				else
					printf("-(%d/%d)x",-p->coef_numerator,p->coef_denominator);
			}
		else 
		{	if(p->coef_numerator>0)
				printf("(%d/%d)x^%d",p->coef_numerator,p->coef_denominator,p->exp);
			else
				printf("-(%d/%d)x^%d",-p->coef_numerator,p->coef_denominator,p->exp);
		}
		p=p->next;
	}


	while(p!=NULL)
	{	if(p->coef_denominator==1)			//整数系数项
		{	if(p->exp==0)
			{	if(p->coef_numerator==0)	continue;
				else if(p->coef_numerator<0)	printf("%d",p->coef_numerator);
				else				printf("+%d",p->coef_numerator);				
			}
			else if(p->exp==1)
				{	if(p->coef_numerator>0)
					{	if(p->coef_numerator==1)		printf("+x");
						else				printf("+%dx",p->coef_numerator);
					}
					else if(p->exp==-1)		printf("-x");
					else					printf("%dx",p->coef_numerator);
				}
			else if(p->coef_numerator==1)
					printf("+x^%d",p->exp);
			else if(p->coef_numerator==-1)
					printf("-x^%d",p->exp);
			else if(p->coef_numerator>0)
					printf("+%dx^%d",p->coef_numerator,p->exp);
			else	printf("%dx^%d",p->coef_numerator,p->exp);	
			p=p->next;
		}		//end if(coef_denominator==1)

		else					//分数系数项		
		{	if(p->exp==0)
			{	if(p->coef_numerator==0)	 continue;
				else if(p->coef_numerator<0) printf("%d/%d",p->coef_numerator,p->coef_denominator);
				else						 printf("+%d/%d",p->coef_numerator,p->coef_denominator);			
			}
			else if(p->exp==1)
			{	if(p->coef_numerator>0)	
					printf("+(%d/%d)x",p->coef_numerator,p->coef_denominator);
				else 
					printf("-(%d/%d)x",-p->coef_numerator,p->coef_denominator);
			}
			else if(p->coef_numerator>0)
					printf("+(%d/%d)x^%d",p->coef_numerator,p->coef_denominator,p->exp);
			else	printf("-(%d/%d)x^%d",-p->coef_numerator,p->coef_denominator,p->exp);	
			p=p->next;
		}		//end if(coef_denominator!=1) 
	}	//end while
	printf("\n");
}



//          __________
//_________|合并(加法)|__________
Linklist unite(Linklist head,Linklist head1)
{	Linklist p,q,pahead;
	pahead=head;
	p=head->next;
    q=head1->next;
	while(p!=NULL&&q!=NULL)
	{	if(p->exp>q->exp)			//head链里指数比head1大，向后移
		{	pahead=p;
			p=p->next;
			continue;
		}
		else if(p->exp<q->exp)		//head链里指数比head1小，将head1里该项插入head
		{	pahead->next=q;	
			pahead=q;
			q=q->next;
			head1->next=q;
			pahead->next=p;
		}
		else			//指数相同
		{	if(p->coef_numerator*q->coef_numerator==-p->coef_denominator*q->coef_denominator)
			{	pahead->next=p->next;
				free(p);
				p=pahead->next;
				head1->next=q->next;
				free(q);
				q=head1->next;
			}		//系数互为相反数，刚好可以消掉，删除结点
			else	//否则，合并
			{	p->coef_numerator*=q->coef_denominator;
				q->coef_numerator*=p->coef_denominator;
				p->coef_denominator*=q->coef_denominator;
				p->coef_numerator+=q->coef_numerator;
				if(p->coef_denominator!=1)
					reduction(&p->coef_numerator,&p->coef_denominator);
				pahead=p;
				p=p->next;
				head1->next=q->next;
				free(q);
				q=head1->next;	
			}
		}
	}
	if(p==NULL)			pahead->next=q;
	free(head1);
	
	return head;
}



//          __________
//_________|合并(减法)|__________
Node *_unite(Linklist head,Linklist head1)
{	Linklist p;
	for(p=head1->next;p!=NULL;p=p->next)
		p->coef_numerator*=-1;
	//head1系数变反后跟head做加法
	head=unite(head,head1);
	return(head);
}


//          ____
//_________|乘法|__________
Linklist multiply(Linklist head,Linklist head1)
{	Linklist temp1,temp2,point,point1,pahead,pnew;
	//建两个临时链表存每次乘后的临时多项式
	temp1=(Linklist)malloc(sizeof(Node));
	if(temp1==NULL)			exit(OVERFLOW);
	temp1->next=NULL;
	pahead=temp1;
	point1=head1->next;
	for(point=head->next;point!=NULL;point=point->next)
	{	pnew=(Linklist)malloc(sizeof(Node));
		if(pnew==NULL)			exit(OVERFLOW);
		pnew->coef_denominator=1;
		pnew->next=NULL;
		pnew->coef_numerator=point->coef_numerator*point1->coef_numerator;
		pnew->coef_denominator=point->coef_denominator*point1->coef_denominator;
		pnew->exp=point->exp+point1->exp;
		pahead->next=pnew;
		pahead=pahead->next;					
	}
	head1->next=point1->next;
	free(point1);
	//head1第一项与head各项相乘作为基本多项式，与后面的做加运算

	
	//head1每一项与head各项相乘然后与temp1相加			
	for(point1=head1->next;point1!=NULL;point1=point1->next)
	{	temp2=(Linklist)malloc(sizeof(Node));
		if(temp2==NULL)			exit(OVERFLOW);
		temp2->next=NULL;
		pahead=temp2;
		for(point=head->next;point!=NULL;point=point->next)
		{	pnew=(Linklist)malloc(sizeof(Node));
			if(pnew==NULL)			exit(OVERFLOW);
			pnew->coef_denominator=1;
			pnew->next=NULL;
			pnew->coef_numerator=point->coef_numerator*point1->coef_numerator;
			pnew->coef_denominator=point->coef_denominator*point1->coef_denominator;
			pnew->exp=point->exp+point1->exp;
			pahead->next=pnew;
			pahead=pahead->next;					
		}
		temp1=unite(temp1,temp2);
	}

	return(temp1);
}



//          ____
//_________|除法|__________
void division(Linklist head,Linklist head1)
{	Linklist quotient;			//商式
	Linklist temp,point,point1,pahead,pnew;

	quotient=(Linklist)malloc(sizeof(Node));
	if(quotient==NULL)			exit(OVERFLOW);
	quotient->next=NULL;


	for(point=head->next;point!=NULL;point=head->next)
	{	if(point->exp<head1->next->exp)		break;
		//如果被除式最高项指数比除式低，退出循环

		pnew=(Linklist)malloc(sizeof(Node));
		if(pnew==NULL)			exit(OVERFLOW);
		pnew->coef_denominator=1;
		pnew->next=NULL;
		if(point->coef_denominator==1&&point->coef_numerator%head1->next->coef_numerator==0)
			pnew->coef_numerator=point->coef_numerator/head1->next->coef_numerator;
		else
		{	pnew->coef_numerator=point->coef_numerator*head1->next->coef_denominator;
			pnew->coef_denominator=point->coef_denominator*head1->next->coef_numerator;
			reduction(&pnew->coef_numerator,&pnew->coef_denominator);
			if(pnew->coef_denominator<0)
			{	pnew->coef_denominator*=-1;
				pnew->coef_numerator*=-1;
			}
		}
		pnew->exp=point->exp-head1->next->exp;
		//计算商式中新项


		head->next=point->next;
		free(point);//将最高项释放

		for(point=quotient;point->next!=NULL;point=point->next);
		point->next=pnew;			//链入商式

		//新项与除式乘后成为被减式(temp)
		temp=(Linklist)malloc(sizeof(Node));
		if(temp==NULL)			exit(OVERFLOW);
		pahead=temp;
		for(point1=head1->next->next;point1!=NULL;point1=point1->next)
		{	pnew=(Linklist)malloc(sizeof(Node));
			if(pnew==NULL)			exit(OVERFLOW);
			pnew->next=NULL;
			pnew->coef_numerator=point->next->coef_numerator*point1->coef_numerator;
			pnew->coef_denominator=point->next->coef_denominator*point1->coef_denominator;
			reduction(&pnew->coef_numerator,&pnew->coef_denominator);
			//系数(分母、分子约分)
			pnew->exp=point->next->exp+point1->exp;//指数
			pahead->next=pnew;
			pahead=pahead->next;					
		}
		head=_unite(head,temp);//合并被除式和被减式
	}			//end for
	//head剩余就是余式
	if(quotient->next==NULL)		printf("商式是:0\n");
	else
	{	printf("商式是:");
		print(quotient);
	}
	printf("余式是:");
	print(head);	
}