数据结构 多项式乘法.docx

《数据结构 多项式乘法.docx》由会员分享，可在线阅读，更多相关《数据结构 多项式乘法.docx（17页珍藏版）》请在三一办公上搜索。

1、数据结构 多项式乘法 实习报告 一、实习题： 请写出计算两个以单链接表表示的多项式相乘的程序。 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;

2、排列结果：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; f

3、riend 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 ( istream & is, Term & T ); friend ostream & operator ( ostream & os, const Term & T ); friend char compare( const Term & P, const Term & T ); friend Is_Empty(

4、const Term & T ) return !T.coef; ; /多项式类 template 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); frie

5、nd istream & operator ( istream & is, Polynomial & T ); friend ostream & operator ( ostream & os, const Polynomial & T ); private: List poly; ElemType Stop_flag; / 用于判断多项式输入结束。 ; 算法思想： 用两个单链表的存储两个多项式，每个结点包含单项式的系数，幂和指向下一个元素地址的指针。用其中的一个多项式中的每一项乘以另一个多项式，将得到的若干个多项式中的每一项按照幂次的顺序相加。即幂数相等项的系数相加，最后得到结果。 调用关系

6、： 程序有三个文件，list.h, poly.h，main.cpp,文件poly.h调用list.h。文件main.cpp调用poly.h。 算法实现框架： 2 声明两个Polynomial类的多项式 用一个多项式中的每一个单项式去乘以另一个多项式，得若干个多项式。 将得到的若干个多项式中的每一项按照幂次的顺序相加。即幂数相等项的系数相加，然后升幂排列 得运算结果。 3用户手册： 运行程序，按照屏幕提示按幂次由低到高的顺序输入两个多项式，以作为结束标志。两个多项式输入完毕后，程序自动显示两个多项式相乘的结果。 4调试报告： 时间复杂度分析： 假设两个多项式的单项式个数分别为m和n。先用A多项式

7、去乘以B多项式的每一项时，得到m个项数为n的多项式，完成这一步的时间复杂度为O。然后进行相加的步骤，按照时间复杂度的求和定理，整个程序的时间复杂度为O。 算法改进思路： 可以参考首项相乘的幂和末项项乘的幂，即最大次幂n和最小次幂m，取m=i=n,对i循环，对i的每一个值寻找多项式相乘的幂对应项，最后对所有项求和表示即可。但其时间复杂度要更大，在某些情况下可以参考。 5附录 源程序清单 3 /poly.h #include #include listdefine.h /单项式结构 struct Term float coef; / 系数。 int exp; / 幂指数。 Term( float

8、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 ( istream & is, Term & T ); friend ostream &

9、 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 (PT) return ; istream & operator ( istream &is, Term &T ) cout Create a coeffic

10、ient and power exponent ! n; coutT.coef; coutT.exp; return is; ostream & operator 0) os +; os T.coef T.exp; return os ; /多项式类 template class Polynomial public: Polynomial (const ElemType &P) Stop_flag=P; Polynomial ( ) Polynomial ( ) Polynomial & operator = ( const Polynomial & T ); / Polynomial & o

11、perator + ( const Polynomial & T); Polynomial & operator*( const Polynomial &T); friend istream & operator ( istream & is, Polynomial & T ); friend ostream & operator ( ostream & os, const Polynomial & T ); private: List poly; ElemType Stop_flag; / 用于判断多项式输入结束。 ; template istream & operator ( istrea

12、m & is, Polynomial & T ) ElemType elem; ListItr Itr(T.poly); cout Create a Polynomial! n; cout elem,!equal_stop(elem,T.Stop_flag) Itr.Insert(elem); return is; template ostream & operator ( ostream & os, const Polynomial & T ) if (T.poly ).IsEmpty( ) os Polynomial is Empty!n; else for (ListItrItr(T.p

13、oly);+Itr;+Itr) osItr ; return osn; 5 template Polynomial& Polynomial:operator Polynomial &T) if(this=&T) return *this; poly.MakeEmpty; ListItr ItrT(T.poly); ListItr ItrThis(poly); for(;+ItrT;+ItrT) ItrThis.Insert(ItrT); return *this; template Polynomial& Polynomial:operator Polynomial &T) ElemType

14、elemA,elemB; Polynomial C; ListItr ItrA(poly); ListItr ItrB(T.poly); ListItr 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

15、=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;ik;+i) +ItrC; ItrC.Insert(elemA); k=-1; break; if(!+ItrC&k!=-1) if(C.poly).IsEmpty) ItrC.Insert(elemA); else ItrC.Find(a); ItrC.Inse

16、rt(elemA); *this=C; return *this; /listdefine.h #include void Exception(int Condition, const char* ErrorMsg) if(Condition) cerr ErrorMsg endl; 7 /单链表节点类 template class AbsListItr; template class AbsList public: AbsList; virtual AbsList; virtual IsEmpty const=0; virtual IsFull const=0; virtual void M

