(此文档为word格式，下载后您可任意编辑修改！)江西理工大学软件学院计算机类课程实验报告课程名称：数据结构班级：姓名：学号：江西理工大学软件学院实验二：顺序表2012年11月10日一. 实验目的掌握顺序表的逻辑结构、存储结构、以及操作。

二. 问题描述线性表是由n(n≥0)个元素（结点）a1, a2, …, a n组成的有限序列，其中a i中的i称为该数据元素的位置（序号），n为数据元素的个数（表的长度），当n等于0时称为空表。

按逻辑次序依次把数据元素存放在一组连续的地址存储单元里的线性表称为顺序表。

在这里，我们通过C++中的动态数组来实现顺序表的存放，并通过建立顺序表类实现它的各种操作。

三. 实验要求实现顺序表的三个框架操作：随机生成，用已有顺序表初始化另一个顺序表，输入顺序表。

以及十个基本操作：在第i个元素之前插入元素，判断是否为空，求元素个数，取第i个元素，查找第一个与e满足compare()关系的元素，返回元素的前驱，返回后继，删除第i个元素，把一个顺序表赋值给另一个顺序表，置空顺序表。

四. 实验环境3323机房OS：WxpC环境：1、TC2.02、VC++ 6.0 五．运行结果程序开始界面1.随机生成顺序表（元素值为0到99之间的整数）2. 用已有的顺序表初始化另一个顺序表3. 输入顺序表基本操作：1.在第i个元素之前插入一个元素2. 判断顺序表是否为空3. 求顺序表中元素的个数4. 取第i个元素5. 查找第一个与之满足compare()关系的元素序号6. 返回某元素的前驱7. 返回某元素的后继8. 删除第i个元素9. 把一个顺序表复制给另一个顺序表10. 把顺序表置空11.顺序表的运用六．实验心得熟悉最基本的数据类型——顺序表，同时我们让我们熟练C++的基本操作，模板的使用，以及模块化的设计思想。

同时也运用顺序表做一些简单的运用，比如顺序表的并交差运算，学生管理系统等等。

在这次的实验中，我掌握了很多C++的特性，在运用顺序表时，由于水平的原因，只是把简单的并交差运算写完，我想通过以后的学习，我们能够将其实现学生管理系统。

在实验中我也遇到很多的问题，输入输出的重载，输出格式的控制等等，在以后的实验中吸取经验和教训，提高自己的水平。

