polynomial.cpp

数据结构中用链表实现的多项式的加法

////////////////////////////////////////////////////////////////////////////////
//计算机科学与技术 ////////////////////////////////////////////////////////////
//0610394/////////////////////////////////////////////////////////////////////
//翁超群/////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
#include<iostream.h>
#include<fstream.h>
#include<string.h>
/////////////////////////////////////////////////////
 //多项式每一项data（包括系数和指数）的数据类型
////////////////////////////////////////////////////
class polydata{             
public:                                                  
	double coe;
	int exp;
};
///////////////////////////////////////////////////
//节点类，包含数据和next指针
///////////////////////////////////////////////////
class node {
	static node* freelist;
public:
    polydata data;
	node* next;
	void* operator new(size_t);
	void operator delete(void *);
};
////////////////////////////////////////////////
//节点类的内部函数实现，new和delete的重载，实现
//可利用空间表
////////////////////////////////////////////////
node* node::freelist=NULL;
void* node::operator new(size_t){
    if(freelist==NULL)
		return ::new node;
	node* temp=freelist;
	freelist=freelist->next;
	return temp;
}
void node::operator delete(void *ptr){
	((node*)ptr)->next=freelist;
	freelist=(node*)ptr;
}
/////////////////////////////////////////////////////
//多项式类是由一个链表组成，数据成员包括头尾指针，
//按照指数的降序排列从头指针到尾指针   
////////////////////////////////////////////////////
class polynomial{     
	node *head,*tail;
public:
    polynomial();
    void append(polydata *);
    void traverse(); 
    polynomial& operator+(polynomial& p2);
    polynomial& operator-(polynomial& p2);
    polynomial& operator*(polynomial& p2);
    polynomial& read(char *filename);
    void write(char * filename);
};
//////////////////////////////////////////////多项式类内部成员函数的实现////////////////////////////////////////////////////////

/////////////////////////////////////
//构造函数
////////////////////////////////////
polynomial::polynomial(){   
	    head=new node;
        head->next=NULL;
        tail=head;
};
////////////////////////////////////
//在多项式末尾添加多项式节点数据
///////////////////////////////////
void polynomial::append(polydata * newdata){
	 node *nptmp;
	 nptmp=new node;
	 nptmp->next=NULL;
	 nptmp->data= *newdata;
	 tail->next=nptmp;	
	 tail=nptmp;
}
///////////////////////////////////
//遍历多项式，输出每个数据
///////////////////////////////////
void polynomial::traverse(){                                         
	if(head->next==NULL){
		cout<<"It's empty!\n";return;
	}
	for(node * nptmp=head->next;nptmp!=NULL;nptmp=nptmp->next){
		cout<<"("<<nptmp->data.coe<<",";
		cout<<nptmp->data.exp<<") ";
	}
	cout<<endl;
}
 /////////////////////////////////
 //操作符+重载，实现多项式加法
//////////////////////////////////                                          
polynomial& polynomial::operator+(polynomial& poly2){
node * nptmp1=head;
	node * nptmp2=(poly2).head;
	if((poly2).head->next==NULL)
		return *this;
	if(head->next==NULL){
		return poly2;
	}
	while(nptmp1->next!=NULL&&nptmp2->next!=NULL){
		if(nptmp1->next->data.exp>nptmp2->next->data.exp){
			nptmp1=nptmp1->next;
			continue;
		}
		if(nptmp1->next->data.exp<nptmp2->next->data.exp){//如果第二个多项式的节点的指数大，该节点将被插入到第一个多项式中去。这样就节省了内存。
			node * nptmp=nptmp2->next->next;
		    nptmp2->next->next=nptmp1->next;
			nptmp1->next=nptmp2->next;
			nptmp2->next=nptmp;
            continue;
		}
		if(nptmp1->next->data.exp==nptmp2->next->data.exp){//如果两节点指数相等，则系数相加送到当前多项式节点中，同时删除第二个多项式的节点。
			nptmp1->next->data.coe+=nptmp2->next->data.coe;
	        if(nptmp1->next->data.coe==0){//相加等于零，删除当前多项式的这个节点。再删除第二个多项式的节点。
				node *npdel=nptmp1->next;
				nptmp1->next=npdel->next;
				if(npdel==tail)
					tail=nptmp1;
			    delete npdel;
			}
			else{
				nptmp1=nptmp1->next;
			}

	        node * nptmp=nptmp2->next;//第二个多项式没有指针下移，代之的是删除这个节点。
		    nptmp2->next=nptmp->next;
			delete nptmp;

			//nptmp2=nptmp2->next;

			continue;
		}
	}	
	if(nptmp2->next!=NULL){
    	 nptmp1->next=nptmp2->next;
	}

    return *this; 
}
 /////////////////////////////////////////