17、akeEmpty=0; friend class AbsListItr ; private: AbsList(const AbsList &) ; template class AbsListItr public: AbsListItr(const AbsList&L) AbsListItr(const AbsListItr &); virtual AbsListItr virtual void Insert(const ElemType &x)=0; virtual int Remove(const ElemType &x)=0; virtual int Find(const ElemTyp

18、e &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 List; / 单链表类的向前说明。 template

19、 class ListItr; / 单链表迭代器类的向前说明。 template class ListNode friend class List ; / 单链表类为其友元类, 便于访问结点类中的私有成员。 8 friend class ListItr ; / 单链表迭代器类为其友元类, 便于访问结点类中的私有成员。 private: ElemType Element; / 结点数据。 ListNode * Next; / 指向下一个结点的指针。 public: ListNode (const ElemType &E, ListNode *N=NULL):Element(E),Next(N)

20、/ 构造函数 ListNode * getNextreturn Next; ListNode( ) : Next( NULL ) / 构造函数 ListNode ( ) ; / 析构函数 ; /单链表类 template class ListItr; / 单链表迭代器类的向前说明。 template class List : public AbsList friend class ListItr ; / 单链表迭代器类为其友元类。 private: ListNode * head; / 指向头结点的指针。 public: List( ) head = new ListNode( ); List

21、( ) MakeEmpty( ); delete head; / 析构函数 const List & operator=(const List &R); / 完成复制功能。 int IsEmpty( ) const return head-Next = NULL; int IsFull( ) const return 0; void MakeEmpty( ); ; template void List :MakeEmpty ListNode *Ptr; ListNode *NextNode; for(Ptr=head-Next;Ptr!=NULL;Ptr=NextNode) NextNode=

22、Ptr-Next; delete Ptr; head-Next=NULL; template class ListItr : public AbsListItr private: ListNode *const head; / 指向头结点的常指针。 9 ListNode *Current; / 指向当前结点的指针。 public: ListItr( const List & L) : head( L.head ) Current = L.IsEmpty( ) ? head : head-Next; ListItr( ) / 析构函数 int Find( const ElemType & x )

23、; / 查找值为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; / 当前结点非空则返回T

24、rue。 const ElemType & operator ( ) ( ) const; / 取当前结点的数据值。 void operator + ( ); / 使当前结点的直接后继结点成为当前结点。 void operator + (int) operator+( ); / 定义为前缀+运算符。 void Zeroth ( ) Current=head; / 当前指针指向头结点。 void First( ); / 当前指针指向首结点。 const ListItr & operator=(const ListItr &); ; template int ListItr : Find( con

25、st ElemType & x ) ListNode * Ptr = head-Next; while (Ptr!=NULL & !(Ptr-Element=x) Ptr=Ptr-Next; if (Ptr = NULL) return 0; Current = Ptr; return 1; template int ListItr : IsFound( const ElemType & x ) const ListNode * Ptr = head-Next; while ( Ptr != NULL & !( Ptr-Element = x) ) Ptr = Ptr-Next; return

26、 Ptr != NULL; template void ListItr : Insert( const ElemType & x ) / 插入操作。 Exception( Current = NULL, The location is illegal! ); ListNode *p; p = new ListNode ( x,Current-Next); Current = Current-Next=p; 10 template int ListItr : Remove( const ElemType & x ) ListNode * Ptr = head; while ( Ptr-Next

27、!= NULL & !( Ptr-Next-Element = x) ) Ptr = Ptr-Next; if ( Ptr -Next = NULL ) return 0; / 未找到数据值为x的结点，删除失败。 ListNode * P = Ptr-Next; Ptr-Next = Ptr-Next-Next; delete P; Current = head; return 1; template const ElemType & ListItr:operator const Exception(Current=head,The location is not correct!); ret

28、urn Current-Element; template void ListItr:operator + Exception(Current=NULL,There is not next node!); Current=Current-Next; template const ListItr&ListItr:operator =(const ListItr&R) /符值运算符的实现。 if(this=&R)return*this; Exception(head!=R.reader,Reference to another list,it is ERROR!); Current=R.Curre

29、nt; return*this; template const List& List:operator =(const List &R) /赋值运算符的实现 if(this=&R) return *this; MakeEmpty; ListItr Itr(*this); for(ListItr Ritr(R);+Ritr;Ritr+) 11 Itr.Insert(Ritr); return *this; template void ListItr:First Exception(head-Next = NULL,There is not first node!); Current=head-g

30、etNext; /main.cpp #include poly.h main Term R(-1,-1); / 多项式输入的结束标志。 Polynomial a(R), b(R), c; cin a b; / 读入 2 个多项式，通过对 重载实现。 c = a; / 多项式 a 并不破坏，将其值送入 c 暂存。 c * b; / 完成多项式c、b相乘，结果保存在多项式 c 之中。 cout 1+3X-2)*(1X-2+2X-4) 预计运行结果：+1x-3+3x-4+2x-5+6x-6 测试及运行结果： Create a Polynomial! Please input coefficient

31、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

32、 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