link_polynomial.h

这是一个用面向对象方法实现多项式四则运算的源程序

#include<iostream.h>
#include<string.h>
#include<stdio.h>
#include<math.h>
class multinomial;
class term
{
friend class multinomial;
	int ceof;
	int exp;
	term *next;
};
class multinomial
{
  public:
	  multinomial();
	  insert(term *ps);//插入项
	  del();//删除结点
	  input();//输入多项式,并把多项式存放到链表中
	  del_zero();//清链,把多项式中系数为零的相删除掉;
	  term *getMax();//找到多项式中有最大指数的项
	  multinomial add(multinomial b);//加法
	  multinomial sub(multinomial b);//减法
      multinomial term_mul_poly(term *b);//项与多项式相乘，为乘法做准备
	  multinomial multiply(multinomial b);//乘法
	  void divide(multinomial &a);//除法
	  output();//输出多项式
	  int iszero();

 private:
	  int termnumber;
	  term *newterm;//用于指向新建结点，引导其插入多项式中
	  term *head,*end;//头指针、末指针
	  term *first;//头结点，不放数据，用以简化插入、删除操作
};
multinomial::multinomial()//构造
{  	
	first=new term;
	first->ceof=first->exp=0;
	head=first;	
	first->next=NULL;
	end=first;
	termnumber=0;

}
multinomial::del_zero()//把链表中的零项清除掉
{
	term *p=first;
	for(;p->next;p=p->next)
	{
		for(;(p->next!=NULL)&&(p->next->ceof==0);)
		{
			newterm=p->next;
			p->next=newterm->next;
			delete newterm;
		}
		if(p->next==NULL) break;
	}
}
multinomial::insert(term *ps)//插入项
{
  if(first->next==NULL)//当多项式是空时,插入first后面
	{
      ps->next=first->next;
	  first->next=ps;
	  end=ps;
	}
  else
  {
   for(term *guard=first->next;guard;guard=guard->next)//按指数的大小从大到小插入
	{
	   if(guard->exp==ps->exp)//如果插入项的指数与多项式中某一项指数相等,系数相加就可以了
	   {
		   guard->ceof+=ps->ceof;
		   break;
	   }
	   if(guard->exp>ps->exp&&guard->next==NULL)//如果插入项的指数小于最后一项的指数,插到后面
	   {
            ps->next=guard->next;
			guard->next=ps;
			end=ps;
			break; 
	   }
	   if(guard->exp>ps->exp&&guard->next->exp<ps->exp)//插到中间适当位置
		{
			ps->next=guard->next;
			guard->next=ps;
			break;
	   }  	  
	   if(guard->exp<ps->exp)//如果插入项指数是最大的，插到最前面
	   {
		   ps->next=first->next;
		   first->next=ps;
		   break;
	   }
	   
	}
  }
}
term *multinomial::getMax()//取具有最大指数的项
{
	term *p=first->next,*q=first;
	for(;p;p=p->next)
		if(p->exp>=q->exp) q=p;	
	return q;
}
multinomial::input()//输入函数,把输入的多项式系数、指数辨认出来，存到多项式类中
{
    cout<<"(X表示变量，常数项后面要加X^0,回车结束输入):"<<endl;
	char poly[100];	
	char *p=gets(poly);
    
	newterm=new term;
	newterm->ceof=newterm->exp=0;
	int len=strlen(p);

	for(int j=0;j<=len;j++)
		if(p[j]=='^') termnumber++;
	int mark=0,ceofmark=0,sign=1;
	for(j=0;j<=len;j++,p++)
	{
		if((*p>='0')&&(*p<='9'))
		{
			if(mark==0)
			{
				ceofmark*=10;
				ceofmark+=sign*(*p-'0');
			}
			if(mark==1)
			{
				newterm->exp*=10;
				newterm->exp+=sign*(*p-'0');
			}
		}
		if(*p=='x'||*p=='X')
		{
			if(*(p-1)=='+'||(*(p-1)=='-')||j==0) ceofmark=sign;
			newterm->ceof=ceofmark;
			mark=1;
			ceofmark=0;
			sign=1;
		}
		if((*p=='+')||(*p=='-')||(*p=='\0'))
		{
            if(*(p-1)=='x'||*(p-1)=='X') 
			{
				newterm->exp=1;
			}		
			if(j!=0)
			{
			 insert(newterm);
             newterm=new term;
		     termnumber++;
			  newterm->exp=newterm->ceof=0;				
			}
			mark=0;
			if(*p=='-')  
			sign=-1;
			else sign=1;	
		}
	} 
	del_zero();
}
multinomial::output()//输出
{ 
	if(first->next==NULL) cout<<'0';
	else 
	{
	int i=0;//用于标示是否是要输出的第一项，因为第一项的系数如果是正的话不用输出'+'号
	term *p=first->next;
	//cout<<"p->next->ceof="<<p->ceof<<endl;
	for(;p;p=p->next)
	{  
			i++;//i为要输出的第一项，前面不用加'+"号
 	   	if((p->ceof)>0)
		{   
		   if(i==1) 
		   {
			   if(p->ceof==1);
			   else
				   cout<<p->ceof;
		   }
			else
			{
			  if(p->ceof==1) cout<<'+';			               
			       else
				cout<<'+'<<p->ceof;
			}
		}
		else
		{
	    	if(p->ceof==-1) cout<<'-';
					else if(p->ceof!=0) cout<<p->ceof;
		}
		if(p->ceof!=0) cout<<'X'<<'^'<<p->exp;
	}
	}
}
multinomial multinomial::add(multinomial b)//加法(把a加到b中，返回b)
{ 
	newterm=new term;
	term *guard=b.first->next,*q=first->next;
	int mark; //用于标示是否找到指数相同的接结，若有，则系数相加，否则，建一个新结点
	for(;q;q=q->next)
	{
		guard=b.first->next;//指示指针志指向头结点
		mark=0;
		for(;guard;guard=guard->next)
		{  
		  
		   if(guard->exp==q->exp)
		   { 
			   
			    guard->ceof=q->ceof+guard->ceof;
			    mark=1;
		   }
		}
		if(mark==0)
		{
		   newterm->ceof=q->ceof;
		   newterm->exp=q->exp;
		   b.insert(newterm);
           newterm=new term;
		}
		//cout<<"mark"<<endl;
		//b.output();
	}
	return b;
}
multinomial multinomial::sub(multinomial b)//减法(把b变为-b，然后加a)
{  
    newterm=new term;
	term *guard=(b.first)->next,*q=first->next;
	for(;guard;guard=guard->next)
		guard->ceof=-guard->ceof;
	multinomial result=add(b);
	return result;
}
multinomial multinomial::term_mul_poly(term *b)//项与多项式相乘，其为乘法的基础
{
	multinomial result;
    newterm=new term;
	term *guard=first->next;
	for(;guard;guard=guard->next)
	{
		newterm->ceof=(guard->ceof)*(b->ceof);
		newterm->exp=guard->exp+b->exp;
		//cout<<"newterm->exp"<<newterm->exp;   //此为编程过程中的测试语句，用于输出过程中的
        //cout<<"newterm->ceof"<<newterm->ceof; //结果，以便出现错误时分析错误原因，下同。
		result.insert(newterm);
		newterm=new term;
	}
	return result;

}
multinomial multinomial::multiply(multinomial b)//乘法
{	
	multinomial r;
    if(first->next==NULL||(b.first)->next==NULL)
		 cout<<"error!";
	else
	{
	    term *guard=(b.first)->next; 
		r=term_mul_poly(guard);	
		//cout<<(b.first)->next->exp;
      	for(guard=guard->next;guard;guard=guard->next)
		{
	       r=r.add(term_mul_poly(guard));
		}
	}
	return r;
}
void multinomial::divide(multinomial &a)//除法
{
	if(first->next==NULL) cout<<"Error!!除数多项式不能为零!";
	else
	{
	multinomial quot,remain=a;
	newterm=new term;
	term *A,*B;
	A=a.getMax();
	B=getMax();
	
   if(B->exp>A->exp)//如果除数最高指数大于被除数的最高指数，则商为零，余数等于被除数 
	{
		cout<<"多项式相除结果为:商:"<<'0'<<'\t';
		cout<<"余项:";
		a.output();
	}
    else
	{
	 for(;A->exp>=B->exp;)//如果除数最高指数大于被除数的最高指数，则继续求商所含的项
	  {
          newterm->ceof=A->ceof/B->ceof;
	      newterm->exp=A->exp-B->exp;
	      quot.insert(newterm);
	      remain=remain.sub(term_mul_poly(newterm));
		  remain.del_zero();
	      A=remain.getMax();
	      //remain.output();
          //cout<<newterm->exp<<endl;
	   	 if((A->exp==0)&&(B->exp==0)) break;
		 newterm=new term;		 
	  }
	  cout<<"<商>为:"<<endl;
	  quot.del_zero();
	  quot.output();
	  cout<<endl;
	  cout<<"<余项>为:";
	  remain.output();
	}
	}
}