南邮数据结构实验一.doc

实 验 报 告（2014 / 2015 学年 第 二 学期）课程名称数据结构实验名称线性表的基本运算及多项式的算术运算实验时间2015年9月28日指导单位计算机科学与技术系指导教师黄海平学生姓名陈明阳班级学号Q14010119学院(系)贝尔英才专 业信息科技强化班实 验 报 告实验名称线性表的基本运算及多项式的算术运算指导教师黄海平实验类型验证实验学时4实验时间9.28一、 实验目的和要求内容：实现顺序表和单链表的基本运算，多项式的加法和乘法算术运算。要求：能够正确演示线性表的查找、插入、删除运算。实现多项式的加法和乘法运算操作。二、实验环境(实验设备)VSUAL STUDIO2015三、实验原理及内容LinearlistseqlistLA,LB函数调用数据类型如下图源码：Linearlist.h:#includeusing namespace std;template class LinearListpublic:virtual bool IsEmpty() const = 0;virtual int Length() const = 0;virtual bool Find(int i, T&x) const = 0;virtual int Search(T x) const = 0;virtual bool Insert(int i, T x) = 0;virtual bool Delete(int i) = 0;virtual bool Update(int i, T x) = 0;virtual void Output(ostream& out) const = 0;protected:int n;Seqlist.h:#includelinearlist.htemplateclass SeqList :public LinearListpublic:SeqList(int mSize);SeqList() delete elements; bool IsEmpty() const;int Length() const;bool Find(int i, T& x) const;int Search(T x) const;bool Insert(int i, T x);bool Delete(int i);bool Update(int i, T x);void Output(ostream& out)const;private:int maxLength;T *elements;templateSeqList:SeqList(int mSize)maxLength = mSize;elements = new TmaxLength;n = 0;templatebool SeqList:IsEmpty() constreturn n = 0;templateint SeqList:Length()constreturn n;templatebool SeqList:Find(int i, T& x)constif (in - 1)cout out of bounds endl; return false;x = elementsi;return true;templateint SeqList:Search(T x)constfor (int j = 0; j n; j+)if (elementsj = x)return j;return -1;templatebool SeqList:Insert(int i, T x)if (in - 1)cout out of bounds endl;return false;if (n = maxLength)cout over flow i; j-)elementsj + 1 = elementsj;elementsi + 1 = x;n+;return true;templatebool SeqList:Delete(int i)if (in - 1)cout out of bounds endl;return false;if (!n)cout over flow endl;return false;for (int j = i+1; j n; j-)elementsj -1 = elementsj;n-;return true;templatebool SeqList:Update(int i, T x)if (in - 1)cout out of bounds endl;return false;elementsi = x;return true;templatevoid SeqList:Output(ostream& out)constfor (int i = 0; i n; i+)out elementsi ;out endl;源.cpp:#includeseqlist.hconst int SIZE = 20;void main()SeqList LA(SIZE);int i = 0;for (i = 0; i5; i+) LA.Insert(i - 1, i);LA.Insert(-1, 10);LA.Output(cout);实现在线性表LA中插入0-4然后在一开始插入10运行截图如下：多项式实验：定义类如下 重构函数如下：源码：#includeusing namespace std;class Termpublic: Term(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 ostream& 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 *nxt) : coef(c), exp(e) link = nxt;Term* Term:InsertAfter(int c, int e) link = new Term(c, e, link); return link;ostream& operator(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 X val.exp; break; return out;class Polynominalpublic: Polynominal(); Polynominal(); void AddTerms(istream& in); void Output(ostream& out)const; void PolyAdd(Polynominal& r); void PolyMul(Polynominal& r);private: Term* theList; friend ostream& operator(istream&, Polynominal &); friend Polynominal& operator+(Polynominal &, Polynominal &); friend Polynominal& operator*(Polynominal &, Polynominal &);Polynominal:Polynominal() theList = new Term(0, -1); /头结点 theList-link = NULL; /单链表尾结点指针域为空Polynominal:Polynominal() Term* p = theList-link; while (p != NULL) theList-link = p-link; delete p; p = theList-link; delete theList;void Polynominal:AddTerms(istream & in) Term* q = theList; int c, e; for (;) cout Input a term(coef,exp):n c e; q = q-InsertAfter(c, e); if (0 = e) break; void Polynominal:Output(ostream& out)const int first = 1; Term *p = theList-link; for (; p != NULL & p-exp = 0; p = p-link) if (!first & (p-coef0) out +; first = 0; out *p; cout link; /p指向第一个要处理的结点 q = q1-link; /q1是q的前驱，p和q就指向两个当前进行比较的项 while (p != NULL & p-exp = 0)/对r的单循环链表遍历，知道全部结点都处理完 while (p-exp exp) /跳过q-exp大的项 q1 = q; q = q-link; if (p-exp = q-exp) /当指数相等时，系数相加 q-coef = q-coef + p-coef; if (q-coef = 0) /若相加后系数为0，则删除q q1-link = q-link; delete(q); q = q1-link; /重置q指针 else q1 = q; /若相加后系数不为0，则移动q1和q q = q-link; else /pexpq-exp的情况 q1 = q1-InsertAfter(p-coef, p-exp); /以p的系数和指数生成新结点，插入q1后 p = p-link; void Polynominal:PolyMul(Polynominal& r) Polynominal result; /定义相乘后的数据 Term *n = result.theList; /n指向result的头结点 n = n-InsertAfter(0, 0); /在result的头结点后插入新结点，系数指数均为0 Term *p = r.theList-link; /p指向第一个要处理的结点 while(p-exp = 0) /对r的单循环链表遍历 Polynominal tmp; /存储某段相乘后的数据 Term *m = tmp.theList; /m指向tmp的头结点 Term *q = theList-link; /q指向表头结点的后继结点 while(q-exp = 0) /对当前对象的单循环环链表遍历 m = m-InsertAfter(p-coef)*(q-coef), (p-exp) + (q-exp); /生成新结点插入n后 q = q-link; result.PolyAdd(tmp); /将temp加到result上 p = p-link; Term *q = theList-link; /q指向表头结点的后继结点 while(q != NULL) /删除原对象的所有数据 theList-link = q-link; delete q; q = theList-link; q = theList; q = q-InsertAfter(0, 0); PolyAdd(result); /将result加到当前对象上ostream &operator(istream& in, Polynominal &x) x.AddTerms(in); return in;Polynominal & operator + (Polynominal &a, Polynominal &b) a.PolyAdd(b); return a;Polynominal & operator * (Polynominal &a, Polynominal &b) a.PolyMul(b); return a;int main() int choose; cout choose calculate type 1.add 2.mul choose; Polynominal p, q; switch (choose) case 1: cin p; cout q; cout p; cout q; co