五．实验代码基类：SqList.;public:构造函数，析构函数，拷贝构造函数的声明SqList();virtual ~SqList();SqList(const SqList<ElemType>& otherL);顺序表的方法有序顺序表的折半查找int bin_Search(ElemType key);把顺序表置空void clear();删除第i个元素Status deleteElem(int i,ElemType& e);取第i个元素int getElem(int i,ElemType& e);求顺序表中元素的个数int getLength();求顺序表存储空间的大小int getListSize();在第i个元素之前插入一个元素Status insert(int i,ElemType e);判断顺序表是否为空bool isEmpty();查找第1个与e满足compare关系的元素的序号int locateElem(ElemTypee,Status(*compare)(ElemType,ElemType));返回某个元素的后继Status nextElem(ElemType e,ElemType& next_e);重载复制运算符SqList<ElemType> operator =(SqList<ElemType> rightL);返回某个元素的前驱Status priorElem(ElemType e,ElemType& prior_e);在顺序表中顺序查找某个元素、int sequentialSearch(ElemType e);};顺序表的方法有序顺序表的折半查找template <typename ElemType>int SqList<ElemType>::bin_Search(ElemType key){int low,mid,-1;while(low<= mid+1;else if(elem[mid]<key)low=mid+1;else 0;把顺序表置空template <typename ElemType>void SqList<ElemType>::clear(){n=0;}删除第i个元素template <typename ElemType>Status SqList<ElemType>::deleteElem(int i,ElemType& e) {if(i<1||i>n) return ERROR;e=elem[i-1];for(int j=i+1;j<=n;++j)elem[j-2]=elem[j-1];--n;return OK;}取第i个元素template <typename ElemType>Status SqList<ElemType>::getElem(int i,ElemType& e) {if(i<1||i>n) return ERROR;e=elem[i-1];return OK;}求顺序表中元素的个数template <typename ElemType>int SqList<ElemType>::getLength(){return n;取顺序表存储空间的大小template <typename ElemType>int SqList<ElemType>::getListSize(){return listSize;}在第i元素之前插入一个元素template <typename ElemType>Status SqList<ElemType>::insert(int i,ElemType e){ElemType *newbase;if(i<1||i>n+1)return ERROR;if(n>=listSize){newbase =new ElemType[listSize+LISTINCERMENT];assert(newbase!=0);for(int j=1;j<n;++j)newbase[j-1]=elem[j-1];delete[] elem;elem = newbase;listSize+=LISTINCERMENT;}for(int j=n;j>=i;--j)elem[j]=elem[j-1];elem[i-1]=e;++n;return OK;}判断顺序表是否为空template <typename ElemType>bool SqList<ElemType>::isEmpty(){return n?false:true;}查找第1个与某元素e满足compare()关系元素template <typename ElemType>int SqList<ElemType>::locateElem(ElemType e,Status(*compare)(ElemType,ElemType)){int i;for(i=1;i<=n&&!(*compare)(elem[i-1],e);++i);if(i<=n)return i;elsereturn 0;}返回某个元素的后继template <typename ElemType>Status SqList<ElemType>::nextElem(ElemType e,ElemType& next_e){int i=locateElem(e,equal);if(i<1||i==n)return ERROR;elsegetElem(i+1,next_e);return OK;}重载运算符的定义template <typename ElemType>SqList<ElemType>SqList<ElemType>::operator=(SqList<ElemType>rightL) {if(this!=&rightL){if(listSize<rightL.listSize){delete[] elem;elem=new ElemType[rightL.listSize];assert(elem!=0);listSize=rightL.listSize;}n=rightL.n;for(int i=1;i<=n;++i)elem[i-1]=rightL.elem[i-1];}return *this;}返回某个元素的前驱template <typename ElemType>Status SqList<ElemType>::priorElem(ElemType e,ElemType& prior_e){int i=locateElem(e,equal);if(i<=1)return ERROR;elsegetElem(i-1,prior_e);return OK;}在顺序表中顺序查找某个元素template <typename ElemType>int SqList<ElemType>::sequentialSearch(ElemType key){for(int i=1;i<n&& key!=elem[i-1];i++);if(i<=n)return i;elsereturn 0;}构造函数的实现template <typename ElemType>SqList<ElemType>::SqList(){elem =new ElemType[LIST_MAX_SIZE];assert(elem!=0);listSize=LIST_MAX_SIZE;n=0;}析构函数的实现template <typename ElemType>SqList<ElemType>::~SqList(){delete[] elem;}拷贝构造函数的实现template <typename ElemType>SqList<ElemType>::SqList(const SqList<ElemType>& otherL) {elem=new ElemType[otherL.listSize];assert(elem!=0);listSize=otherL.listSize;n=otherL.n;for(int i=1;i<=n;i++)elem[i-1]=otherL.elem[i-1];}派生类MySqList.);显示数据void display(ostream& out)const;生成随机顺序表Status randSql(int n,MySqList<ElemType>& otherS);};派生类的实现输入template <typename ElemType>void MySqList<ElemType>::read(istream& in){cout<<"请输入要建立的顺序表的元素个数：";cin>>n;for(int i=0;i<n;i++){cout<<n<<endl;cout<<"请输入顺序表的第"<<i+1<<"个元素：";in>>elem[i];n++;}cout<<endl;}template <typename ElemType>istream& operator >>(istream& in,MySqList<ElemType>& iL) {iL.read(in);return in;}输出template <typename ElemType>void MySqList<ElemType>::display(ostream& out) const {for(int i=0;i<n;i++)out<<"["<<i+1<<"]"<<"\t";out<<endl;for(int i=0;i<n;i++)out<<elem[i]<<"\t";out<<endl<<endl;}template <typename ElemType>ostream& *MySqList<ElemType>::*operator <<(ostream& out,const MySqList<ElemType>& oL){oL.display(out);return out;}生成随机数顺序表template <typename ElemType>Status MySqList<ElemType>::randSql(intn,MySqList<ElemType>& otherS){errno_t err;unsigned int number;int max=100;if(n<1||n>otherS.listSize) return ERROR;else{for(int i=0;i<n;i++){err = rand_s(&number);if (err != 0){printf_s("The rand_s function failed!\n");}otherS.elem[i]=(unsigned int)((double)number ((double) UINT_MAX + 1 ) * 100.0) + 1;}otherS.n=n;}return OK;}21。