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

浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验四 线性表的顺序表示和实现 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1、学会定义线性表的动态分配顺序存储结构。2、掌握线性表的动态分配顺序存储结构及基本操作实现函数。3、进一步熟悉C语言函数的基本结构，掌握程序中的头文件、实现文件和主文件之间的相互关系及各自的作用。二. 实验内容1、编写应用程序（填空），实现可以在顺序表中插入任意给定数据类型（定义为抽象数据类型）数据并求和的功能。要求在主函数中定义顺序表并对该顺序表插入若干个整数类型的数据（正整数），对它们求和并输出。把主函数存放在文件test4.cpp中，其余函数存放在另一个文件SeqList.h。要求使用动态内存分配的方式申请数组空间。请填空完成以下给出的源代码程序并调试通过。（1） 文件SeqList.h:typedef struct List ElemType *list; int size; int MaxSize; SeqList;void InitList(SeqList &L) /初始化线性表 void ClearList(SeqList &L) /清除线性表 int LengthList(SeqList L) /求线性表长度.void TraverseList(SeqList L) /遍历线性表 bool InsertList(SeqList &L, ElemType item, int pos) /按给定条件pos向线性表插入一个元素 .ElemType GetList(SeqList L, int pos) /在线性表L中求序号为pos的元素，该元素作为函数值返回. （2）文件test4.cpp：#include #include typedef int ElemType;#define MAXSize 10;#include SeqList.hvoid main(void)SeqList myList;int i=1, x, sum=0, n;InitList ( myList );scanf(“%d”, &x);while ( x!= -1 ) if ( InsertList (myList, x , i )=0) printf(错误!n);return ; i+; scanf(“%d”, &x);TraverseList(myList)；n = LengthList (myList);for (i=1; i=n; i+)x=GetList(myList, i);sum = sum + x;printf(%dn , sum); ClearList(myList); 2、选做部分：编写函数bool DeleteElem(SeqList &L, int min, int max) 实现从顺序表中删除其值在给定值min和max之间（min max）的所有元素，要求把该函数添加到文件SeqList.h中，并在主函数文件test4.cpp中添加相应语句进行测试。3、填写实验报告，实验报告文件取名为report4.doc。4、上传实验报告文件report4.doc 、源程序文件test4.cpp及SeqList.h到Ftp服务器上（ 40:5000 ）自己的文件夹下。三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路） 1. 初始化线性表：需要完成动态储存空间的初始分配，并且把线性表置为空。 2.线性表的清除：将L清空， 动态空间还给系统。3.线性表的长度只要返回L.size就行。 4.遍历线性表：用 for嵌套进行选择排序，并输出。 5. 线性表的插入： 首先判断POS是否有效，否则返回无效。若是，POS=0，是将item插入并保持有序，此时判断item所要插入的位置，并将值赋给POS。pos=-1，此时将pos=L.size+1。接着判断是否空间足够，不够就重新分配大一倍的空间。待插入位置及所有后续位置元素，从后向前依次后移一个位置，把item的值赋给已空出的（下标为pos-1）的位置，它为第pos个元素位置。 6.get只要返回L.listpos-1就可以了。 7.取出小于或等于min和大于或等于max的部分，再重新组合就行了。四. 实验结果与分析（包括运行结果截图、结果分析等）五. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）遍历需要用for嵌套循环选出最小的一个再一个个。删除min,max之间的数我用了自己的方法，拆了再重组。【附录-源程序】Test4.cpp:#include #include #include typedef int ElemType;#define MAXSize 10;#include SeqList.hvoid main(void)SeqList myList;int i=1, x, sum=0, n, min, max;InitList (myList);scanf(%d, &x);while ( x!= -1 ) if ( InsertList (myList, x, i )=0) printf(错误!n);return ; i+; scanf(%d, &x);TraverseList(myList);n = LengthList (myList);for (i=1; i=n; i+)x=GetList(myList, i);sum = sum + x;printf(%dn , sum);scanf(%d%d,&min,&max);DeleteElem(myList,min,max);ClearList(myList); SeqList.h:typedef struct List ElemType *list; int size; int MaxSize; SeqList;void InitList(SeqList &L) /初始化线性表 L.MaxSize=10;L.list=new ElemTypeL.MaxSize;if(L.list=NULL)cout动态可分配的存储空间用完，退出运行！endl;exit(1);L.size=0; void ClearList(SeqList &L) /清除线性表if(L.list!=NULL)delete L.list;L.list=NULL;L.MaxSize=0;L.size=0;int LengthList(SeqList L) /求线性表长度return L.size;void TraverseList(SeqList L) /遍历线性表int a,j,b,t;for(b=0;bL.size;b+) t=b;for(j=b;jL.listj)t=j;a=L.listb; L.listb=L.listt;L.listt=a; for(int i=0;iL.size;i+) coutL.listi ; coutendl;bool InsertList(SeqList &L, ElemType item, int pos) /按给定条件pos向线性表插入一个元素if(posL.size+1)coutpos值无效！endl;return false;int i;if(pos=0)for(i=0;iL.size;i+)if(itemL.listi)break;pos=i+1;else if(pos=-1) pos=L.size+1;if(L.size=L.MaxSize)int k=sizeof(ElemType);L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k);if(L.list=NULL)cout动态可分配的存储空间用完，退出运行！=pos-1;i-)L.listi+1=L.listi;L.listpos-1=item;L.size+;return true;ElemType GetList(SeqList L, int pos) /在线性表L中求序号为pos的元素，该元素作为函数值返回if(posL.size)cerrpos is out range!endl;exit(1);return L.listpos-1;bool DeleteElem(SeqList &L, int min, int