//操作符-重载，实现多项式减法
/////////////////////////////////////////
polynomial& polynomial::operator-(polynomial& poly2){
     for(node *nptmp=poly2.head->next;nptmp!=NULL;nptmp=nptmp->next){
         nptmp->data.coe=0-nptmp->data.coe;
     }
     return (*this+poly2);
}
////////////////////////////////////////
//操作符*重载，实现多项式乘法
////////////////////////////////////////
polynomial& polynomial::operator*(polynomial& poly2){
    polynomial *polysum_all=new polynomial;
	polydata polynodedata;
	for(node * nptmp1=head;nptmp1->next!=NULL;nptmp1=nptmp1->next){
		polynomial polytmp;
       	for(node * nptmp2=poly2.head;nptmp2->next!=NULL;nptmp2=nptmp2->next){
		        polynodedata.coe=nptmp2->next->data.coe*nptmp1->next->data.coe;
			    polynodedata.exp=nptmp2->next->data.exp+nptmp1->next->data.exp;
                polytmp.append(&polynodedata);
		}
		*polysum_all=*polysum_all+polytmp;
	}
    return *polysum_all; 
}
///////////////////////////////////////
//从文件中读出两个多项式，并根据其中的
//运算符号对两个多项式进行操作，并返回
//操作结果
////////////////////////////////////////                         
polynomial& polynomial::read(char *filename){
    polynomial polytest[2],*polyoperator=new polynomial ;
	ifstream inputfile(filename);
	polydata polynodedata;
	char ch,ch_operator[3],ch_eofcode[81];
       double da;int ib;
	int j=0;
	while(j<=1){
            inputfile.get(ch);
            inputfile>>da;
            inputfile.get(ch);
	        inputfile>>ib;
	        inputfile.get(ch);
	        polynodedata.coe=da;
	        polynodedata.exp=ib;
            if(!(da==0&&ib==0)){
				if(polynodedata.coe!=0)
		             polytest[j].append(&polynodedata);
			}
            else{
		        j++;
		        inputfile.get(ch);
			}	}  
	cout<<"从文件inputfile.txt读出的两个多项式是：\n";
	polytest[0].traverse();
    polytest[1].traverse();
    for(int k=0;k<3;k++)
	    inputfile.get(ch_operator[k]);
	ch_operator[3]='\0';
	cout<<"操作符是：\n"<<ch_operator<<endl;
	inputfile.getline(ch_eofcode,80);
	cout<<"文件末尾是:\n"<<ch_eofcode<<endl; 
    inputfile.close();
	if(strcmp(ch_operator,"AND")==0){

		*polyoperator=polytest[0]+(polytest[1]);
		
	};
	if(strcmp(ch_operator,"SUB")==0){
	    *polyoperator=polytest[0]-polytest[1];
	};
	if(strcmp(ch_operator,"MUL")==0){
		*polyoperator=polytest[0]*polytest[1];
	};
	cout<<"操作后形成的多项式链表是：\n";
    (*polyoperator).traverse();
	return *polyoperator;
}
/////////////////////////////
//将多项式写入指定文件
/////////////////////////////                         
void polynomial::write(char *filename){
    ofstream outputfile(filename);
	if(head->next==NULL)
	{
		outputfile<<"It's empty!"<<endl;
		return;
	}
    for(node * nptmp=head->next;nptmp!=NULL;nptmp=nptmp->next)
	{
        if(nptmp==head->next)
		{
			outputfile<<nptmp->data.coe<<"X"<<nptmp->data.exp;
			continue;
		}
		if(nptmp->data.exp==0){
	        if(nptmp->data.coe<0)
			{
			    outputfile<<nptmp->data.coe;
		        continue;
			}
	    	else
			{
				outputfile<<"+"<<nptmp->data.coe;
				continue;
			}
		}
		if(nptmp!=head->next&&nptmp->data.exp!=0)
		{
				if(nptmp->data.coe<0)
				{
					outputfile<<nptmp->data.coe<<"X"<<nptmp->data.exp;
				    continue;			
				}
				else{
					outputfile<<"+"<<nptmp->data.coe<<"X"<<nptmp->data.exp;
				    continue;
				}

		}
	}
    outputfile<<endl;
    outputfile.close();
	cout<<"运算结果已经按照要求的格式写入文件outputfile中!\n";
}

///////////////////////////////////////////////////////主函数//////////////////////////////////////////////////////
void main(){
    char *infilename="inputfile.txt";
    char *outfilename="outputfile.txt"; 
    polynomial polyreader,polywriter;
    polywriter=polyreader.read(infilename);
    polywriter.write(outfilename);
}