polynomial.cpp

运用链表来操作多项式,实现多项式加减乘的功能

// CPolynomial.cpp: implementation of the CPolynomial class.
//
//////////////////////////////////////////////////////////////////////

#include "Polynomial.h"
#include <string.h>
#include "stdio.h"
#include "stdlib.h"
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
class string;
CPolynomial::CPolynomial()
{
	nTerms=0;
	nNodes=0;
}

CPolynomial::~CPolynomial()
{

}

void CPolynomial::CreatePoly(Poly &p)
{
	Poly pHead;
	Poly p1,p2;
	int n=1;
	p1=p2=(Poly)malloc(sizeof(Poly));
//	scanf("%ld%f",&p1->data->coefficent,&p1->data->exp);
	cout<<"请输入多项式的第1项的系数：";
	cin>>p1->data.coefficent;
	cout<<"请输入多项式的第1项的指数：";
	cin>>p1->data.exp;
	cout<<endl;
	pHead=NULL;
	while(p1->data.coefficent!=0 || p1->data.exp!=0)
	{
		n+=1;
		if(n==2)
			pHead=p1;
		else
			p2->next=p1;
		p2=p1;
		p1=(Poly)malloc(sizeof(Poly));
//		scanf("%ld%f",&p1->data->coefficent,&p1->data->exp);
//		cin>>p1->data.coefficent>>p1->data.exp;
		cout<<"请输入多项式的第"<<n<<"项的系数：";
		cin>>p1->data.coefficent;
		cout<<"请输入多项式的第"<<n<<"项的指数：";
		cin>>p1->data.exp;
		cout<<endl;
	}
	p2->next=NULL;
	p=pHead;
	this->nNodes=n-1;
}

void CPolynomial::DestroyPoly(Poly &p)
{

}

//将多项式转换为字符串
char* CPolynomial::PolyToSymbol(Poly p)
{
	bool bIsVanish=true;
	//该多项式为0
	if(!p)
	{
		return "p(x)=0";
	}

	char *pStr,*pTemp;
	char *pCoef,*pExp;
	bool bFirst=true;
	pCoef=(char*)malloc(10);
	pExp=(char*)malloc(10);
	pStr=(char*)malloc(100);
	pTemp=(char*)malloc(100);

	while(p)
	{
		if(p->data.coefficent!=0)
		{
			bIsVanish=false;

			itoa(p->data.coefficent,pCoef,10);
			itoa(p->data.exp,pExp,10);
			if(bFirst)//如果是第一项
			{
				bFirst=false;
				if(p->data.coefficent==1)//如果系数等于1
				{
					if(p->data.exp==1)
						*pCoef='x';
					else
						if(p->data.exp>1)
							strcat(strcat("x","^"),pExp);
				}
				else
				{
					if(p->data.exp==1)
						strcat(pCoef,"x");
					else
						if(p->data.exp>1)
							strcat(strcat(strcat(pCoef,"x"),"^"),pExp);
				}
				strcpy(pStr,pCoef);
			}
			else
			{
				if(p->data.coefficent>0)//如果系数大于0
					pStr=strcat(pStr,"+");

				if(p->data.coefficent==1)//如果系数等于1
				{
					if(p->data.exp==0)//如果指数等于0
						pStr=strcat(pStr,pCoef);
					else
						if(p->data.exp==1)//如果指数等于1
							pStr=strcat(pStr,"x");
						else
	//						strcat(pStr,strcat(strcat("x","^"),pExp));
							strcat(strcat(pStr,"x^"),pExp);
				}
				else
				{
					if(p->data.exp==0)//如果指数等于0
						pStr=strcat(pStr,pCoef);
					else
						if(p->data.exp==1)//如果指数等于1
							pStr=strcat(pStr,strcat(pCoef,"x"));
						else
							strcat(pStr,strcat(strcat(strcat(pCoef,"x"),"^"),pExp));
				}
			}
		}
		
		p=p->next;
	}

	if(bIsVanish)
	{
		return "p(x)=0";
	}

	return pStr;
}


//多项式相加
void CPolynomial::AddPoly(Poly& pa, Poly& pb)
{
	Poly qa=pa;  //用指针qa扫描多项式pa
	Poly qb=pb;  //用指针qb扫描多项式pb
	Poly temp;   //临时指针

	Term ta,tb;
	float sum=0;
	while(qa&&qb)
	{
		ta=GetCurElem(qa);
		tb=GetCurElem(qb);
		switch(CmpTerm(ta,tb))
		{
		case -1:
			qa=NextPos(qa);
			break;
		case 0:
			sum=ta.coefficent+tb.coefficent;
//			if(sum!=0)
			{
				SetCurElem(qa,sum);
				qa=NextPos(qa);
				DelCurNode(qb);
			}
/*			else
			{
				temp=pa;
				pa=qa;
				DelCurNode(pa);
				DelCurNode(qa);
				pa=temp;
				DelCurNode(qb);*/
//				FreeNode(qa);
//				FreeNode(qb);
//			}
			break;
		case 1:
			//保存qa
			temp=qa;
			//是qa指向qb
			qa->next=qb;
			//使qa后移一位
			qa=NextPos(qa);
			qb=qa;
			//使qa还原
			qa=temp;
			break;
		}
	}
	if(!IsListEmpty(qb))
		Append(pa,qb);
}

