polynomial.cpp

用循环链表实现的多项式 包括 运算符及io重载

#include "Polynomial.h"
#include <iostream>
using namespace std;

Node * CircList::av = 0;

CircList::CircList()
{
	Node *head = new Node();
	first = last = head;
	last->link = first;
}

CircList::~CircList()
{
	if(first)
	{
		Node *second = first->link;
		first->link = av;
		av = second;
		first = 0;
	}//是否要对last操作?av呢?
}

Node *CircList::GetNode()
{
	Node *x = 0;
	if(!av)
		x = new Node();
	else
	{
		x = av;
		av = av->link;
	}
	return x;
}

void CircList::RetNode(Node *x)
{
	x->link = av;
	av = x;
}

void CircList::InsertFront(Node *x)
{
	if(!last->link)
	{
		first = last = x;
		last->link = first;
	}
	else
	{
		x->link = last->link;
		first = x;
		last->link = first;
	}
}

void CircList::InsertRear(Node *x)
{
	if(!last->link)
	{
		first = last = x;
		last->link = first;
	}
	else
	{
		x->link = last->link;
		last->link = x;
		last = x;
	}
}

void CircList::DeleteFront()
{
	if(!last->link)
	{}//empty body
	else
	{//at least one node (except the head node) exists
		Node *x = first->link;//it's the first node after the head node that is to be deleted
		if(last==x)//there are only two nodes
		{
			first->link = first;//i.e. first->link = first->link->link;
			last = first;
		}
		else
			first->link = first->link->link;
		RetNode(x);//returning a node
	}
}

void CircList::DeleteRear()
{
	if(!last->link)
	{}//empty body
	else
	{//at least one node (except the head node) exists
		Node *x = last;//it's the first node after the head node that is to be deleted
		if(first->link==x)//there are only two nodes
		{
			first->link = first;
			last = first;
		}
		else
		{
			Node *prev = last;
			while(prev->link!=last)
				prev = prev->link;//last points to the previous node before last node
			prev->link = last->link;
			last = prev;
		}
		RetNode(x);//returning a node
	}
}

void CircList::Delete(Node *x)
{	
	if(x==first)
	{}//empty body
	else if(x==first->link)
		DeleteFront();
	else if(x==last)
		DeleteRear();
	else
	{
		Node *prev = x;
		while(prev->link!=x)
			prev = prev->link;
		prev->link = x->link;
		RetNode(x);
	}
}

Polynomial::Polynomial(const int t)
{
	Node *temp = 0;
	Terms = 0;//initialize...very important
	for(int i=0; i<t; i++)
	{
		temp = new Node();
		AddTerm(temp);
	}
}

Polynomial::Polynomial(const Polynomial&p)
{
	Copy(p);
}

const Polynomial &Polynomial::operator=(const Polynomial &p)
{
	if(&p!=this)
	{
		while(cl.GetFirst()!=(*cl.GetFirst()).GetLink())
			DeleteTerm();
		Copy(p);
	}

	return *this;
}

Polynomial::~Polynomial()
{
	cl.~CircList();
}

istream & operator>>(istream &input,Polynomial &p)
{
	cout<<"for input, the form: c1,e1,c2,e2,c3,e3...,cn,en,"
	    <<"\nwhere ei represents an exponent and ci represents a coefficient,"
		<<"\nThe exponents are in decreasing order-i.e.,e1>e2>e3>...>en\n";
	Node *temp = (*p.cl.GetFirst()).GetLink();
	for(int i=1; i<=p.GetTerms(); i++)
	{		
		cout<<"c"<<i<<": ";
		input>>(*temp).GetCoef();
		cout<<"e"<<i<<": ";
		input>>(*temp).GetExp();
		temp = ((*temp).GetLink());
	}

	return input;
}

ostream & operator<<(ostream &output,const Polynomial &p)
{
	Node *temp = (*p.cl.GetFirst()).GetLink();
	output<<(*temp).GetCoef()<<"x^"
		  <<(*temp).GetExp();
	temp = ((*temp).GetLink());
	for(int i=2; i<p.GetTerms(); i++)
	{		
		if((*temp).GetCoef()>0)
			output<<"+";
		output<<(*temp).GetCoef()<<"x^"
			  <<(*temp).GetExp();/*//need improving*/
		temp = ((*temp).GetLink());
	}	
	if(p.GetTerms()>=2)
	{
		if((*temp).GetCoef()>0)
			output<<"+";
		output<<(*temp).GetCoef()<<"x^"
			  <<(*temp).GetExp();
	}
	output<<endl;
	return output;
}

