《南邮数据结构上机实验一线性表的基本运算和多项式的基本运算剖析》由会员分享，可在线阅读，更多相关《南邮数据结构上机实验一线性表的基本运算和多项式的基本运算剖析（26页珍藏版）》请在金锄头文库上搜索。
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()实现顺序表的逆置，通过函数bool DeleteX(const T &x),删除表中所有元素值等于x元素。三、 详细设计1. 类和类的层次设计程序使用了两个类, 线性表Linearlist类和顺序表SeqList类和一个主函数mian。Linearlist类里包括常见的线性表运算,在类SeqList里面新增成员函数void Reverse()和bool
3、 DeleteX(const T &x)。Linearlist#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 vo
4、id Output(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);T2. 核心算法顺序表SeqList类中,私有段封装了两个私有数据成员maxLen
5、gth和elements,公有段封装了构造、析构、查找、删除、逆置等函数。实现要求的主要操作通过void Reverse()和bool DeleteX(const T &x)实现，void Reverse()通过前后互换实现逆置， bool DeleteX(const T &x)使用hash数组标记需要删除的元素，然后将放在elements里面的数据删除。两个函数的流程图如下。YYNY临时变量存放数据int i=0i=n/2i+前后互换逆置void Reverse()return false删除hashn=tmpreturn falseNYi+elementsn+=elementsiNYi=0
6、itmpelementsi=xhashi=0hashi+i+int tmp=n,ii=0itmpYNNYbool DeleteX(const T &x)3. 算法分析线性表的基本运算程序的主要算法的算法时间复杂度和空间复杂度为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:Dele
7、teX(const T& x) int tmp = n, i; /用于判断是否有删除数据 n = 0; int *hash = new inttmp; for(i = 0; i tmp; i+) hashi = 0; if(elementsi = x) hashi+; for(i = 0; i exp=0q1=qp-exp=q-expq-coef=q-coef+p-coefq-coef=0重置q指针p=p-linkp-expexpq1=q以p的系数和指数生成新结点插入q1后PolyAdd(Polynominal& r)YN定义相乘后的数据p-exp=0存储某段相乘后的数据q-exp=0生成新节
8、点插入n后将temp加到result上q指向表头结点的后继结点q!=NULL删除原对象的所有数据将result加到当前对象上NYNYPolyMul(Polynominal& r)3. 算法分析多项式的加法和乘法算术运算程序的主要算法的时间复杂程度和和空间复杂程度为O（n）。四、 程序代码void Polynominal:PolyAdd(Polynominal& r) Term *q, *q1 = theList, *p; /q1指向表头结点 p = r.theList-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) /若相
