数据结构 多项式乘法.docx

数据结构 多项式乘法 实习报告 一、实习题： 请写出计算两个以单链接表表示的多项式相乘的程序。 1需求分析和说明 两个多项式相乘，可以利用两个多项式的加法来实现，因为乘法运算可以分n解为一系列的加法运算：C(x)=A(x)*B(x)=A(x)*(b1x+b2x+bnx)=å2nA(x)bixii=1先用其中一个多项式去乘以另一个多项式的每一项，得出的若干个多项式按照一定的顺序相加，即幂不同的按照升幂排列，幂相同的将系数相加。 例如： 对于 (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; 1 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, Polynomial<ElemType> & T ); friend ostream & operator << ( ostream & os, const Polynomial<ElemType> & T ); private: List<ElemType> poly; ElemType Stop_flag; / 用于判断多项式输入结束。 ; 算法思想： 用两个单链表的存储两个多项式，每个结点包含单项式的系数，幂和指向下一个元素地址的指针。用其中的一个多项式中的每一项乘以另一个多项式，将得到的若干个多项式中的每一项按照幂次的顺序相加。即幂数相等项的系数相加，最后得到结果。 调用关系： 程序有三个文件，list.h, poly.h，main.cpp,文件poly.h调用list.h。文件main.cpp调用poly.h。 算法实现框架： 2 声明两个Polynomial类的多项式 用一个多项式中的每一个单项式去乘以另一个多项式，得若干个多项式。 将得到的若干个多项式中的每一项按照幂次的顺序相加。即幂数相等项的系数相加，然后升幂排列 得运算结果。 3用户手册： 运行程序，按照屏幕提示按幂次由低到高的顺序输入两个多项式，以作为结束标志。两个多项式输入完毕后，程序自动显示两个多项式相乘的结果。 4调试报告： 时间复杂度分析： 假设两个多项式的单项式个数分别为m和n。先用A多项式去乘以B多项式的每一项时，得到m个项数为n的多项式，完成这一步的时间复杂度为O。然后进行相加的步骤，按照时间复杂度的求和定理，整个程序的时间复杂度为O。 算法改进思路： 可以参考首项相乘的幂和末项项乘的幂，即最大次幂n和最小次幂m，取m<=i<=n,对i循环，对i的每一个值寻找多项式相乘的幂对应项，最后对所有项求和表示即可。但其时间复杂度要更大，在某些情况下可以参考。 5附录 源程序清单 3 /poly.h #include<iostream.h> #include "listdefine.h" /单项式结构 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; ; char compare(const Term &P, const Term &T) if (P=T) return '=' else if (P<T) return '<' else return '>' istream & operator >> ( istream &is, Term &T ) cout<< "Create a coefficient and power exponent ! n" cout<< "Please input a coefficient ! n" is >>T.coef; cout<< "Please input a power exponent ! n" 4 is >>T.exp; return is; ostream & operator << ( ostream & os, const Term & T ) if (T.coef>0) os<< '+' os << T.coef << "x->"<< T.exp; return os ; /多项式类 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, Polynomial<ElemType> & T ); friend ostream & operator << ( ostream & os, const Polynomial<ElemType> & T ); private: List<ElemType> poly; ElemType Stop_flag; / 用于判断多项式输入结束。 ; template <class ElemType> istream & operator >>( istream & is, Polynomial<ElemType> & T ) ElemType elem; ListItr<ElemType> Itr(T.poly); cout << "Create a Polynomial! n" cout << "Please input coefficient and power exponent one by one! n" while ( is>>elem,!equal_stop(elem,T.Stop_flag) Itr.Insert(elem); return is; template <class ElemType> ostream & operator << ( ostream & os, const Polynomial< ElemType > & T ) if (T.poly ).IsEmpty( ) os << "Polynomial is Empty!n" else for (ListItr<ElemType>Itr(T.poly);+Itr;+Itr) os<<Itr<<' ' return os<<'n' 5 template<class ElemType> Polynomial<ElemType>& Polynomial<ElemType>:operator Polynomial<ElemType> &T) if(this=&T) return *this; poly.MakeEmpty; ListItr<ElemType> ItrT(T.poly); ListItr<ElemType> ItrThis(poly); for(;+ItrT;+ItrT) ItrThis.Insert(ItrT); return *this; template<class ElemType> Polynomial<ElemType>& Polynomial<ElemType>:operator Polynomial<ElemType> &T) ElemType elemA,elemB; Polynomial<ElemType> C; ListItr<ElemType> ItrA(poly); ListItr<ElemType> ItrB(T.poly); ListItr<ElemType> ItrC(C.poly); for(;+ItrA;+ItrA) ItrB.First; for(;+ItrB;+ItrB) elemA=ItrA; elemB=ItrB; elemA*=elemB; if(!(C.poly).IsEmpty) ItrC.First; ElemType a; int k; for(k=0;(+ItrC)&&(k!=-1);+ItrC) switch(compare(elemA,ItrC) case '>': k+; a=ItrC; break; case '=': 6 =(const *(const ElemType b=ItrC; a=ItrC; b+=elemA; if(!Is_Empty(b) ItrC.Insert(b); ItrC.Remove(a); k=-1; break; case '<': ItrC.Zeroth; for(int i=0;i<k;+i) +ItrC; ItrC.Insert(elemA); k=-1; break; if(!+ItrC&&k!=-1) if(C.poly).IsEmpty) ItrC.Insert(elemA); else ItrC.Find(a); ItrC.Insert(elemA); *this=C; return *this; /listdefine.h #include<iostream.h> void Exception(int Condition, const char* ErrorMsg) if(Condition) cerr << ErrorMsg << endl; 7 /单链表节点类 template<class ElemType> class AbsListItr; template<class ElemType> class AbsList public: AbsList; virtual AbsList; virtual IsEmpty const=0; virtual IsFull const=0; virtual void MakeEmpty=0; friend class AbsListItr <ElemType> private: AbsList(const AbsList &) ; template <class ElemType> class AbsListItr public: AbsListItr(const AbsList<ElemType>&L) AbsListItr(const AbsListItr &); virtual AbsListItr virtual void Insert(const ElemType &x)=0; virtual int Remove(const ElemType &x)=0; virtual int Find(const ElemType &x)=0; virtual int IsFound(const ElemType &x) const =0; virtual int operator +const=0; virtual const ElemType &operatorconst=0; virtual void Zeroth=0; virtual void First=0; virtual void operator +=0; virtual void operator +(int)=0; protected: AbsListItr ; template <class ElemType> class List; / 单链表类的向前说明。 template <class ElemType> class ListItr; / 单链表迭代器类的向前说明。 template <class ElemType> class ListNode friend class List <ElemType> / 单链表类为其友元类, 便于访问结点类中的私有成员。 8 friend class ListItr <ElemType> / 单链表迭代器类为其友元类, 便于访问结点类中的私有成员。 private: ElemType Element; / 结点数据。 ListNode<ElemType> * Next; / 指向下一个结点的指针。 public: ListNode (const ElemType &E, ListNode<ElemType> *N=NULL):Element(E),Next(N) / 构造函数 ListNode<ElemType> * getNextreturn Next; ListNode( ) : Next( NULL ) / 构造函数 ListNode ( ) ; / 析构函数 ; /单链表类 template <class ElemType> class ListItr; / 单链表迭代器类的向前说明。 template <class ElemType> class List : public AbsList<ElemType> friend class ListItr <ElemType> / 单链表迭代器类为其友元类。 private: ListNode<ElemType> * head; / 指向头结点的指针。 public: List( ) head = new ListNode< ElemType >( ); List( ) MakeEmpty( ); delete head; / 析构函数 const List & operator=(const List &R); / 完成复制功能。 int IsEmpty( ) const return head->Next = NULL; int IsFull( ) const return 0; void MakeEmpty( ); ; template <class ElemType> void List <ElemType>:MakeEmpty ListNode <ElemType> *Ptr; ListNode <ElemType> *NextNode; for(Ptr=head->Next;Ptr!=NULL;Ptr=NextNode) NextNode=Ptr->Next; delete Ptr; head->Next=NULL; template <class ElemType> class ListItr : public AbsListItr<ElemType> private: ListNode<ElemType> *const head; / 指向头结点的常指针。 9 ListNode<ElemType> *Current; / 指向当前结点的指针。 public: ListItr( const List<ElemType> & L) : head( L.head ) Current = L.IsEmpty( ) ? head : head->Next; ListItr( ) / 析构函数 int Find( const ElemType & x ); / 查找值为x的结点，查找成功则使其成为当前结点，并返回True。 int IsFound( const ElemType & x ) const; /查找值为x的结点，查找成功返回 / True，否则返回False;不改变指针Current的值。 void Insert( const ElemType & x ); / 插入成功，新结点成为当前结点。 int Remove( const ElemType & x ); / 删除值为x的结点的操作。 int operator + ( ) const return Current && Current != head; / 当前结点非空则返回True。 const ElemType & operator ( ) ( ) const; / 取当前结点的数据值。 void operator + ( ); / 使当前结点的直接后继结点成为当前结点。 void operator + (int) operator+( ); / 定义为前缀+运算符。 void Zeroth ( ) Current=head; / 当前指针指向头结点。 void First( ); / 当前指针指向首结点。 const ListItr & operator=(const ListItr &); ; template <class ElemType> int ListItr<ElemType> : Find( const ElemType & x ) ListNode<ElemType> * Ptr = head->Next; while (Ptr!=NULL && !(Ptr->Element=x) Ptr=Ptr->Next; if (Ptr = NULL) return 0; Current = Ptr; return 1; template <class ElemType> int ListItr<ElemType> : IsFound( const ElemType & x ) const ListNode<ElemType> * Ptr = head->Next; while ( Ptr != NULL && !( Ptr->Element = x) ) Ptr = Ptr->Next; return Ptr != NULL; template <class ElemType> void ListItr<ElemType> : Insert( const ElemType & x ) / 插入操作。 Exception( Current = NULL, " The location is illegal!" ); ListNode<ElemType> *p; p = new ListNode<ElemType> ( x,Current->Next); Current = Current->Next=p; 10 template <class ElemType> int ListItr<ElemType> : Remove( const ElemType & x ) ListNode<ElemType> * Ptr = head; while ( Ptr->Next != NULL && !( Ptr->Next->Element = x) ) Ptr = Ptr->Next; if ( Ptr ->Next = NULL ) return 0; / 未找到数据值为x的结点，删除失败。 ListNode<ElemType> * P = Ptr->Next; Ptr->Next = Ptr->Next->Next; delete P; Current = head; return 1; template<class ElemType> const ElemType & ListItr<ElemType>:operator const Exception(Current=head,"The location is not correct!"); return Current->Element; template<class ElemType> void ListItr<ElemType>:operator + Exception(Current=NULL,"There is not next node!"); Current=Current->Next; template<class ElemType> const ListItr<ElemType>&ListItr<ElemType>:operator =(const ListItr<ElemType>&R) /符值运算符的实现。 if(this=&R)return*this; Exception(head!=R.reader,"Reference to another list,it is ERROR!"); Current=R.Current; return*this; template <class ElemType> const List<ElemType>& List<ElemType>:operator =(const List<ElemType> &R) /赋值运算符的实现 if(this=&R) return *this; MakeEmpty; ListItr<ElemType> Itr(*this); for(ListItr<ElemType> Ritr(R);+Ritr;Ritr+) 11 Itr.Insert(Ritr); return *this; template<class ElemType> void ListItr<ElemType>:First Exception(head->Next = NULL,"There is not first node!"); Current=head->getNext; /main.cpp #include "poly.h" main Term R(-1,-1); / 多项式输入的结束标志。 Polynomial<Term > a(R), b(R), c; cin >> a >> b; / 读入 2 个多项式，通过对 >> 重载实现。 c = a; / 多项式 a 并不破坏，将其值送入 c 暂存。 c * b; / 完成多项式c、b相乘，结果保存在多项式 c 之中。 cout << c; / 将多项式 c 输出。 return 0; 测试数据： (1X->1+3X->2)*(1X->2+2X->4) 预计运行结果：+1x->3+3x->4+2x->5+6x->6 测试及运行结果： Create a Polynomial! Please input coefficient and power exponent one by one! Create a coefficient and power exponent ! Please input a coefficient ! 1 Pease input a power exponent ! 1 Create a coefficient and power exponent ! Please input a coefficient ! 3 Please input a power exponent ! 2 Create a coefficient and power exponent ! Please input a coefficient ! -1 12 Please input a power exponent ! -1 Create a Polynomial! Please input coefficient and power exponent one by one! Create a coefficient and power exponent ! Please input a coefficient ! 1 Please input a power exponent ! 2 Create a coefficient and power exponent ! Please input a coefficient ! 2 Please input a power exponent ! 4 Create a coefficient and power exponent ! Please input a coefficient ! -1 Please input a power exponent ! -1 +1x->3+3x->4+2x->5+6x->6 Press any key to continue 运行结果分析： 运行结果符合预定目标 13