多项式运算
polynomial.h
#ifndef POLYNOMAL_H#define POLYNOMAL_H#include<iostream>using namespace std;class Term{//多项式结点public: float coef; //系数 int exp;//指数 Term *link; Term(float c,int e,Term *next=NULL):coef(c),exp(e),link(next){} Term* InsertAfter(float c,int e); friend ostream& operator<<(ostream&,const Term&);};class Polynomial{public: Polynomial(){ first = new Term(0,-1); } Polynomial(Polynomial& R); int maxOrder();//最大阶数 Term *getHead()const{ return first; } Term* InsertAfter(Term*);private: Term *first; friend ostream& operator<<(ostream&,const Polynomial&); friend istream& operator>>(istream&,Polynomial&); friend Polynomial operator+(Polynomial&,Polynomial&); friend Polynomial operator*(Polynomial&,Polynomial&);};#endif // POLYNOMAL_H#include"Polynomial.h"using namespace std;/* 在当前结点再插入一个结点:c的e次方 */Term* Term::InsertAfter(float c, int e){ link = new Term(c,e,link); return link;}ostream& operator<<(ostream& out,const Term& x){ if(x.coef == 0.0){ return out; } out << x.coef; switch(x.exp){ case 0: break; case 1: out << "X"; break; default: out << "X^" << x.exp; break; } return out;}Polynomial::Polynomial(Polynomial &R){ Term* src = R.getHead()->link; Term* dest = new Term(0,-1); while(NULL!=src){ dest->InsertAfter(src->coef,src->exp); dest = dest->link; src = src->link; }}/* 最大阶数 */int Polynomial::maxOrder(){ Term* current = getHead()->link; int maxOrder,times=0; while(NULL!=current){ if(times==0){ maxOrder = current->exp; times++; }else{ maxOrder = max(maxOrder,current->exp); } current = current->link; } return maxOrder;}Term* Polynomial::InsertAfter(Term *term){ Term* current = first; while(NULL!=current->link){ current = current->link; } current->InsertAfter(term->coef,term->exp); return current;}istream& operator>>(istream& in,Polynomial& x){ Term* current = x.getHead(); float c; int e; while(1){ cout << "Input a term(coef,exp):" << endl; in >> c >> e; if(e<0) break; current = current->InsertAfter(c,e); } return in;}ostream& operator<<(ostream& out,Polynomial& x){ Term* current = x.getHead()->link; bool first = true; while(NULL!=current){ if(current->coef>0.0&&(not first)){ out << "+"; } out << *current; first = false; current = current->link; } out << endl; return out;}Polynomial operator+(Polynomial& p1,Polynomial& p2){ Polynomial p3; Term *current1,*current2,*current3; current3 = p3.getHead(); current1 = p1.getHead()->link; current2 = p2.getHead()->link; float coef; while(NULL!=current1&&NULL!=current2){ if(current1->exp==current2->exp){ coef = current1->coef+current2->coef; p3.InsertAfter(new Term(coef,current1->exp)); current1 = current1->link; current2 = current2->link; }else if(current1->exp<current2->exp){ p3.InsertAfter(new Term(current1->coef,current1->exp)); current1 = current1->link; }else{ p3.InsertAfter(new Term(current2->coef,current2->exp)); current2 = current2->link; } } //处理长的那个多项式 while(NULL!=current1){ p3.InsertAfter(new Term(current1->coef,current1->exp)); current1 = current1->link; } while(NULL!=current2){ p3.InsertAfter(new Term(current2->coef,current2->exp)); current2 = current2->link; } return p3;}/* 先把所有的乘出来，再合并 */Polynomial operator*(Polynomial& p1,Polynomial& p2){ Polynomial p3,p4; Term *current1,*current2,*current3,*current4; current1 = p1.getHead()->link; current2 = p2.getHead()->link; current3 = p3.getHead(); current4 = p4.getHead(); int minExp,currExp; bool flag = true; while(NULL!=current1){ current2 = p2.getHead()->link; while(NULL!=current2){ currExp = current1->exp+current2->exp; if(flag){ minExp = currExp; flag = false; }else{ minExp = minExp<currExp?minExp:currExp; } p3.InsertAfter(new Term(current1->coef*current2->coef, current1->exp+current2->exp)); current2 = current2->link; } current1 = current1->link; } Term t(0,-1); int maxExp = p2.maxOrder()+p1.maxOrder(); for(int i=minExp;i<=maxExp;++i){ current3 = p3.getHead()->link; t.exp = i; while(NULL!=current3){ if(current3->exp==i){ t.coef += current3->coef; } current3 = current3->link; } if(t.coef!=0){ p4.InsertAfter(new Term(t.coef,t.exp)); t.coef=0; } } return p4;}int main(){ Polynomial p1,p2,p3,p4; p1.getHead()->InsertAfter(3,-1)->InsertAfter(-2,1)->InsertAfter(3,3); p2.getHead()->InsertAfter(2,0)->InsertAfter(2,2)->InsertAfter(4,3)->InsertAfter(3,5); cout << "p1:" << p1; cout << "p2:" << p2; p3 = p1+p2; p4 = p1*p2; cout << "p1+p2:" << p3; cout << "p1*p2:" << p4;}p1:3X^-1-2X+3X^3p2:2+2X^2+4X^3+3X^5p1+p2:3X^-1+2-2X+2X^2+7X^3+3X^5p1*p2:6X^-1+2X+12X^2+2X^3+1X^4+6X^5+6X^6+9X^8