南邮数据结构上机实验一线性表的基本运算和多项式的基本运算资料

1、实验报告2015 / 2016 学年 第二学期）课程名称数据结构 A实验名称线性表的基本运算和多项式的基本运算实验时间2016年3月10 日指导单位计算机科学与技术系指导教师骆健学生姓名学院(系)管理学院班级学号专业信息管理与信息系统实习题名:线性表的基本运算班级姓名学号日期2016.03.10一、问题描述深入理解线性表数据结构, 熟练掌握顺序表的各种基本操作。在顺序表类SeqList中增加成员函数void Reverse()，实现顺序表的逆置；在顺序表类SeqList中增加成员函数 bool DeleteX(const T &x),删除表中所有元素值等于x 元素。若表中存在这样的元素，则删除

2、之，且函数返回true ，否则函数返回false 。二、概要设计文件 Inverse.cpp中定义了Linearlist类 , SeqList类继承 Linearlist序表类 SeqList中通过函数void Reverse()实现顺序表的逆置，通过函数DeleteX(const T &x),删除表中所有元素值等于x 元素。类。在顺bool三、详细设计1.类和类的层次设计程序使用了两个类,线性表 LinearlistLinearlist类里包括常见的线性表运算, 在类类和顺序表SeqList类和一个主函数mian 。SeqList里面新增成员函数void Reverse()和bool Del

3、eteX(const T &x)。TLinearlist#int n+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

4、(ostream& out) const = 0;TSeqList-int maxLength;-T *elements;+IsEmpty() const;+Length() const;+Find(int i,T& x) const;+Search(T x) const;+Insert(int i,T x);+Delete(int i);+Update(int i,T x);+Output(ostream& out) const;+Reverse();+DeleteX(const T& x);核心算法顺序表 SeqList类中 , 私有段封装了两个私有数据成员maxLength 和 elem

5、ents,公有段封装了构造、析构、查找、删除、逆置等函数。实现要求的主要操作通过void Reverse()和bool DeleteX(const T &x)实现，void Reverse()通过前后互换实现逆置，boolDeleteX(constT &x) 使用hash数组标记需要删除的元素，然后将放在elements里面的数据删除。两个函数的流程图如下。临时变量存放数据int i=0Ni=n/2Y前后互换逆置i+void Reverse()int tmp=n,ii=0NitmpYhashi=0elementsi=xYNhashi+i+i=0NitmpYelementsn+=elements

6、ii+删除 hashNn=tmpYreturn falsereturn falsebool DeleteX(const T &x)算法分析线性表的基本运算程序的主要算法的算法时间复杂度和空间复杂度为O（ n）四、程序代码void SeqList:Reverse()T temp;/临时变量存放数据for(int i = 0; i n / 2; i+)/ 前后互换逆置temp = elementsi;elementsi = elementsn - i - 1;elementsn - i - 1 = temp;templatebool SeqList:DeleteX(const T& x)int t

7、mp = n, i;/ 用于判断是否有删除数据n = 0;int *hash = new inttmp;for(i = 0; i tmp; i+)hashi = 0;if(elementsi = x)hashi+;for(i = 0; i expYNp-expexpYq1=qNp-exp=q-exYq-coef=q-coef+p-coeNq-coef=0Yq1=q重置 q 指针以 p 的系数和指数生成新结点插入 q1 后p=p-linkPolyAdd(Polynominal& r)定义相乘后的数据Np-exp=0Y存储某段相乘后的数据Nq-exp=0Y生成新节点插入n 后将 temp 加到 r

8、esult 上指向表头结点的后继结点Nq!=NULLY删除原对象的所有数据将 result 加到当前对象上PolyMul(Polynominal& r)算法分析多项式的加法和乘法算术运算程序的主要算法的时间复杂程度和和空间复杂程度为 O（n）。四、程序代码void Polynominal:PolyAdd(Polynominal& r)Term *q, *q1 = theList, *p;p = r.theList-link;q = q1-link;/q1 指向表头结点/p 指向第一个要处理的结点/q1 是 q 的前驱， p 和 q 就指向两个当前进行比较的项while (p != NULL &

9、 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，则删除qq1-link = q-link;delete(q);q = q1-link;/ 重置q 指针elseq1 = q;/若相加后系数不为0，则移动q1 和qq = q-link;else/pexpq-exp的情况q1 = q1-InsertAfter(p-coef,

10、 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的头结点后插入新结点，系数指数均为0Term *p = r.theList-link;while(p-exp = 0)/p 指向第一个要处理的结点/对 r 的单循环链表遍历Polynominal tmp;/ 存储某段相乘后的数

11、据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)/ 删除原对象的所有数据th

12、eList-link = q-link;delete q;q = theList-link;q = theList;q = q-InsertAfter(0, 0);PolyAdd(result);/ 将 result 加到当前对象上五、测试和调试测试用例和结果选择 1, 计算多项式相加2)分别输入系数和项数3 2,4 6,9 7,如图所示得到相加的多项式如图选择 2, 计算多项式相乘5)输入系数和项数4 2,6 3,得到多项式一 , 如图再次输入系数和项数 7 3, 得到多项式二以及多项一和多项式二的乘积结果分析程序能够正确实现多项式的相加以及相乘但是程序无法实现不能加法乘法混用，下一步改进方

