poly.cpp

设计一个算法

#include<iostream.h>
#include<stdio.h>
#include<math.h>
#include<fstream.h>

ifstream in("input.txt");
ofstream out("output.txt");

template <class T>
class poly;
template <class T>
class Node{
	friend poly<T>;
public:
	T coef;
	T exp;
	Node<T> * next;
};
template<class T>
class poly{
private:
	Node<T> * head;
public:
	poly ();
	~poly();
	void input ( int ,istream & in);
	void output(ostream & out)const;
	Node<T> *gethead();
	T getcoef();
	T getexp();
	poly  dev  ( poly );
	poly  indev( poly );
	double val(double);
	poly & operator = ( poly &);
	poly & operator + ( poly &);
	poly & operator - ( poly &);
	poly & operator * ( poly &);
	poly & add(poly &,poly &);
	poly & sub(poly &,poly &);
	poly & mul(poly &,poly &);
};
template <class T>
poly<T>::poly()
{
	head=NULL;
}

template <class T>
poly<T>::~poly(){}

template <class T>
T poly<T>:: getcoef()
{
	return head->coef;
}

template <class T>
T poly<T>::getexp()
{
	return head->exp;
}

template <class T>
Node <T> * poly <T>:: gethead()
{
	return head;
}

template <class T>
void poly<T>::input(int n,istream & in)
{
	int i;
	Node<double> *p,*q,*np;
	for(i=0;i<n;i++)
	{
		np=new Node<double>;
		in>>np->coef>>np->exp;
		if(np->coef==0)
			continue;
		else{
			if(head==NULL)
			{
				head=np;
				head->next=NULL;
			}
			else
			{
				p=head;
				q=p;
				while(p!=NULL&&p->exp>np->exp)
				{
					q=p;
					p=p->next;
				}
				if(p==NULL)
				{
					q->next=np;
					np->next=p;
				}
				else if(p==head)
				{
					if(np->exp==p->exp)
						p->coef=p->coef+np->coef;
					else
					{
						p=head;
						head=np;
						np->next=p;
					}
				}
				else
				{
					if(np->exp==p->exp)
					{
						p->coef=p->coef+np->coef;
						delete np;
					}
					else
					{
						q->next=np;
						np->next=p;
					}
				}
			}
		}
	}
}

template <class T>
void poly<T>::output(ostream & out)const
{
	Node<double> *h;
	h=head;
	if(h)
	{
		if(h->coef==0)
			;
		else if(h->coef==1)
		{
			if(h->exp==1)
				out<<"x";
			else if(h->exp==0)
				out<<h->coef;
			else
				out<<"x^"<<h->exp;
		}
		else if(h->coef==-1)
		{
			if(h->exp==1)
				out<<"-x";
			else if(h->exp==0)
				out<<h->coef;
			else
				out<<"-x^"<<h->exp;
		}
		else
		{
			if(h->exp==1)
				out<<h->coef<<"x";
			else if(h->exp==0)
				out<<h->coef;
			else
				out<<h->coef<<"x^"<<h->exp;
		}
		h=h->next;
	}
	while(h)
	{
		if(h->coef==0)
			;
		else if(h->coef==1)
		{
			if(h->exp==1)
				out<<"+x";
			else if(h->exp==0)
				out<<"+"<<h->coef;
			else
				out<<"+x^"<<h->exp;
		}
		else if(h->coef==-1)
		{
			if(h->exp==1)
				out<<"-x";
			else if(h->exp==0)
				out<<h->coef;
			else
				out<<"-x^"<<h->exp;
		}
		else
		{
			if(h->exp==1)
			{
				if(h->coef<0)
					out<<h->coef<<"x";
				else
					out<<"+"<<h->coef<<"x";
			}
			else if(h->exp==0)
			{
				if(h->coef<0)
					out<<h->coef;
				else
					out<<"+"<<h->coef;
			}
			else
			{
				if(h->coef<0)
					out<<h->coef<<"x^"<<h->exp;
				else
					out<<"+"<<h->coef<<"x^"<<h->exp;
			}
		}
		h=h->next;
	}
	out<<endl;
}

template <class T>
poly<T> & poly <T>:: add(poly & pa,poly & pb)
{
	Node<double> *p,*q,*pre,*nq,*np,*h;
	double x;
	h=pa.gethead();
	q=pb.gethead();
	p=h;
	pre=p;
	while((p!=NULL)&&(q!=NULL))
		if(p->exp<q->exp)
		{
			if(p==h)
			{
				nq=q;
				q=q->next;
				nq->next =h;
				h=nq;
				p=h;
				pre=h;
				
			}
			else
			{
				nq=q;
				q=q->next;
				pre->next=nq;
				nq->next=p;
				pre=nq;
				
			}
		}
		else if(p->exp==q->exp)
		{
			x=p->coef+q->coef;
			if(x!=0)
			{
				p->coef=x;
				nq=q;
				q=q->next;
				pre=p;
				p=p->next;
				delete nq;
			}
			else
			{
				np=p;
				pre->next=p->next;
				p=p->next;
				delete(np);
				q=q->next ;
			}
		}
		else
		{
			pre=p;
			p=p->next ;
		}
		if(q!=NULL)
			pre->next=q;
		head=h;
		return pa;
}

