南邮数据结构实验一

1、实验报告（2014 / 2015学年第二学期）课程名称数据结构实验名称线性表的基本运算及多项式的算术运算实验时间2015年 9 月 28 日指导单位计算机科学与技术系指导教师黄海平学生姓名陈明阳班级学号Q14010119学院（系）贝尔英才专 业 信息科技强化班实验报告实验名称线性表的基本运算及多项式的算术运算指导教师黄海平实验类型验证实验学时4实验时间9.28一、实验目的和要求内容：实现顺序表和单链表的基本运算，多项式的加法和乘法算术运算。要求：能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。二、实验环境（实验设备）VSUAL STUDIO2015三、实验原理及内容L

2、inearlis_ jseqlisL_LA 丄B.函数调用数据类型如下图§ Delete(mt i)Find(int ir T & x) const妙 |nsert(int ir T x)1 IsEmptyQ const卡 LengthQ const齐 Output(o£tream & out)匚oust 0 SearchCT x) const学 Update(int L T x)源码：_Lin earlist.h:#inelude <iostream>using namespacestd;template < class T>cla

3、ss Lin earListpublic : |virtual bool lsEmpty() const = 0;virtual int Length() const = 0;virtualbool Find( int i,T&x) const = 0;virtualint Search( T x) const = 0;virtualboolInsert(inti,T x) =0;virtualboolDelete(inti)= 0;virtualboolUpdate(inti,T x) =0;virtual void Output( ostream & out) const

4、= 0;protected :int n;Seqlist.h:#include "linearlist.hItemplate <class T>class SeqList : public LinearList <T> public :SeqList( int mSize);SeqList() delete elements; bool lsEmpty() const;int Length()const;bool Find( int i, T& x) const;int Search( T x) con st;boolInsert(inti,T x);

5、boolDelete(inti);boolUpdate(inti,T x);voidOutput( ostream & out) const ;private :int maxLength;T *eleme nts;template <class T>SeqList <T>:SeqList( int mSize)maxLe ngth = mSize;elements = new TmaxLength;n = 0;template <class T>bool SeqList <T>:IsEmpty() constreturn n = 0;t

6、emplate <class T>nt SeqList <T>:Length() constreturn n;template <class T>bool SeqList <T>:Find( int i , T& x) constif ( i <0 | i >n - 1)falsecout << "out of bounds"<< endl; returnx = elements i ;return true ;template vclass T>int SeqList <

7、;T>:Search( T x) constfor (int j = 0; j < n; j+)if (elementsj =x) return j;return -1;template <class T>bool SeqList <T>:Insert( int i , T x)if ( i <-1 | i >n - 1)cout << "out of bounds"<< endl;return false ;if (n = maxLength)cout << "over flow

8、"<< endl;return false ;for (int j = n -1; j >i; j-)eleme ntsj + 1 = eleme ntsj;elements i + 1 = x;n+;return true ;template <class T>bool SeqList <T>:Delete( int i)if ( i <0 | i >n - 1)cout << "out of bounds"<< endl;returnfalse ;if(!n)cout<<

9、 "over flow"<< en dl;returnfalse ;for (int j = i +1; j <n; j-)elementsj -1 = elementsj;n-;return true ;template <class T>bool SeqList <T>:Update( int i , T x)if(i <0 | i >n - 1)cout << "out of bounds"<< endl;return false ;elements i = x;retu

10、rn true ;template <class T>void SeqList <T>:Output( ostream & out )constfor (int i = 0; i < n; i+) out << elementsi <<""out << endl;源.cpp:#include "seqlist.h"const int SIZE = 20;void main()SeqList <int > LA(SIZE);int i = 0;for (i = 0; i&

11、lt;5; i+) LA.Insert(i - 1, i);LA.I nsert(-1, 10);LA.Output(cout);实现在线性表LA中插入0-4然后在一开始插入10运行截图如下：多项式实验：定义类如下-PolynominalQI AddTermsfistream & in)却 ConsoleApplicationJ 9全局函数和变星 作 Polynominal TermL1 Outputfostream & out) const 5' PolyAdd (Polyno mi na I & r) 屮 PolyMul(Polynominal &

