ponominal.cpp

通过链表实现多项式得加法。。思想是3层循环建立一单向循环链表

// Polynominal.cpp : Defines the entry point for the console application.
//
//#include "cstdafx"
#include <iostream>
#include <cmath>
using namespace std;
class Term{
public:
    Term(int c,int e);
	Term(int c,int e,Term* nxt);
    Term* InsertAfter(int c,int e);//在this指针指示的项后插入新项
    int coef;
    int exp;
    Term *link;
};    
Term::Term(int c,int e):coef(c),exp(e){
link=0;
}
Term::Term(int c,int e,Term *nxt):coef(c),exp(e){
link=nxt;
}
Term* Term::InsertAfter(int c,int e)
{	
link=new Term(c,e,link);//相当于this->link=new Term(c,e,this->link);
return link;
}


ostream &operator<<(ostream& out, const Term &val)
{
  if(val.coef==0) return out;    
  out<<val.coef;
  switch(val.exp){
    case 0:break;
    case 1:out<<"X"; break;
    default:out<<"X^"<<val.exp; break;
}
return out;
}


class Polynominal
{
public:
  Polynominal();
  ~Polynominal();
  void AddTerms(istream& in);
  void Output(ostream& out)const;
  void PolyAdd(Polynominal& r);
 // void PolyMul(Polynominal& r);1
  void empty();
  Term* theList; 
};
Polynominal::Polynominal()
{
theList = new Term(0,-1); //生成带头结点的空循环链表
theList->link=theList;
}
void Polynominal::empty(){
	Term* p = theList->link;
	while(p != theList) {
		Term* temp;
		temp = p;
		p=p->link;
		theList->link=p->link;
		delete temp ;
	
	}
	delete theList;
}

Polynominal::~Polynominal(){
empty();
}
void Polynominal:: AddTerms(istream & in)
{
Term* q=theList;
int c,e;
for(;;){ 	  
          cout<<"Input a term(coef,exp):\n"<<endl;
    in>>c>>e;
    if (e<0) break;
          q=q->InsertAfter(c,e);
     }
}
void Polynominal::Output(ostream& out)const
{
   int first=1;
   Term *p=theList->link;
   cout<<"The polynominal is:\n"<<endl;
   for ( ; p!=theList; p=p->link){
     if (!first && (p->coef>0))  out<<"+";
     first=0;
     out<< *p;// 调用Term类上重载的“<<”操作。
   }
   cout<<"\n"<<endl;
}
void Polynominal::PolyAdd(Polynominal& r) //为什么只有一个参数
{
    Term* q,*q1=theList,*q2,*p;
    p=r.theList; q=q1->link; p=p->link;   //p和q指向两个当前进行比较的项
 while (p->exp>=0){    //如果p多项式未结束，则继续
    if (p->exp<q->exp){
		q1=q; q=q->link;
	}
    if (p->exp==q->exp){
        q->coef=q->coef+p->coef;
        if (q->coef==0){
            q2=q;q1->link=q->link;
            q=q->link;
			delete q2;
            p=p->link;
        }
        else {
            q1=q; q=q->link; p=p->link;
        }
    }
    else{                      // (p->exp>q->exp)
        q1=q1->InsertAfter(p->coef,p->exp);  
        p=p->link;
    }   //end else
 }    //end while
}     //end PolyAdd

ostream& operator <<(ostream &out,const Polynominal &x) 
{  x.Output(out);   return out;

}
istream& operator >>(istream& in, Polynominal &x)
{  x.AddTerms(in);   return in;
}
Polynominal& operator +(Polynominal &a, Polynominal &b) 
{  a.PolyAdd(b);
   return a;
}
Polynominal& operator * (Polynominal& a, Polynominal& b){
	Term *p=a.theList, *q;
	p=p->link;
	Polynominal sum;
    
	for (; p->exp >= 0; p=p->link) {
		q=b.theList;
		q=q->link;
		Polynominal temp; //保存每次循环所得的多项式
		Term* t=temp.theList;
		for (;q->exp >= 0; q=q->link) {
			t=t->InsertAfter(p->coef*q->coef,p->exp+q->exp);//把相乘后所得项放入临时多项式temp中
			}
		sum = sum + temp;//实现本次循环所得多项式与上次循环所得多项式的相加，并把结果保存在另一多项式sum中
		temp.empty();
		delete t;
	}
	a = sum;
	return a;
}
		
int main()
{ 
Polynominal p,q; //创建两个多项式对象p、q
int a;
cin>>p; cout<<p; //输入和显示多项式p
cin>>q; cout<<q; //输入和显示多项式q
cout<<"Please enter the number standing for operation(1 for add, 2 for multiply):"<<endl;
cin>>a;
switch(a){
	case 1:p=p+q;break;
	case 2:p=p*q;break;
}
cout<<p;
getchar();
}