void CPolynomial::SubtractPoly(Poly& pa, Poly& pb)
{
	Poly temp;
	temp=pb;
	do
	{
		pb->data.coefficent=-pb->data.coefficent;
		pb=pb->next;
	}
	while(pb);
	this->AddPoly(pa,temp);
}

//多项式相乘
void CPolynomial::MultiplyPoly(Poly& pa, Poly& pb)
{
	//只要一个为0，就返回0
	if(!pa||!pb)
	{
		pa=NULL;
		return;
	}

	Poly temp;
	Poly pHead;
	Poly p1;
	Poly p=NULL;      //存放总和
	int n=0;


	//保存多项式pa到p1
	p1=this->CopyPoly(pa);
	//保存其指针
	pHead=p1;

	temp=pa;
	do
	{
		n++;
		//计算A(x)*bi*x^ei
		do
		{
			temp->data.coefficent=pb->data.coefficent*p1->data.coefficent;
			temp->data.exp=pb->data.exp+p1->data.exp;
			p1=p1->next;
			temp=temp->next;
		}
		while(p1&&temp);
		//恢复指针
		p1=pHead;
		temp=pa;
		if(n==1)
			p=this->CopyPoly(temp);
		else
			this->AddPoly(p,temp);
		pb=pb->next;
	}
	while(pb);

	//保存总和
	pa=p;
}

int CPolynomial::CmpTerm(Term ta, Term tb)
{
	if(ta.exp<tb.exp)
		return -1;
	
	if(ta.exp==tb.exp)
		return 0;

	return 1;
}

Poly CPolynomial::GetHead(Poly p)
{
	return p;
}

Poly CPolynomial::NextPos(Poly p)
{
	return p->next;
}

Term CPolynomial::GetCurElem(Poly p)
{
	return p->data;
}

void CPolynomial::SetCurElem(Poly& p, float coef)
{
	p->data.coefficent=coef;
}

void CPolynomial::FreeNode(Poly p)
{
	free(p);
}

void CPolynomial::DelCurNode(Poly& p)
{
	Poly temp;
	temp=p;
	if(p->next)
		p=p->next;
	else
		p=NULL;
//	free(temp);
}

bool CPolynomial::IsListEmpty(Poly p)
{
	return !p?true:false;
}

void CPolynomial::InsNode(Poly &pa, Poly &pb)
{
}

void CPolynomial::Append(Poly &pa, Poly &pb)
{
	Poly temp;
	temp=pa;
	if(!pa)
	{
		pa=pb;
		return;
	}

	while(pa->next)
		pa=pa->next;
	pa->next=pb;
	pa=temp;
}


//化简多项式
void CPolynomial::ToBeEasy(Poly &p)
{
	Poly pHead;
	Poly temp,temp1,temp2;
	Poly p2=NULL;
	Term t;
	float sum=0;
	Term ta,tb;
	int nLen,nSteps=0;
	
	if(!p||!p->next)
		return;

	pHead=p;

	nLen=this->GetPolyLen(p);

	for(int i=1;i<=nLen;i++)
	{
		nSteps=0;
		temp=p;
		p2=p+i;
		while(temp && temp->next && nLen-i+1-nSteps)
		{
			nSteps++;
			temp1=temp;
			temp2=temp->next;
			ta=temp1->data;
			tb=temp2->data;
			
			switch(CmpTerm(ta,tb))
			{
			case 0:
				sum=ta.coefficent+tb.coefficent;
				SetCurElem(temp1,sum);
				SetCurElem(temp2,0);
				//	DelCurNode(temp2);
				break;
			case 1:
				t=ta;
				temp1->data=tb;
				temp2->data=t;
				break;
			default:
				break;
			}
			temp=temp->next;
		}
	}

	p=pHead;
}

int CPolynomial::GetPolyLen(Poly p)
{
	int n=0;
	while(p)
	{
		n+=1;
		p=p->next;
	}
	return n;
}

Poly CPolynomial::CopyPoly(Poly p)
{
	Poly pResult,temp;
	Poly pHead;
	int n=0;

	if(!p)
		return NULL;

	while(p)
	{
		pResult=(Poly)malloc(sizeof(Poly));
		n+=1;

		if(n>1)
			temp->next=pResult;
		else
			//保存头指针
			pHead=pResult;

		temp=pResult;   

		pResult->data.coefficent=p->data.coefficent;
		pResult->data.exp=p->data.exp;

		p=p->next;
	}
	temp->next=NULL;
	//恢复指针
	pResult=pHead;

	return pResult;
}