poly.cpp

本程序用于实系数一元项式问题

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


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 ()
	{
		head=NULL;
	}
	~poly()
	{
	}
	void input ( int n,istream & in)
	{
		int i;
		Node<double> *p,*q,*r;
		for(i=0;i<n;i++)
		{
			r=new Node<double>;
			in>>r->coef>>r->exp;
			if(r->coef==0)
				continue;
			else{
					if(head==NULL)
					{
						head=r;
						head->next=NULL;
					}
					else
					{
						p=head;
						q=p;
						while(p!=NULL&&p->exp>r->exp)
						{
							q=p;
							p=p->next;
						}
						if(p==NULL)
						{	
							q->next=r;
							r->next=p;
						}
						else if(p==head)
						{
							if(r->exp==p->exp)
								p->coef=p->coef+r->coef;
							else
							{
								p=head;
								head=r;
								r->next=p;
							}
						}
					else
					{
						if(r->exp==p->exp)
						{
							p->coef=p->coef+r->coef;
							delete r;
						}
						else
						{
							q->next=r;
							r->next=p;
						}
					}
				}
			}
		}
	}
	void output(ostream & out)const
	{
		Node<double> *h;
		h=head;
		if(h)
		{
			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<<"\n";
	}
	Node<T> *gethead()
	{
	return head;
	}
	T getcoef()
	{
		return head->coef;
	}
	T getexp()
	{
		return head->exp;
	}
	poly dev(poly m)
	{
		Node<double> * h,* p;
		h=m.gethead();
		p=h;
		while(h)
		{
			h->coef=h->coef*h->exp;
			h->exp=h->exp-1;
			h=h->next;
		}
		head=p;
		return  m;
	}
	poly indev(poly n)
	{
		Node<double> * h,* p;
		h=n.gethead();
		p=h;
		while(h)
		{
			h->exp=h->exp+1;
			h->coef=h->coef/h->exp;
			h=h->next;
		}
		head=p;
		return  n;
	}
	double 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;
	}
	poly & operator = ( poly & x)
	{
		Node<double> * p, *q=NULL,*h,*m;
		m=new Node<double>;
		m=x.gethead();
		while(m)
		{
			p=new Node<double>;
			p->coef=m->coef;
			p->exp=m->exp;
			if(q==NULL)
			{
				q=p;
				h=p;
			}
			else
			{
				q->next=p;
				q=p;
			}
			m=m->next;
		}
		p->next=NULL;
		head=h;
		delete m;
		return *this;
	}
	poly & operator + ( poly & x)
	{
		*this=add(*this,x);
		return *this;
	}
	poly & operator - ( poly & x)
	{
		*this=sub(*this,x);
		return *this;
	}
	poly & operator * ( poly & x)
	{
		*this=mul(*this,x);
		return *this;
	}
	poly & add(poly & a,poly & b)
	{
		Node<double> *p,*q,*l,*n,*m,*h;
		double x;
		h=a.gethead();
		q=b.gethead();
		p=h;
		l=p;
		while((p!=NULL)&&(q!=NULL))
			if(p->exp<q->exp)
			{
				if(p==h)
				{
					n=q;
					q=q->next;
					n->next =h;
					h=n;
					p=h;
					l=h;
				
				}
				else
				{
					n=q;
					q=q->next;
					l->next=n;
					n->next=p;
					l=n;
				
				}
			}
			else if(p->exp==q->exp)
			{
				x=p->coef+q->coef;
				if(x!=0)
				{
					p->coef=x;
					n=q;
					q=q->next;
					l=p;
					p=p->next;
					delete n;
				}
				else
				{
					m=p;
					l->next=p->next;
					p=p->next;
					delete(m);
					q=q->next ;
				}
			}
			else
			{
				l=p;
				p=p->next ;
			}
			if(q!=NULL)
				l->next=q;
			head=h;
			return a;
	}
	poly & sub(poly & a,poly & b)
	{
		Node<double> *p,*q,*l,*n,*m,*h;
		double x;
		p=a.gethead();
		q=b.gethead();
		while(p)
		{
			p->coef=-p->coef;
			p=p->next;
		}	
		h=a.gethead();
		q=b.gethead();
		p=h;
		l=p;
		while((p!=NULL)&&(q!=NULL))
			if(p->exp<q->exp)
			{
				if(p==h)
				{
					m=q;
					q=q->next;
					n->next =h;
					h=n;
					p=h;
					l=h;
				}
				else
				{
					n=q;
					q=q->next;
					l->next=n;
					n->next=p;
					l=n;	
				}
			}
			else if(p->exp==q->exp)
			{
				x=p->coef+q->coef;
				if(x!=0)
				{
					p->coef=x;
					n=q;
					q=q->next;
					l=p;
					p=p->next;
					delete n;
				}
				else
				{
					m=p;
					l->next=p->next;
					p=p->next;
					delete(m);
					q=q->next ;
				}
			}
			else
			{
				l=p;
				p=p->next ;
			}
			if(q!=NULL)
				l->next=q;
			head=h;
			return a;
	}
	poly & mul(poly & a,poly & b)
	{
		Node <double>*p,*q,*r,*l,*h,*m,*t;
		int flag;
		p=a.gethead();
		q=b.gethead();
		h=new  Node<double>;
		h->coef=a.getcoef();
		h->exp=a.getexp();
		flag=1;
		for(p;p!=NULL;p=p->next)
		{
			q=b.gethead();
			for(q;q!=NULL;q=q->next)
			{
				m=new Node<double>;
				m->coef=p->coef*q->coef;
				m->exp=p->exp+q->exp;
				if(flag)
				{
					if(h->coef==p->coef&&h->exp==p->exp)
					{
						h=m;
						h->next=NULL;
						l=h;
					}
					else
					{
						l->next=m;
						l=m;
						l->next=NULL;
					}
				}
				else
				{
					l=h;
					while(l!=NULL&&l->exp>m->exp)
					{
						r=l;
						l=l->next;
					}
					if(l==NULL)
					{
						r->next=m;
						m->next=l;
					}
					else
					{
						if(l->exp==m->exp)
						{
							l->coef=l->coef+m->coef;
							delete m;
							if(l->coef==0)
							{
								t=l;
								r->next=l->next;
								delete t;
							}
						}
						else
						{
							r->next=m;
							m->next=l;
						}
					}
				}

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



int main()
{
	int m=0,n,i,num=0;
	char *h,t;
	double result,v;
	poly<double> b,c;
	poly <double> *a;
	ifstream in("input.txt");
	ofstream out("output.txt");
	in>>m;
	if(m==0)
		out<<0<<"\n"<<0<<"\n"<<0<<"\n"<<0<<"\n"<<0<<"\n";
	else if(m<0)
		out<<"input error"<<"\n";
	else
	{
		h=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>>h[i];
		}
		for(i=1;i<m;i++)
		{
			if(h[i]=='+')
				a[i]=a[i]+a[i-1];
			else if(h[i]=='-')
				a[i]=a[i]-a[i-1];
			else if(h[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>>t>>v)
		{
			if(t==48&&v==0)
				break;
			if(t=='i')
			{
				c.output(out);
				result=c.val(v);
				out<<result<<"\n";
			}
			if(t=='d')
			{
				b.output(out);
				result=b.val(v);
				out<<result<<"\n";
			}
			
		}
	}
	return 0;
}