数据结构 多项式乘法.docVIP

实习报告 一、实习题： 请写出计算两个以单链接表表示的多项式相乘的程序。 1．需求分析和说明 两个多项式相乘，可以利用两个多项式的加法来实现，因为乘法运算可以分解为一系列的加法运算：C(x)=A(x)*B(x)=A(x)*(b1x+b2x2+…+bnxn)= 先用其中一个多项式去乘以另一个多项式的每一项，得出的若干个多项式按照一定的顺序相加，即幂不同的按照升幂排列，幂相同的将系数相加。 例如： 对于 (X-1+2X-2)*(2X-2+4X-3). X-1*(2X-2+4X-3)=2X-3+4X-4; 2X-2*(2X-2+4X-3)=4X-4+8X-5; 排列结果：2X-3+8X-4+8X-5 2．设计 用两个单链表的存储两个多项式，每个结点包含单项式的系数，幂和指向下一个元素地址的指针。用其中的一个多项式乘以另一个多项式的每一项，随后将所得结果按照升幂顺序排列，最后得到结果。 存储结构： //单项式结构 struct Term { float coef; // 系数。 int exp; // 幂指数。 Term( float c, int e) { coef = c; exp = e;} Term( ) { } friend int operator == (const Term L, const Term T ) { return L.exp == T.exp; } friend int operator (const Term L, const Term T ) { return L.exp T.exp; } friend int operator (const Term L, const Term T ) { return L.exp T.exp; } friend Term operator += ( Term L, const Term T ) { L.coef += T.coef; return L; } //幂指数相同，则系数相加。 friend Term operator *=(Term L, const Term T){ //实现单项式乘法 L.coef*=T.coef; L.exp+=T.exp; return L; } friend int equal_stop(const Term L, const Term T ) //用作输入结束标志，等则结束输入。 {return L.exp==T.exp L.coef==T.coef;} friend istream operator ( istream is, Term T ); friend ostream operator ( ostream os, const Term T ); friend char compare( const Term P, const Term T ); friend Is_Empty( const Term T ){ return !T.coef; } }; //多项式类 template class ElemType class Polynomial { public: Polynomial (const ElemType P) {Stop_flag=P;} Polynomial ( ) { } ~Polynomial ( ){ } Polynomial operator = ( const Polynomial T ); // Polynomial operator + ( const Polynomial T); Polynomial operator*( const Polynomial T); friend istream operator ( istream is, PolynomialElemType T );