实 验 报 告
（ 2015 / 2016学年 第二学期）
课程名称
数据结构A
实验名称 线性表的基本运算和多项式的基本运算
实验时间 指导单位 指导教师
2016 年 3 月 10 日
计算机科学与技术系
骆健
学生姓名 学院(系)
管理学院
班级学号 专 业
信息管理与信息系统
实习题名:线性表的基本运算
班级 姓名 学号 日期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元素。
三、 详细设计
1. 类和类的层次设计
程序使用了两个类, 线性表Linearlist类和顺序表SeqList类和一个主函数mian。Linearlist类里包括常见的线性表运算,在类SeqList里面新增成员函数void Reverse()和bool DeleteX(const T &x)。
T 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 void Output(ostream& out) const = 0; T SeqList -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); 2. 核心算法
顺序表SeqList类中,私有段封装了两个私有数据成员maxLength和elements,公有段封装了构造、析构、查找、删除、逆置等函数。实现要求的主要操作通过void Reverse()和bool DeleteX(const T &x)实现，void Reverse()通过前后互换实现逆置， bool DeleteX(const T &x)使用hash数组标记需要删除的元素，然后将放在elements里面的数据删除。两个函数的流程图如下。
临时变量存放数据 int i=0 Ni<=n/2 Y前后互换逆置 i++ void Reverse()
int tmp=n,i i=0 N i