polymul.cpp

多项式相乘作业

// Polymul.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"


int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

#include<iostream>
using namespace std;

class Term {
public:
	Term(int c, int e);
	Term(int c, int e, Term *nxt);
	Term* InsertAfter(int c, int e);
private:
	int coef;
	int exp;
	Term *link;
	friend ostream &operator<<(ostream &, const Term &);
	friend class Polynominal;
};

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);
	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:cout<<"X";break;
		default:out<<"X^"<<val.exp;break;
	}
	return out;
}

class Polynominal {
public:
	Polynominal();
	~Polynominal();                                          //析构函数
	Polynominal(const Polynominal &p);                      //复制构造函数
	void AddTerms(istream &in);
	void AddTerms(int c, int e);							//增加项
	void Output(ostream &out)const;
	void PolyAdd(Polynominal &r);
	Polynominal PolyMul(Polynominal&b);					  //用于进行乘法运算的成员函数
private:
	Term *theList;
	friend ostream &operator<<(ostream &, const Polynominal &);
	friend istream &operator>>(istream &, Polynominal &);
	friend Polynominal operator*(Polynominal &, Polynominal &);    //定义重载运算符*为友元类
};

Polynominal::Polynominal() {
	theList=new Term(0,-1);
	theList->link=theList;
}

Polynominal::Polynominal(const Polynominal& p){                 //调用复制构造函数为使乘法运算结果保存于另一个多项式中，这样调用析构函数不存在访问冲突
	theList=new Term(0,-1);
    theList->link=theList;
	Term* q =theList;
	Term* r =p.theList->link;
	while(r!=p.theList){
		q=q->InsertAfter(r->coef,r->exp);
		r=r->link;
	}
}

Polynominal::~Polynominal() {                            //析构函数
		Term *m,*n;
		for(m=this->theList->link;m->exp>=0;) {        //释放多项式所有节点的空间 
			n=m;
			m=m->link;
			delete(n);
		}
		delete(m);
}

void Polynominal::AddTerms(istream &in) {
	Term *q=theList;
	int c,e;
	for(;;) {
		cout<<"Input a term(coef,exp):"<<endl;
		in>>c>>e;
		if(e<0)break;
		q=q->InsertAfter(c,e);
	}
}

void Polynominal::AddTerms(int c, int e) {				//AddTerms实现
	Term *q=theList;
	q=q->InsertAfter(c,e);
}

void Polynominal::Output(ostream &out) const {
	int first=1;
	Term *p=theList->link;
	cout<<"The polynominal is:"<<endl;
	for(;p!=theList;p=p->link) {
		if(!first&&(p->coef>0)) out<<"+";
		first=0;
		out<<*p;
	}
	cout<<"\n"<<endl;
}

void Polynominal::PolyAdd(Polynominal &r) {
	Term *q,*q1=theList,*q2,*p;
	p=r.theList;q=q1->link;p=p->link;
	while(p->exp>=0) {
		while(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 {
				q1=q1->InsertAfter(p->coef,p->exp);
				p=p->link;
		}
	}
}

Polynominal Polynominal::PolyMul(Polynominal &b) {				 //虽然是传引用，但函数体中没有改变b的值，只是使用了。
	Polynominal z;										        //z用于保存相乘的结果，而不是修改当前多项式来保存结果。
	Term *t,*m;
	for(t=this->theList->link;t->exp>=0;t=t->link) {
		Polynominal r;											//r为临时的多项式，用于保存第一个多项式的每一项和第二个多项式相乘的结果
		for(m=b.theList->link;m->exp>=0;m=m->link) {
			r.AddTerms((t->coef)*(m->coef),(t->exp)+(m->exp));	//系数相乘，指数相加
		}
		z.PolyAdd(r);                                         //将临时多项式累加到表示最终结果的多项式里去
	}
	return Polynominal(z);                                   //结果返回
}

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,b的值，只是使用了。
	return Polynominal(a.PolyMul(b));
}

int main() {
	Polynominal p,q;
	int a;
	cout<<"Please input the first polynominal:"<<endl;				//根据输入创建第一个多项式
	cin>>p;cout<<p;
	cout<<"Please input the second polynominal:"<<endl;				//根据输入创建第二个多项式
	cin>>q;cout<<q;
	cout<<"working on multiplication..."<<endl;
	cout<<q*p;								                     //输出两个多项式相乘的结果	
	getchar();
	getchar();
}