南邮数据结构上机实验一线性表的基本运算和多项式的基本运算讲述.doc

实 验 报 告 （/ 2016学年 第学期） 课程名称 实验名称 实验时间 2016 年 月 日 指导单位 系 指导教师 学生姓名 班级学号 学院(系) 专 业 实习题名:线性表的基本运算 班级 姓名 学号 日期2016.03.10 问题描述 深入理解线性表数据结构,熟练掌握顺序表的各种基本操作。在顺序表类SeqList中增加成员函数void Reverse()，实现顺序表的逆置；在顺序表类SeqList中增加成员函数bool DeleteX(const T x),删除表中所有元素值等于x元素。若表中存在这样的元素，则删除之，且函数返回true，否则函数返回false。 概要设计 文件Inverse.cpp中定义了Linearlist类, SeqList类继承Linearlist类。在顺序表类SeqList中通过函数void Reverse()实现顺序表的逆置，通过函数bool DeleteX(const T x),删除表中所有元素值等于x元素。 详细设计 类和类的层次设计 程序使用了两个类, 线性表Linearlist类和顺序表SeqList类和一个主函数mian。Linearlist类里包括常见的线性表运算,在类SeqList里面新增成员函数void Reverse()和bool DeleteX(const T x)。 核心算法 顺序表SeqList类中,私有段封装了两个私有数据成员maxLength和elements,公有段封装了构造、析构、查找、删除、逆置等函数。实现要求的主要操作通过void Reverse()和bool DeleteX(const T x)实现，void Reverse()通过前后互换实现逆置， bool DeleteX(const T x)使用hash数组标记需要删除的元素，然后将放在elements里面的数据删除。两个函数的流程图如下。 void Reverse() bool DeleteX(const T x) 算法分析 线性表的基本运算程序的主要算法的算法时间复杂度和空间复杂度为O（n） 四、程序代码 void SeqListT::Reverse() { T temp; //临时变量存放数据 for(int i = 0; i n / 2; i++) //前后互换逆置 { temp = elements[i]; elements[i] = elements[n - i - 1]; elements[n - i - 1] = temp; } } templateclass T bool SeqListT::DeleteX(const T x) { int tmp = n, i; //用于判断是否有删除数据 n = 0; int *hash = new int[tmp]; for(i = 0; i tmp; i++) { hash[i] = 0; if(elements[i] == x) hash[i]++; } for(i = 0; i tmp; i++) if(!hash[i]) elements[n++] = elements[i]; delete[]hash; if(n == tmp) //判断是否有删除的数据 return false; else return true; } 重新输入需要删除的数据4,24，如图所示只删除了4 结果分析 程序能够正确的实现顺序表的逆置以及删除特定值的元素 由测试结果来看，数据无法实现两个数的同时删除，还有改进的空间 六、实验小结 通过这次课程设计，使我对数据结构有了初步的清晰了解，增强了程序的编写能力，在程序的运行与调试过程中出现了很多错误，通过反复地复习课本上的相关知识，不停地修改与调试，终于完成了这段程序。在调试过程中，我认识到了数据结构的灵活性与严谨性，同一个功能可以由不同的语句来实现，但编写程序时要特别注意细节方面的问题，因为一个小小的疏忽就能导致整个程序不能运行。我也认识到了自己的薄弱之处，如对c++和链表知识不够熟悉，在以后的学习中我们要集中精力、端正态度，争取把知识学得更扎实、更全面。 实习题名:多项式的基本运算 班级 姓名 学号 日期2016.03.10 问题描述 设计带表