Polynomial operator+(const Polynomial &a,const Polynomial &b)
{
	Node *p;
	Node *q;
	Node *temp;
	Polynomial c;
	float x;
	p = (*a.cl.GetFirst()).GetLink();
	q = (*b.cl.GetFirst()).GetLink();//get first node(not the head node) in a and b
	while(p!=a.cl.GetFirst()&&q!=b.cl.GetFirst())
	{
		switch(c.Compare((*p).GetExp(),(*q).GetExp()))
		{
		case '=':
			x = (*p).GetCoef()+(*q).GetCoef();
			temp  = new Node(x,(*p).GetExp());
			if(x)
				c.AddTerm(temp);
			p = (*p).GetLink();
			q = (*q).GetLink();
			break;
		case '<':
			temp = new Node((*q).GetCoef(),(*q).GetExp());
			c.AddTerm(temp);
			q = (*q).GetLink();//next node of b
			break;
		case '>':
			temp = new Node((*p).GetCoef(),(*p).GetExp());
			c.AddTerm(temp);
			p = (*p).GetLink();//next node of a
			break;
		}
	}

	while(p!=a.cl.GetFirst())//copy rest of a
	{
		temp = new Node((*p).GetCoef(),(*p).GetExp());
		c.AddTerm(temp);
		p = (*p).GetLink();
	}

	while(q!=b.cl.GetFirst())//copy rest of b
	{
		temp = new Node((*q).GetCoef(),(*q).GetExp());
		c.AddTerm(temp);
		q = (*q).GetLink();
	}

	return c;
}

Polynomial operator-(const Polynomial &a,const Polynomial &b)
{
	Node *p;
	Node *q;
	Node *temp;
	Polynomial c;
	float x;
	p = (*a.cl.GetFirst()).GetLink();
	q = (*b.cl.GetFirst()).GetLink();//get first node(not the head node) in a and b
	while(p!=a.cl.GetFirst()&&q!=b.cl.GetFirst())
	{
		switch(c.Compare((*p).GetExp(),(*q).GetExp()))
		{
		case '=':
			x = (*p).GetCoef()-(*q).GetCoef();
			temp  = new Node(x,(*p).GetExp());
			if(x)
				c.AddTerm(temp);
			p = (*p).GetLink();
			q = (*q).GetLink();
			break;
		case '<':
			temp = new Node(-(*q).GetCoef(),(*q).GetExp());
			c.AddTerm(temp);
			q = (*q).GetLink();//next node of b
			break;
		case '>':
			temp = new Node((*p).GetCoef(),(*p).GetExp());
			c.AddTerm(temp);
			p = (*p).GetLink();//next node of a
			break;
		}
	}

	while(p!=a.cl.GetFirst())//copy rest of a
	{
		temp = new Node((*p).GetCoef(),(*p).GetExp());
		c.AddTerm(temp);
		p = (*p).GetLink();
	}

	while(q!=b.cl.GetFirst())//copy rest of b
	{
		temp = new Node(-(*q).GetCoef(),(*q).GetExp());
		c.AddTerm(temp);
		q = (*q).GetLink();
	}

	return c;
}

Polynomial operator*(const Polynomial &a,const Polynomial &b)
{
	Polynomial *c;
	int min = a.GetTerms()<b.GetTerms()?a.GetTerms():b.GetTerms();
	c = new Polynomial[min+1];
	Node *p;
	Node *q;
	Node *temp;
	float x;
	int y;
	p = (*a.cl.GetFirst()).GetLink();
	q = (*b.cl.GetFirst()).GetLink();//get first node(not the head node) in a and b
	if(a.GetTerms()<=b.GetTerms())
	{
		for(int i=1; i<=min&&p!=a.cl.GetFirst(); i++)
		{
			while(q!=b.cl.GetFirst())
			{
				x = (*p).GetCoef()*(*q).GetCoef();
				y = (*p).GetExp()+(*q).GetExp();
				temp  = new Node(x,y);
				if(x)
					c[i].AddTerm(temp);
				q = (*q).GetLink();
			}
			p = (*p).GetLink();
		q = (*b.cl.GetFirst()).GetLink();
		}
	}

	else
	{
		for(int i=1; i<=min&&p!=b.cl.GetFirst(); i++)
		{
			while(p!=a.cl.GetFirst())
			{
				x = (*q).GetCoef()*(*p).GetCoef();
				y = (*q).GetExp()+(*p).GetExp();
				temp  = new Node(x,y);
				if(x)
					c[i].AddTerm(temp);
				p = (*p).GetLink();
			}
			q = (*q).GetLink();
		p = (*a.cl.GetFirst()).GetLink();
		}
	}

	for(int i=1; i<=min; i++)
		c[0] = c[0] + c[i];

	return c[0];
}

void Polynomial::AddTerm(Node *x)
{
	cl.InsertRear(x);
	Terms++;
}

void Polynomial::DeleteTerm()
{
	cl.DeleteRear();
	Terms--;
}

float Polynomial::Evaluate(float x)
{
	float sum = 0;
	Node *temp=(*(cl.GetFirst())).GetLink();
	for(int i=0; i<GetTerms(); i++)
	{
		sum+=Calculate(x,(*temp).GetCoef(),(*temp).GetExp());
		temp = (*temp).GetLink();
	}
	return sum;	
}

void Polynomial::Copy(const Polynomial &p)
{
	Terms = 0;
	Node *x=(*(p.GetCl().GetFirst())).GetLink();
	Node *temp = 0;
	for(int i=0; i<p.GetTerms(); i++)
	{
		temp = new Node((*x).GetCoef(),(*x).GetExp());
		AddTerm(temp);
		x = (*x).GetLink();
	}
}

float Polynomial::Calculate(float x, float c, int e)
{
	float sum = 1;
	for(int i=0; i<e; i++)
		sum *= x;
	return c*sum;
}

char Polynomial::Compare(int x, int y)
{
	if(x==y)
		return '=';
	else if(x<y)
		return '<';
	else
		return '>';
}