12、r) 叨 PolynominalOd. theLi&t3 lnsertAfter(int c, int e) j Ternn(int ©int e); Term(int c, int er Term 土 nxt)J. coef气exp气 link重构函数如下:friend ostrearofe peratarH('C(o3ti'g/inconst Polynominal &);friend istreair operator,»(istrearr PolyrLOiTinal 及)；friend PolynoTninal- operat.or+

13、CPoLynoiriinal &, Polynonunal &); friend Polynominalfe op er ator* (Polynominal fe, Polynominal &):源码：#inelude <iostream> using namespacestd;class TermTerm( 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 ost

14、ream & 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 *n xt) : coef( c), exp( e) link = nxt ;Term* Term:lnsertAfter( int c, int e)link = new Term(c, e, link);return link;ostream& operato

15、r<< (ostream & out, const Term& val) if (0 = val .coef)return out;if (1!= val .coef)out << val .coef;switch ( val .exp)case 0: break;case 1: out << "X" ; break;default : out << "XA" << val .exp; break;return out;class Polynominalpublic :"

16、;|Poly nomin al();Poly no mi nal();void AddTerms( istream & in);void Output( ostream & out) const;void PolyAdd( Polynominal & r);voidPolyMul( Polynominal & r); Jprivate :Term* theList;friend ostream & operatorvv (ostream &, const Polynominal &); friend istream & opera

17、tor>> (istream &, Polynominal &);friend Polynominal & operator* (Polynominal &, Polynominal &); friend Polynominal & operator* (Polynominal &, Polynominal &);Polynominal : Polynomin al()theList =new Term(0, -1);/头结点theList->li nk=NULL/单链表尾结点指针域为空Polynominal :

18、Polynominal() Term* p = theList->li nk;while (p != NULLtheList->li nk = p->li nk; delete p;p = theList->li nk;delete theList;void Polynominal :AddTerms( istream & in ) Term* q = theList;int c, e;for (;)cout<< "Input a term(coef,exp):n"<< en dl;cin>> c >

19、> e;q = q->l nsertAfter(c, e);if (0 >= e) break; void Polynominal :Output( ostream& out) constint first = 1;Term*p = theList->li nk;for (; p !=NULL&& p->exp >= 0; p = p->link)if (!first && (p->coef>0)out << "+"cout<< en dl;q1指向表头结点

20、void Polynominal :PolyAdd( Polynominal & r) Term*q, *q1 = theList, *p;p =r .theList->li nk;/p指向第一个要处理的结点q = q1->li nk;q1是q的前驱，p和q就指向两个当前进行比较的项while (p !=NULL&& p->exp >= 0) /对r的单循环链表遍历，知道全部结点都处理完while (p->exp < q->exp)/跳过q->exp大的项q->exp)/当指数相等时，系数相加q->coef =

21、 q->coef + p->coef;/若相加后系数为0,则删除qif (q->coef = 0) q1->li nk = q->li nk;delete (q);q = q1->link;/ 重置 q指针elsep>exp>q->exp 的情况q1 = q1->InsertAfter(p->coef, p->exp);/以p的系数和指数生成新结点，插入 q1后p = p->li nk;m = m_>lnsertAfter(p->coef)*(q->coef), (p->exp) + (q-&

22、gt;exp);/ 生成新结点插入 n后void Pol yno mi nal :PolyMul( Poly no mi nal & r) Polynominal result;/疋义相乘后的数据Term* n = result.theList;n指向result的头结点n = n->1 nsertAfter(0, 0);/在result的头结点后插入新结点，系数指数均为0Term*p =r .theList->li nk;/p指向第一个要处理的结点while (p->exp >= 0)/对r的单循环链表遍历Polynominal tmp;/存储某段相乘后的数据

23、Term *m = tmp.theList;/m指向tmp的头结点Term *q = theList->li nk;/q指向表头结点的后继结点while (q->exp >= 0)/对当前对象的单循环环链表遍历q = q->li nk;result.PolyAdd(tmp);/ 将temp加到 result 上p = p->li nk;Term*q = theList->li nk;/q指向表头结点的后继结点while (q != NULL/删除原对象的所有数据theList->li nk = q->li nk;delete q;q = theL

24、ist->li nk;q = theList;q = q->l nsertAfter(O, 0);PolyAdd(result);/将result加到当前对象上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 +( Po"nominal &a. Polynominal &b)a.PolyAdd( b);return a;Polynominal & operator *( Polynomin