polynomal.cpp

数据结构关于多项式相加的源码

#include<iostream.h>
//作者:5021419011 安然   5021419012 曹蕾 
class polynomal;  //多项式前视类定义
class term{    //项类定义
	friend class polynomal;
public:
	double coef;  //系数
	int expn;     //指数
	term * link;
   //项链接指针
public:
	
	term(double c=0,int e=0,term * next=NULL):coef(c),expn(e),link(next){}
	term* getlink(){return link;}
};


class polynomal{    //多项式类定义
	term *first,*current;    //头指针,当前指针
	int n;    //多项式阶数
public:
	polynomal(){first=new term(0,0,NULL);current=first;}    //构造函数
//	~polynomal();   //析构函数
	int length()const;    //计算多项式项数
	int isempty(){return first->link==first;}  //判断是否零多项式
	int find(int value);  //在多项式中寻找指数为value的项
	int getexpn()const;    //返回当前项的指数值
	double getcoef()const;   //返回当前项的系数值
	double value(term *p,double x);
	void Insert(double coef,int expn);
	void firster(){current=first;}   //将当前指针置于头结点
	int thefirst();  //将当前指针指向链表的第一个结点
	int next();    //将当前指针指到当前结点的后继结点
	int prior();    //将当前指针指到当前结点的前驱结点
	void inser(const double coef,int expn);    //插入新结点
	void remove();   //删除当前结点
	double calc(double x);   //求多项式的值
	void output();  //显示多项式
	friend polynomal operator +(polynomal&,polynomal&);
	friend polynomal operator *(polynomal&,polynomal&);
};

double polynomal::value(term *p,double x){
	if(p->link==first)return p->coef;
	else return p->coef+value(p->link,x);
}

double polynomal::calc(double x){
	term *pc=first->link;
	return (pc==first)?0.0:value(pc,x);
}

polynomal operator *(polynomal&a,polynomal&b){
	polynomal temp;
	term *pa=a.first->link,*pb,*pc,*pctemp,*pcprior,*p;
	double value;
	int expvalue;
	temp.first=pc=new term;
	pc->link=NULL;
    pctemp=pc->link;

	while(pa!=NULL){
		pb=b.first->link;
	
		while(pb!=NULL){
       
		pctemp=pc->link;
        value=pa->coef * pb->coef;
		expvalue=pa->expn+pb->expn;
	
		if(pctemp==NULL)
		{
			p=new term(value,expvalue);
			p->link=NULL;
			pc->link=p;
		}

		else {

			while(pctemp!=NULL&&expvalue>pctemp->expn)
			{
				
					pcprior=pctemp;
			    	pctemp=pctemp->link;
			
			}
				
			if(pctemp!=NULL&&pctemp->expn==expvalue)
			{	pctemp->coef=pctemp->coef+value;}
			else{	
	      p=new term(value,expvalue);
	      p->link=pctemp;
		  pcprior->link=p;
				}


		}
		
	
     pb=pb->link;
	
}
		pa=pa->link;
	}
   temp.first=pc;
	return temp;


}
	
void polynomal::Insert(double coef,int expn){
	term *p=first;
	current=first;
	if(first->link==NULL)
	{
	current=new term(coef,expn);
	current->link=NULL;
    first->link=current;
	}

	else{ 
			current=first;	
		while(current->link!=NULL&&expn>current->link->expn){
			current=current->link;}

	    p=new term(coef,expn);
	     p->link=current->link;
		 current->link=p;
	}
}


void polynomal::output(){
         current=first;
		 if(current->link==NULL)
			 cout<<"多项式为空"<<endl;
		 else{
			 current=first->link;
			 cout<<"多项式为"<<endl;
			 while(current->link!=NULL)
			 {
                cout<<current->coef<<"x^"<<current->expn<<"+"; 
				current=current->link;
			 }
               cout<<current->coef<<"x^"<<current->expn<<endl; 
		 }
}

void main()
{
   polynomal pla,plb,plc;
   pla.Insert(2,3);
   pla.Insert(3,4);
   pla.Insert(5,6);
   pla.Insert(5,5);
   cout<<"a";
   pla.output();
   plb.Insert(2,3);
   plb.Insert(3,4);
   plb.Insert(5,5);
   cout<<"b";
   plb.output();
   plc=pla*plb;
   cout<<"c";
   plc.output();
}