13、向是实现加法乘法混用，是计算更加简便六、实习小结这个实验的重难点都在于正确灵活使用，大部分代码在书上都有提供，真正的操作重点在于理解这些代码的意义和使用方法。通过这次课程设计，使我对数据结构有了初步的清晰了解， 增强了程序的编写能力，巩固了专业知识，对程序的模块化观念也又模糊逐渐变的清晰了。 在程序的运行与调试过程中出现了很多错误，通过反复地复习课本上的相关知识，不停地修改与调试，终于完成了这段程序。在调试过程中， 我认识到了数据结构的灵活性与严谨性， 同一个功能可以由不同的语句来实现，但编写程序时要特别注意细节方面的问题，因为一个小小的疏忽就能导致整个程序不能运行。我也认识到了自己的薄弱之处

14、，如对c+ 和链表知识不够熟悉，在以后的学习中我们要集中精力、端正态度，争取把知识学得更扎实、更全面。经过这次的实验，我在各个方面都得到了不少的提高，我希望多几次像这样的实验让我们更好的锻炼自己。附录：线性表的基本运算#include using namespace std;int const LEN = 50;template class LinearListpublic:virtual bool IsEmpty() const = 0;virtual int Length() const = 0;virtual bool Find(int i,T& x) const = 0;virtual

15、 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;/ 线性表的长度;template class SeqList: public LinearListprivate:int maxLength;T *elements;public:/线性表的最大长度/动态一维数组的指针Se

16、qList(int mSize);SeqList()deleteelements;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;void Reverse();bool DeleteX(const T& x);template SeqList:SeqList(int mSi

17、ze)maxLength = mSize;elements = new TmaxLength; / 动态分配顺序表的存储空间 n = 0;template bool SeqList:IsEmpty() constreturn n = 0;template int SeqList:Length() constreturn n;template bool SeqList:Find(int i, T& x) constif(i n - 1)cout Out of Bounds endl;/对 i 进行越界检查return false;x = elementsi;return true;templat

18、eint 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(i n - 1)cout Out Of Bounds endl;return false;if(n = maxLength)cout OverFlow i; j-)elementsj + 1 = elementsj;elementsi + 1 = x;n+;return true;template bool SeqList:Delete

19、(int i)if(!n)cout UnderFlow endl;return false;if(i n - 1)cout Out Of Bounds endl;return false;for(int j = i + 1; j n; j+)elementsj - 1 = elementsj;n-;return true;template bool SeqList:Update(int i,T x)if(i n - 1)coutOut Of Boundsendl;return false;elementsi = x;return true;template void SeqList:Outpu

20、t(ostream& out)constfor(int i = 0; i n; i+)out elementsi ;out endl;template void SeqList:Reverse()T temp;/临时变量存放数据for(int i = 0; i n / 2; i+)/ 前后互换逆置temp = elementsi;elementsi = elementsn - i - 1;elementsn - i - 1 = temp;templatebool SeqList:DeleteX(const T& x)int tmp = n, i;/ 用于判断是否有删除数据n = 0;int *

21、hash = new inttmp;for(i = 0; i tmp; i+)hashi = 0;if(elementsi = x)hashi+;for(i = 0; i tmp; i+)if(!hashi)elementsn+ = elementsi;deletehash;if(n = tmp)/ 判断是否有删除的数据return false;elsereturn true;int main()int del_data, len ,num;SeqList A(LEN);cout len;cout nInput each element: ;for(int i = 0; i num;A.Ins

22、ert(i - 1, num);cout nInitial seqlist: ;A.Output(cout);A.Reverse();cout nResevered seqlist: ;A.Output(cout);cout del_data;if(A.DeleteX(del_data) = true)cout nSeqlist after being deleted: ;A.Output(cout);elsecout nNot found endl;return 0;多项式的基本运算#includeclass Termpublic:Term(int c, int e);Term(int c,

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

24、 c, int e)link = new Term(c, e, link);return link;ostream& operator(ostream& out, const Term& val)if (val.coef=0)return out;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&

25、 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:P

26、olynominal()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,ex

27、p):n c e;q = q-InsertAfter(c, e);if (0 e) break;void Polynominal:Output(ostream& out)constint 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;q = q1-link;/p指向第一个要处理的结点/q1 是 q 的前驱， p 和 q 就指向两个当前进行比较的项while (p != NULL &

28、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，则删除qq1-link = q-link;delete(q);q = q1-link;/ 重置q 指针elseq1 = q;/若相加后系数不为0，则移动q1 和qq = 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-I