数据结构实验报告 顺序表

江西理工大学软件学院计算机类课程实验报告课程名称：数据结构班级：姓名：学号：江西理工大学软件学院实验二：顺序表2012年11月10日一.实验目的掌握顺序表的逻辑结构、存储结构、以及操作。二.问题描述线性表是由n(n≥0)个元素（结点）a1,a2,…,an组成的有限序列，其中ai中的i称为该数据元素的位置（序号），n为数据元素的个数（表的长度），当n等于0时称为空表。按逻辑次序依次把数据元素存放在一组连续的地址存储单元里的线性表称为顺序表。在这里，我们通过C++中的动态数组来实现顺序表的存放，并通过建立顺序表类实现它的各种操作。三.实验要求实现顺序表的三个框架操作：随机生成，用已有顺序表初始化另一个顺序表，输入顺序表。以及十个基本操作：在第i个元素之前插入元素，判断是否为空，求元素个数，取第i个元素，查找第一个与e满足compare()关系的元素，返回元素的前驱，返回后继，删除第i个元素，把一个顺序表赋值给另一个顺序表，置空顺序表。四.实验环境3323机房OS：WxpC环境：1、TC2.02、VC++6.0五．运行结果 程序开始界面框架操作：随机生成顺序表（元素值为0到99之间的整数）2.用已有的顺序表初始化另一个顺序表3.输入顺序表基本操作：在第i个元素之前插入一个元素2.判断顺序表是否为空3.求顺序表中元素的个数4.取第i个元素5.查找第一个与之满足compare()关系的元素序号6.返回某元素的前驱7.返回某元素的后继8.删除第i个元素9.把一个顺序表复制给另一个顺序表10.把顺序表置空11.顺序表的运用六．实验心得 熟悉最基本的数据类型——顺序表，同时我们让我们熟练C++的基本操作，模板的使用，以及模块化的设计思想。同时也运用顺序表做一些简单的运用，比如顺序表的并交差运算，学生管理系统等等。 在这次的实验中，我掌握了很多C++的特性，在运用顺序表时，由于水平的原因，只是把简单的并交差运算写完，我想通过以后的学习，我们能够将其实现学生管理系统。 在实验中我也遇到很多的问题，输入输出的重载，输出格式的控制等等，在以后的实验中吸取经验和教训，提高自己的水平。五．实验代码 基类：SqList.h//myhead.h包含自己设定的一些常量和类型#ifndefMYHEAD_H#defineMYHEAD_H//#include"D:\数据结构C++\实验2\myhead.h"#include"D:\Users\fclz\Documents\VisualStudio2010\Projects\数据结构C++\实验2\myhead.h"#endif//顺序表的一些常量说明#defineLIST_MAX_SIZE100#defineLISTINCERMENT10//随机数生成必须#define_CRT_RAND_S#include<stdlib.h>#include<stdio.h>#include<limits.h>//顺序表数据结构的C++类的声明（基类）template<typenameElemType>classSqList{protected: ElemType*elem; intlistSize; intn;public: //构造函数，析构函数，拷贝构造函数的声明 SqList(); virtual~SqList(); SqList(constSqList<ElemType>&otherL); //顺序表的方法 //有序顺序表的折半查找 intbin_Search(ElemTypekey); //把顺序表置空 voidclear(); //删除第i个元素 StatusdeleteElem(inti,ElemType&e); //取第i个元素 intgetElem(inti,ElemType&e); //求顺序表中元素的个数 intgetLength(); //求顺序表存储空间的大小 intgetListSize(); //在第i个元素之前插入一个元素 Statusinsert(inti,ElemTypee); //判断顺序表是否为空 boolisEmpty(); //查找第1个与e满足compare关系的元素的序号 intlocateElem(ElemTypee,Status(*compare)(ElemType,ElemType)); //返回某个元素的后继 StatusnextElem(ElemTypee,ElemType&next_e); //重载复制运算符 SqList<ElemType>operator=(SqList<ElemType>rightL); //返回某个元素的前驱 StatuspriorElem(ElemTypee,ElemType&prior_e); //在顺序表中顺序查找某个元素、 intsequentialSearch(ElemTypee);};//顺序表的方法//有序顺序表的折半查找template<typenameElemType>intSqList<ElemType>::bin_Search(ElemTypekey){ intlow,mid,high;//查找区域的起始、中间以及最后一个元素的下标 low=0,high=n-1; while(low<=high) { mid=(low+high)/2; if(elem[mid]==key) returnmid+1; elseif(elem[mid]<key) low=mid+1; elsehigh=mid-1; } return0;}//把顺序表置空template<typenameElemType>voidSqList<ElemType>::clear(){ n=0;}//删除第i个元素template<typenameElemType>StatusSqList<ElemType>::deleteElem(inti,ElemType&e){ if(i<1||i>n)returnERROR; e=elem[i-1]; for(intj=i+1;j<=n;++j) elem[j-2]=elem[j-1]; --n; returnOK;}//取第i个元素template<typenameElemType>StatusSqList<ElemType>::getElem(inti,ElemType&e){ if(i<1||i>n)returnERROR; e=elem[i-1]; returnOK;}//求顺序表中元素的个数template<typenameElemType>intSqList<ElemType>::getLength(){ returnn;}//取顺序表存储空间的大小template<typenameElemType>intSqList<ElemType>::getListSize(){ returnlistSize;}//在第i元素之前插入一个元素template<typenameElemType>StatusSqList<ElemType>::insert(inti,ElemTypee){ ElemType*newbase; if(i<1||i>n+1) returnERROR; if(n>=listSize) { newbase=newElemType[listSize+LISTINCERMENT]; assert(newbase!=0); for(intj=1;j<n;++j) newbase[j-1]=elem[j-1]; delete[]elem; elem=newbase; listSize+=LISTINCERMENT; } for(intj=n;j>=i;--j) elem[j]=elem[j-1]; elem[i-1]=e; ++n; returnOK;}//判断顺序表是否为空template<typenameElemType>boolSqList<ElemType>::isEmpty(){ returnn?false:true;}//查找第1个与某元素e满足compare()关系元素template<typenameElemType>intSqList<ElemType>::locateElem(ElemTypee,Status(*compare)(ElemType,ElemType)){ inti; for(i=1;i<=n&&!(*compare)(elem[i-1],e);++i); if(i<=n) returni; else return0;}//返回某个元素的后继template<typenameElemType>StatusSqList<ElemType>::nextElem(ElemTypee,ElemType&next_e){ inti=locateElem(e,equal); if(i<1||i==n) returnERROR; else getElem(i+1,next_e); returnOK;}//重载运算符的定义template<typenameElemType>SqList<ElemType>SqList<ElemType>::operator=(SqList<ElemType>rightL){ if(this!=&rightL) { if(listSize<rightL.listSize) { delete[]elem; elem=newElemType[rightL.listSize]; assert(elem!=0); listSize=rightL.listSize; } n=rightL.n; for(inti=1;i<=n;++i) elem[i-1]=rightL.elem[i-1]; } return*this;}//返回某个元素的前驱template<typenameElemType>StatusSqList<ElemType>::priorElem(ElemTypee,ElemType&prior_e){ inti=locateElem(e,equal); if(i<=1) returnERROR; else getElem(i-1,prior_e); returnOK;}//在顺序表中顺序查找某个元素template<typenameElemType>intSqList<ElemType>::sequentialSearch(ElemTypekey){ for(inti=1;i<n&&key!=elem[i-1];i++); if(i<=n) returni; else return0;}//构造函数的实现template<typenameElemType>SqList<ElemType>::SqList(){ elem=newElemType[LIST_MAX_SIZE]; assert(elem!=0); listSize=LIST_MAX_SIZE; n=0;}//析构函数的实现template<typenameElemType>SqList<ElemType>::~SqList(){ delete[]elem;}//拷贝构造函数的实现template<typenameElemType>SqList<ElemType>::SqList(constSqList<ElemType>&otherL){ elem=newElemType[otherL.listSize]; assert(elem!=0); listSize=otherL.listSize; n=otherL.n; for(inti=1;i<=n;i++) elem[i-1]=otherL.elem[i-1];}派生类MySqList.h#ifndefSQLIST_H#defineSQLIST_H#include"SqList.h"#endif#include<iosfwd>template<typenameElemType>classMySqList:publicSqList<ElemType>{public: //读输入数据 voidread(istream&in); //显示数据 voiddisplay(ostream&out)const; //生成随机顺序表 StatusrandSql(intn,MySqList<ElemType>&otherS);};//派生类的实现//输入template<typenameElemType>voidMySqList<ElemType>::read(istream&in){ cout<<"请输入要建立的顺序表的元素个数："; cin>>n; for(inti=0;i<n;i++) { //cout<<n<<endl; cout<<"请输入顺序表的第"<<i+1<<"个元素："; in>>elem[i]; //n++; } cout<<endl;}template<typenameElemType>istream&operator>>(istream&in,MySqList<ElemType>&iL){ iL.read(in); returnin;}//输出template<typenameElemType>voidMySqList<ElemType>::display(ostream&out)const{ for(inti=0;i<n;i++) out<<"["<<i+1<<"]"<<"\t"; out<<