polynomial.cpp

数据结构答案 金元平

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

#include "Polynomial.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Polynomial::Polynomial()
{
	newTerm(0, -1);
}

Polynomial::~Polynomial()
{

}

istream& operator>>(istream& is, Polynomial& p)
{
	int n;
	is>>n;

	int c;
	int e;
	for (int i=0; i<n; i++)
	{
		is>>c>>e;
		p.newTerm(c,e);
	}

	return is;
}

ostream& operator<<(ostream& os, const Polynomial& p)
{
	CircListIterator<Term> pIter(p.poly);
	Term* pt = pIter.first();
	int termCount = 0;
	while (pIter.notEnd())
	{	
		pt = pIter.next();
		termCount++;
	}
	os<<termCount<<' '; 

	pt = pIter.first();
	while (pIter.notEnd())
	{	
		pt = pIter.next();
		os<<pt->coef<<' '<<pt->exp<<' ';
	}		
	return os;
}

Polynomial::Polynomial(const Polynomial& p)
{
	newTerm(0, -1);
	CircListIterator<Term> pIter(p.poly);
	Term* pt = pIter.first();
	while (pIter.notEnd())
	{	
		pt = pIter.next();
		newTerm(pt->coef,pt->exp);
	}
}

const Polynomial& Polynomial::operator=(const Polynomial &p)
{
	CircListIterator<Term> pIter(p.poly);
	Term* pt = pIter.first();	
	while (pIter.notEnd())
	{	
		pt = pIter.next();
		newTerm(pt->coef,pt->exp);
	}
	
	return *this;
}

Polynomial Polynomial::operator+(const Polynomial &P)
{
	Term* p;
	Term* q;
	CircListIterator<Term> PIter(P.poly);
	CircListIterator<Term> QIter(poly);

	Polynomial R;
	p = PIter.next();
	q = QIter.next();

	while (p->exp!=-1 ||q->exp!=-1)
	{
		if (p->exp==q->exp)
		{
			int sum = p->coef+q->coef;
			if(sum)
				R.newTerm(sum,p->exp);
			p = PIter.next();
			q = QIter.next();
		}
		else if (p->exp<q->exp)
		{
			R.newTerm(q->coef, q->exp);
			q = QIter.next();
		}
		else
		{
			R.newTerm(p->coef, p->exp);
			p = PIter.next();
		}
	}

	return R;
}

Polynomial Polynomial::operator-(const Polynomial &p)
{
	Polynomial minusP;
	CircListIterator<Term> pIter(p.poly);
	Term* pt = pIter.first();
	
	while (pIter.notEnd())
	{	
		pt = pIter.next();
		minusP.newTerm(-pt->coef,pt->exp);
	}

	return *this+minusP;
}

Polynomial Polynomial::operator*(const Polynomial &P)
{
	Term* p;
	Term* q;
	CircListIterator<Term> PIter(P.poly);
	CircListIterator<Term> QIter(poly);

	p = PIter.next();
	q = QIter.next();

	int highest = p->exp+q->exp;
	float* c = new float[p->exp+q->exp+1];
	for (int i=0; i<=p->exp+q->exp; i++)
	{
		c[i]=0;
	}

	p = PIter.first();
	while (PIter.notEnd())
	{		
		p = PIter.next();
		q = QIter.first();
		while (QIter.notEnd())
		{
			q = QIter.next();
			c[p->exp+q->exp] += p->coef*q->coef;
		}
	}

	Polynomial R;
	for (int e = highest; e>=0; e--)
		if (c[e])
			R.newTerm(c[e], e);

	delete []c;
	return R;
}

float Polynomial::evaluate(float x)
{
	float sum = 0;
	CircListIterator<Term> pIter(poly);
	Term* pt = pIter.first();	
	while (pIter.notEnd())
	{	
		pt = pIter.next();
		sum += pow(pt->coef, pt->exp);
	} 		
	return sum;
}

void Polynomial::newTerm(int c, int e)
{
	Term t(c,e);
	ListNode<Term>* pNode = new ListNode<Term>(t);
	poly.InsertTail(pNode);
}