线性表的顺序表示和实现.doc

浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验四 线性表的顺序表示和实现 学生姓名 吴奇 专业班级 信管1204 学号 31201403 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1、掌握线性表的顺序存储结构；2、掌握线性表的动态分配顺序存储结构及基本操作的实现函数；3、进一步熟悉数据结构及算法的程序实现的基本方法。二. 实验内容1、编写应用程序，实现可以在顺序表中插入任意给定数据类型数据并求和的功能。要求把顺序表的结构定义与基本操作实现函数存放在头文件SeqList.h中，主函数存放在主文件test2_1.cpp中，在主函数中定义顺序表并通过调用基本操作函数来实现对该顺序表插入若干个整数类型的数据，然后求和输出。要求使用动态存储分配的方式申请数组空间。2、选做：编写函数bool DeleteElem(SeqList &L, int min, int max)， 实现从顺序表中删除其值在给定值min和max之间（min max）的所有元素，要求把该函数添加到头文件SeqList.h中，并在主文件test2_1.cpp中添加相应语句进行测试。3、填写实验报告，实验报告文件取名为report4.doc。4、上传实验报告文件report4.doc 、源程序文件test2_1.cpp及SeqList.h到Ftp服务器上自己的文件夹下。三. 函数的功能说明及算法思路 struct List /定义线性表的结构体elemtype *list;int size;int maxsize; void initlist(List &L) /初始化线性表LL.maxsize=10; /线性表的最大长度定位10L.list=new elemtypeL.maxsize; /动态申请线性表的储存空间if(L.list=NULL) /判断线性表指向是否为空cout动态分配空间已用完,按任意键退出程序!endl;getchar();exit(0);L.size=0; /线性表的初始长度为0bool insertlist(List &L,elemtype item, int pos) /线性表的元素插入if(L.size=L.maxsize) /判断线性表的储存空间是否满/*L.list=new elemtype2*L.maxsize;*/ int k=sizeof(elemtype);/计算elemtype类型的字符长度L.list=(elemtype*)realloc(L.list,2*L.maxsize*k);/动态申请空间if(L.list=NULL)cout动态可分配的储存空间用完,按任意键退出!endl;getchar();exit(0);L.maxsize=2*L.maxsize; /将线性表的长度扩大2倍L.listpos-1=item; /将输入的元素储存到线性表中L.size+;return true;void travellist(List &L) /遍历线性表的元素int i;cout线性表中的数字为:endl;for(i=0;iL.size;i+) /输出线性表中的所有元素coutL.listi ;coutendl;int lengthlist(List &L) /计算线性表的长度return L.size;int getlist(List &L,int pos) /获取线性表中位于pos位置的元素if(posL.size)cout输入有误,按任意键退出程序!endl;getchar();exit(0);return L.listpos-1; /返回需要获取的元素void clearlist(List &L) /清空线性表Lif(L.list!=NULL)delete L.list;L.list=NULL;L.maxsize=0;L.size=0;bool deleteelem(List &L, int min, int max) /删除线性表中指定范围的元素int lmin,lmax,i,k;lmin=lmax=L.list0;for(i=0;ilmax)lmax=L.listi;for(i=0;iL.size;i+)if(L.listimax|lmaxmax) /判断输入的范围是否有效cout线性表中没有在此范围内的元素或者输入有误，按任意键退出!endl;return false;List a; /建立一个新的线性表ainitlist(a);k=1;for(i=0;iL.size;i+) /把不需要删除的元素放到线性表a中if(L.listimax)insertlist(a,L.listi,k);k+;clearlist(L); /清空线性表LL=a; /把线性表a传给Lif(L.size=0) /判断L中是否有元素cout线性表中元素已经被删光!endl;elsecout删除后线性表中的元素为:;for(i=0;iL.size;i+)coutL.listi ;coutendl;四. 实验结果与分析五. 心得体会做完这个实验，个人感觉有难点，但是仔细去思考，通过书上的内容还是可以理解的，在做线性表这些实验时，最需要的就是耐心和细心，写完每一个函数，都应该去运行调试，这样才能保证每一步都做对。【附录-源程序】Tset4.cpp#include#include#includetypedef int elemtype;#includeSeqList.hvoid main()struct List mylist;int i=1;int x,sum=0,n;int min,max;initlist(mylist);cout请输入正整数,以输入=0的数为结束标志:x;while(x0)if(insertlist(mylist,x,i)=0)cout系统出错,按任意键退出!x;travellist(mylist);n=lengthlist(mylist);for(i=1;i=n;i+)x=getlist(mylist,i);sum=sum+x;cout线性表中所有元素之和为:sumendl;cout请输入你想要删除线性表中元素的范围:endl;coutmin;coutmax;deleteelem(mylist,min,max);clearlist(mylist);SeqList.hstruct Listelemtype *list;int size;int maxsize;void initlist(List &L)L.maxsize=10;L.list=new elemtypeL.maxsize;if(L.list=NULL)cout动态分配空间已用完,按任意键退出程序!endl;getchar();exit(0);L.size=0;bool insertlist(List &L,elemtype item, int pos)if(L.size=L.maxsize)/*L.list=new elemtype2*L.maxsize;*/int k=sizeof(elemtype);L.list=(elemtype*)realloc(L.list,2*L.maxsize*k);if(L.list=NULL)cout动态可分配的储存空间用完,按任意键退出!endl;getchar();exit(0);L.maxsize=2*L.maxsize;L.listpos-1=item;L.size+;return true;void travellist(List &L)int i;cout线性表中的数字为:endl;for(i=0;iL.size;i+)coutL.listi ;coutendl;int lengthlist(List &L)return L.size;int getlist(List &L,int pos)if(posL.size)cout输入有误,按任意键退出程序!endl;getchar();exit(0);return L.listpos-1;void clearlist(List &L)if(L.list!=NULL)delete L.list;L.list=NULL;L.maxsize=0;L.size=0;bool deleteelem(List &L, int min, int max)int lmin,lmax,i,k;lmin=lmax=L.list0;for(i=0;ilmax)lmax=L.listi;for(i=0;iL.size;i+)if(L.listimax|lmaxmax)cout线性表中没有在此范围内的元素或者输入有误，按任意键退出!endl;return false;List