template <class T>
poly <T>& poly <T>:: sub(poly & pa,poly & pb)
{
	Node<double> *p,*q,*pre,*nq,*np,*h;double x;
	p=pa.gethead();
	q=pb.gethead();
	while(p)
	{
		p->coef=-p->coef;
		p=p->next;
	}	
	h=pa.gethead();
	q=pb.gethead();
	p=h;
	pre=p;
	while((p!=NULL)&&(q!=NULL))
		if(p->exp<q->exp)
		{
			if(p==h)
			{
				nq=q;
				q=q->next;
				nq->next =h;
				h=nq;
				p=h;
				pre=h;
				
			}
			else
			{
				nq=q;
				q=q->next;
				pre->next=nq;
				nq->next=p;
				pre=nq;	
			}
		}
		else if(p->exp==q->exp)
		{
			x=p->coef+q->coef;
			if(x!=0)
			{
				p->coef=x;
				nq=q;
				q=q->next;
				pre=p;
				p=p->next;
				delete nq;
			}
			else
			{
				np=p;
				pre->next=p->next;
				p=p->next;
				delete(np);
				q=q->next ;
			}
		}
		else
		{
			pre=p;
			p=p->next ;
		}
		if(q!=NULL)
			pre->next=q;
		head=h;
		return pa;
}

template <class T>
poly<T> & poly<T> :: mul(poly & pa,poly & pb)
{
	Node <double>*p,*q,*r,*pre,*h,*np,*t;
	int flag;
	p=pa.gethead();
	q=pb.gethead();
	h=new  Node<double>;
	h->coef=pa.getcoef();
	h->exp=pa.getexp();
	flag=1;
	for(p;p!=NULL;p=p->next)
	{
		q=pb.gethead();
		for(q;q!=NULL;q=q->next)
		{
			np=new Node<double>;
			np->coef=p->coef*q->coef;
			np->exp=p->exp+q->exp;
			if(flag)
			{
				if(h->coef==p->coef&&h->exp==p->exp)
				{
					h=np;
					h->next=NULL;
					pre=h;
				}
				else
				{
					pre->next=np;
					pre=np;
					pre->next=NULL;
				}
			}
			else
			{
				pre=h;
				while(pre!=NULL&&pre->exp>np->exp)
				{
					r=pre;
					pre=pre->next;
				}
				if(pre==NULL)
				{
					r->next=np;
					np->next=pre;
				}
				else
				{
					if(pre->exp==np->exp)
					{
						pre->coef=pre->coef+np->coef;
						delete np;

						if(pre->coef==0)
						{
							t=pre;
							r->next=pre->next;
							delete t;
						}
					}
					else
					{
						r->next=np;
						np->next=pre;
					}
				}
			}

		}
		flag=0;
	}
		head=h;
		return pa;
}

template <class T>
poly<T> poly<T>::dev(poly b)
{
	Node<double> * h,* nh;
	h=b.gethead();
	nh=h;
	while(h)
	{
		h->coef=h->coef*h->exp;
		h->exp=h->exp-1;
		h=h->next;
	}
	head=nh;
	return  b;
}

template <class T>
poly<T> poly<T>::indev(poly c)
{
	Node<double> * h,* nh;
	h=c.gethead();
	nh=h;
	while(h)
	{
		h->exp=h->exp+1;
		h->coef=h->coef/h->exp;
		h=h->next;
	}
	head=nh;
	return  c;
}

template <class T>
double poly<T>::val(double x)
{
	Node<double> * h;
	double sum=0.0;
	h=head;
	while(h)
	{
		sum=sum+h->coef*pow(x,(double)(h->exp));
		h=h->next;
	}
	return sum;
}

template <class T>
poly<T> & poly<T>:: operator = (poly & x)
{
	Node<double> * p, *q=NULL,*h,*nh;
	nh=new Node<double>;
	nh=x.gethead();
	while(nh)
	{
		p=new Node<double>;
		p->coef=nh->coef;
		p->exp=nh->exp;
		if(q==NULL)
		{
			q=p;
			h=p;
		}
		else
		{
			q->next=p;
			q=p;
		}
		nh=nh->next;
	}
	p->next=NULL;
	head=h;
	return *this;
}

template <class T>
poly<T> & poly<T>:: operator + ( poly & x)
{
	*this=add(*this,x);
	return *this;
}

template <class T>
poly<T> & poly<T>:: operator - ( poly & x)
{
	*this=sub(*this,x);
	return *this;
}

template <class T>
poly<T> & poly<T>:: operator * ( poly & x)
{
	*this=mul(*this,x);
	return *this;
}

int main()
{
	int m,n,i,num=0;
	char *ch,st;
	double result,value;
	poly<double> b,c;
	poly <double> *a;
	in>>m;
		ch=new char[m];
		a=new poly<double> [m];
		for(i=0;i<m;i++)
		{
			in>>n;
			a[i].input(n,in);
		}
		for(i=1;i<m;i++)
		{
			in>>ch[i];
		}
		for(i=1;i<m;i++)
		{
			if(ch[i]=='+')
				a[i]=a[i]+a[i-1];
			else if(ch[i]=='-')
				a[i]=a[i]-a[i-1];
			else if(ch[i]=='*')
				a[i]=a[i]*a[i-1];
		}
		a[m-1].output(out);
		b=a[m-1];
		b=b.dev(b);
		c=a[m-1];
		c=c.indev(c);
		while(in>>st>>value)
		{
			if(st==48&&value==0)
				break;
			if(st=='d')
			{
				b.output(out);
				result=b.val(value);
				out<<result<<endl;
			}
			else if(st=='i')
			{
				c.output(out);
				result=c.val(value);
				out<<result<<endl;
			}
		}
	return 0;
}